Problem 2
Let’s relax the problem constraints a bit: in one operation, we may decrement any subarray of length 1, 2, or 3, provided that all elements in that subarray are positive. Evidently, this is a superset of the configurations allowed by the original problem. However, the nice thing about this rephrasing is that order of operations no longer matters.
We will first find an optimal solution under these conditions, then show that it’s still a valid solution under the original conditions.
Relaxed Setting (Solution 1)
First, consider the leftmost element . If , we have to decrement the subarray at least times, so let’s just do these operations first. We now have .
Next, observe that we should never decrement subarray again. This is due to the following lemma:
Lemma 1
Decreasing can never increase the required number of operations.
Proof: First, note that this is not generally true for any . For instance, if , decrementing would result in more operations.
However, is special because it is at the border of the array. Consider an optimal solution for the original array, and run the same sequence of operations on the new array. If a previously-valid operation containing now operates in a state with , there are two cases:
- This operation is . Then, we can just discard it.
- This operation is or . Then, we can replace it with or respectively.
Therefore, the new number of required operations is less than or equal to the original number.
Therefore, we will now only decrement subarrays and . This also means that the final value of is fixed at , while could be any value in the range . Here is the crucial lemma:
Lemma 2
- If , decreasing can never increase the number of operations.
- If , increasing can never increase the number of operations.
Proof: First, consider . Because order of operations doesn’t matter, rearrange operations such that all that apply to are executed first. Each of these operations maintains the condition that , therefore they will always be valid. Afterward, we have , and by Lemma 1 we get our desired result.
On the flip side, consider . Note that we will have to decrement times. Therefore, we can always repurpose some of these to while maintaining the same number of operations.
In other words, is a kind of “global minimum” that we should be aiming toward.
Therefore, our strategy is the following:
while a[0] > 0:
if a[0] > a[1]: decrement [0, 0]
else if a[1] > a[2]: decrement [0, 1]
else decrement [0, 2]
proceed with a[1..n]
We will now show how we can achieve this lower-bound strategy in the original setting.
Relaxed Setting (Solution 2)
This idea is thanks to Benjamin Qi.
The key idea is to maintain a list of extendable intervals at each index, then greedily process from left to right. When we pop intervals, we should pop the longer ones before the shorter ones.
Original Setting
We can operate all subarrays of length 3, then subarrays of length 2 from left to right, then subarrays of length 1. This works because there should never be adjacent subarrays of length 1 and 2 or of length 1 and 1, otherwise our assumption of optimality would be contradicted.
In itself, this approach doesn’t guarantee operations. However, we can show that if we shift all operations on a given index to the last time it’s ever operated, the solution will still be valid. Therefore, any valid solution can be transformed into one which requires runs.
Problem 3
First, we find that each index is constrained to be within some interval based on the min and max constraints. If it is only constrained from one side, we may as well set this value to that constraint in order to satisfy it. Else, we have two choices per index for which constraint to satisfy. If these two constraints are and , we can draw an undirected edge from to . Then, our problem reduces to the following:
Main Problem
Given an undirected graph, direct the edges such that each node has an in-degree of at least 1.
Moreover, it turns out the the following algorithm always works:
while there exists a node with 0 in-degree:
select one such node with minimal undirected-degree
if undirected-degree = 0: matching impossible
else: direct any incident undirected edge toward this node
Proof: Evidently, it is necessary that within each connected component, there are at least as many edges and vertices. We will now show that our above algorithm will always maintain this property.
There are two cases:
- The edge we direct toward node is not a bridge. Then, we have decreased both edge and vertex count by 1, so the property still holds.
- The edge we direct toward node is a bridge. If was a leaf, this is clearly fine. Otherwise, has at least degree 2, which means all other nodes also have at least degree 2. Therefore, after deleting this edge, at most one node has degree 1. Any CC that consists only of degree 2 nodes must satisfy . Therefore, we only need to care about the CC containing the degree 1 node. is definitely at least , but since it has to be even, it must be at least . Therefore, our desired inequality still holds.