PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Dynamic Programming
PROBLEM:
You have a binary array A of length N.
In one move, you can increase any element of A by 1.
Find the minimum number of moves needed to ensure that A_i \ne A_{i-1} for all indices i.
EXPLANATION:
Since all the elements of A are initially either 0 or 1, and we only care about adjacent pairs of elements being distinct, intuitively it seems like we shouldn’t have to increment any single index too much.
Indeed, it can be proved that in an optimal solution, we’ll never need to use a value larger than 2.
Proof
Suppose we’ve performed several increment operations in our solution, and ended up with a value \gt 2 somewhere.
Since this is a valid solution, we additionally know that A_i \ne A_{i+1} for all indices.Consider the leftmost occurrence of an element that’s \gt 2, say at index L.
Now,
- If A_L \gt 3, let’s first bring A_L down to 3. This of course reduces the number of increments needed.
Note that this surely won’t cause a conflict with A_{L-1}, though it might create a conflict with A_{L+1}; we’ll deal with that later.- For now, let’s look only at A_{L-1}. We know that A_{L-1} \le 2 for sure.
- If A_{L-1} \le 1, we’re happy.
- If A_{L-1} = 2, we can instead reduce A_{L-1} by 1.
- If this creates a conflict with A_{L-2}, then increment A_{L-2} by 1 instead.
- If this creates a conflict with A_{L-3}, then decrement A_{L-3} by 1, and so on.
- Essentially, we’re able to alternate increments and decrements till we reach the first element (or stop earlier) while ensuring that all elements before index L remain \le 2.
- This doesn’t increase the number of operations, since we started with a decrement (at index L-1).
- So, we’re now in a situation where A_L = 3 and A_{L-1} \le 1, without increasing the number of moves.
- Next, we look at A_{L+1}.
- If A_{L+1} doesn’t exist, i.e. L = N, then we can simply decrement A_L to 2 and still have a valid array.
- Otherwise, if A_{L+1} \ge 3 or A_{L+1} \le 1, we can again decrement A_L by 1 and be fine.
- This leaves the case of A_{L+1} = 2.
Here, if A_{L+2} \ne 3, then we can ‘swap’ A_L and A_{L+1} by decrementing A_L and incrementing A_{L+1} instead.
If A_{L+2} = 3, then we can just decrement both A_L and A_{L+1}.Observe that no matter what, we’re able to end up in a situation where we have A_i \le 2 for all i \le L, without increasing the number of moves used.
This means the ‘first large element’ has now moved to an index beyond L (if at all possible).
Repeatedly performing this process, we’ll end up eliminating all elements \gt 2 from the array without increasing the number of increment operations done, as desired.
Since the only possible values are 0, 1, 2, we can now solve the problem with a fairly straightforward dynamic programming solution.
Define dp(i, x) to be the minimum number of increments needed among the first i elements such that:
- A_i = x, and
- A_j \ne A_{j+1} for each 1 \le j \lt i
Transitions are simple:
- If x \lt A_i, we define dp(i, x) = \infty since it’s impossible to achieve A_i = x.
- Otherwise, we have dp(i, x) = (x - A_i) + \min_{y \ne x} dp(i-1, y).
This is because we need (x - A_i) increments at index i, and then index i-1 just needs to contain any value other than x.
The answer is the minimum of dp(N, 0), dp(N, 1), dp(N, 2).
We have 3N states, and there are 2 transitions from each of them.
So, this runs in \mathcal{O}(N) overall and is easily fast enough.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
dp = [ [10**18 for i in range(3)] for i in range(n) ]
for x in range(a[0], 3): dp[0][x] = x - a[0]
for i in range(1, n):
for x in range(a[i], 3):
for y in range(3):
if x != y: dp[i][x] = min(dp[i][x], dp[i-1][y] + x - a[i])
print(min(dp[n-1]))