Codeforces Round #353 (Div. 2) - C. Money Transfers

Problem Statement:
Codeforces Round #353 (Div. 2) - C. Money Transfers

Summary:
Given a circular array A[1..n] such that the sum of all its elements is zero, find the minimum number of steps needed to make every A[i] equal zero, if at each step we can take any value from A[i] (with positive value) and move it to either A[i-1] or A[i+1] (elements on immediate left/right of A[i]).



Solution:
This is such a cool problem. I was not able to solve it without reading the editorial, which you can find here: http://codeforces.com/blog/entry/44902. I really like the solution. The first observation is that if we have a segment S[1..n] such that the sum of the elements in the segment is 0, then we need n-1 steps to make all the elements in S equal 0. To see this, imagine that we are filling the gap between two consecutive elements in S with a left or right arrow:
S[1] _ S[2] _ S[3] _ ... _ S[n], where _ will be filled with either -> or <- arrow.
Consider the leftmost negative element of S, say at index i:
1. If i is not equal to 1, then we have some positive elements to the left of S[i]. We have no choice but to move these elements to the right towards S[i], starting from the leftmost element S[1], demonstrated by the following arrows: S[1] -> S[2] -> ... -> S[i-1] -> S[i]. Hence we have filled all the arrows on the left part of S[i]. As the result, we now have S[1] = S[2] = ... = S[i-1] = 0.
2. S[i] is currently either still negative or already a positive number. If S[i] is already a positive number, we repeat step 1 on the next leftmost negative element in S.
3. Otherwise, S[i] is still negative. We can find the first a positive S[j] to the right of S[i] such that S[i]+S[i+1]+...+S[j-1]+S[j] >= 0. We know that this must be true since if there is no such S[j], then since S[i]+S[i+1]+...+S[n] = 0, S[n] must be negative. Suppose S[k] be the rightmost positive element of S, then S[i]+S[i+1]+...+S[k-1]+S[k] = -(S[k+1]+...+S[n]) > 0, a contradiction.
4. Hence suppose S[i]+...+S[j] = R. R must be less than S[j], otherwise we have S[i]+...+S[j-1] = R-S[j] > 0 and if S[j-1] > 0 we have contradiction for minimality of j, otherwise S[j-1] < 0 and hence S[i]+..+S[j-2] = R-S[j]-S[j-1] > 0 and we repeat the process, with the basis where we conclude that S[i] > 0, which contradicts definition of S[i]. Then we can move S[j]-R towards S[i], such that all S[i] = S[i+1] = ... = S[j-1] = 0, while the remaining of S[j] must be positive and hence we can repeat step 1 by finding the next negative element after j. In this process we have filled the arrows S[i] <- S[i+1] <- ... <- S[j], up to j (which equals to j-1 arrows). Hence by repeating this process until j = n, we will fill in n-1 arrows, and hence n-1 steps taken to make all S[i] = 0.

Now with that, we go to the next cooler observation: If we compute the prefix sum of A, the minimum number of steps needed is n subtracted by the maximum number of repeating elements in the prefix sum. To see why, suppose we have the following prefix sum P[1..n]. We have P[n] = 0 by definition. Let's say the maximum recurring value in P is v, and it has indices i[1], i[2], i[3], ... up to i[k]. We can rewrite those as P[i[1]] = a[1], P[i[2]] = a[1] + a[2], P[i[3]] = a[1] + a[2] + a[3], ..., P[i[k]] = a[1] + ... + a[k], P[n] = a[1] + a[2] + ... + a[k] + a[k+1], where a[i] is the sum of elements in the non-overlapping segments that make up each P[i[j]]. Then we know that a[1] = v, a[2] = 0, a[3] = 0, ..., a[k] = 0, and a[k+1] = -v. This means that if we recompute the prefix from the first element making up a[2], then we will have k segments with 0 sum. Thus in total we will need n-k number of steps to make all A[i] 0.

(Wow I spend so much time writing about it. I really like the problem and the subtlety behind it.)