PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You’re given an array A.
In one move, you can add either [1, -1, 1, -1, \ldots] or [-1, 1, -1, 1, \ldots] to any of its subarrays.
Find the minimum number of moves needed to make all the elements of A become 0.
EXPLANATION:
This problem can be solved by looking at a couple of transformations of the array.
First, alternating updates are somewhat annoying to deal with, so we’ll get rid of them.
Consider a new array B of length N such that:
- If i is even, B_i = A_i
- If i is odd, B_i = -A_i
Essentially, we’re negating alternate elements of B.
This is helpful because it turns our operation into something a bit nicer - adding [1, -1, 1, -1, \ldots] to the range [L, R] of A now corresponds to either:
- If L is even, add [1, 1, 1, \ldots] to [L, R] in B.
- If L is odd, add [-1, -1, -1, \ldots] to [L, R] in B.
Similarly, adding [-1, 1, -1, 1, \ldots] to a range of A will correspond to adding either +1 or -1 to the entire range in B instead, dependent on the parity of the left endpoint.
So, we’re left with only simple range addition of +1/-1 in B.
Note that A has all its elements become 0 if and only if all the elements of B are 0, so we can now focus entirely on making B have all zeros using these two types of operations.
To solve the modified problem on array B, we once again consider a transformation.
When dealing with operations on a range, prefix sums and difference arrays are common quantities to look at - we’ll use the latter.
Consider the difference array of B, which is an array D of length N such that:
- D_1 = B_1, and
- D_i = B_i - B_{i-1} for 2 \le i \le N
Again, B has all zeros if and only if D has all zeros; so we focus on making D have all zeros with minimum moves.
Adding x to range [L, R] of B corresponds to:
- Increment D_L by x, and
- Decrement D_{R+1} by x.
In particular, when R = N the element D_{R+1} doesn’t exist so we only increment D_L by x.
So, if we choose R \lt N then the sum of D doesn’t change; while if R = N the sum of D increases by x.
Now, let S_p denote the sum of positive values in array D, while S_n denotes the sum of negative values in the array.
Note that the sum of the whole array D equals S_p+S_n.
We have a few cases.
Case 1: S_p+S_n = 0
In this case, the array already has a sum of 0 so we only need to ‘redistribute’ values in such a way that every individual element becomes 0.
This can be done in exactly S_p moves, since in each move we can choose one positive element and one negative element and bring them both closer to 0 (by choosing x=1 or x=-1 for the operation appropriately).
Note that if the sum of an array is 0 and not all its elements are 0, then it surely will have a positive and a negative element, so this is always possible.
We use exactly one move for each positive bit of value, hence S_p moves in total are needed.
(Note that this is also equal to -S_n moves.)
Case 2: S_p + S_n \gt 0
In this case, we definitely need S_p + S_n moves to bring the sum of the array to 0 in the first place; since in a single move we can only decrease the sum by 1.
It’s not hard to see that it’s optimal to perform all these moves on existing positive elements - and hence, S_n won’t change in value.
Thus, after the array attains a sum of 0, another -S_n moves are needed to make each element individually 0.
The total number of moves is hence S_p + S_n - S_n = S_p.
Case 3: S_p + S_n \lt 0
This is basically the same as the previous case, just that we operate on negative elements instead and so the final value comes out to be -S_n.
All three cases can be combined into the simple expression \max(S_p, -S_n), which is also an obvious lower bound on the number of moves (the total positive quantity needs at least S_p moves to become 0, the total negative quantity needs at least -S_n moves to reach 0) and hence is optimal.
Everything here can be computed in linear time so we’re done.
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()))
b = [a[i]*((-1) ** (i%2)) for i in range(n)]
d = [b[0]] + [b[i] - b[i-1] for i in range(1, n)]
pos = sum(x if x > 0 else 0 for x in d)
neg = sum(x if x < 0 else 0 for x in d)
print(max(pos, -neg))