PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
A lot of time was spent in building this intricate problem. The inspiration for the problem came from an IMO 1986 problem, called the “pentagons problem”.
The expected solution was O(N log N) in complexity. The solution is described below in two sets of insights required to solve the problem.
Set 1. Basic solution
Given the array of N numbers A[0 to N-1]. Let us imagine an infinite array a, such that a[i+N] = a[i].
Let us construct the sums array
b[0] = 0
b[i] = b[i-1] + a[i] for i > 0
We notice that the array is periodically increasing.
That is, because s = summation(0<=i<N, a[i]) > 0 (given in the problem statement) and
b[N+i] = b[i] + s
Now, we notice that if a[i] is negative, then b[i] < b[i-1] and if a[i] is positive, then b[i] > b[i-1].
The above is true for all i, N+i, 2N+i, 3N+i and so on.
Hence, we say that negative a[i] create inversions.
There are may be an infinite number of inversions in the sums array.
Let us say, whenever we are performing the operation on A[i], that is adding its value to A[i-1] and A[i+1] and changing its sign, we are also performing the operation on a[i+N], a[i+2 * N], a[i+3 * N] and so on, but we do not perform the operation on a[i].
Notice that performing operation on a[t], swaps adjacent values in the b array constructed from this a. In fact, performing operation on a[t], swaps b[t-1] and b[t]. It also swaps b[t-1+N] and b[t+N]; b[t-1+2N] and b[t+2N] and so on.
We can only invert the two indexes i and i+1 if N <= i < 2N.
The sums array is sorted and increasing when we have reached a solution.
Thus, this is similar to sorting an array by inverting adjacent elements.
Now we use some non-intuitive insight!
-
Let T be the number of inversions such that there is an N <= i < 2N and j > i where b[j] < b[i].
(in fact T is same for any consecutively selected N items from the sums array. we can select 0 <= i < N also.) -
Every time we invert two values b[i] and b[i+1], such that b[i+1] < b[i], we reduce T by 1.
(note that inverting adjacent values means we invert the sign of a[i+1] and add its previous value at a[i] and a[i+2]) -
Every time we invert two values b[i] and b[i+1], such that b[i+1] > b[i], we increase T by 1.
-
If T is not 0, there would always be an inversion in i and i+1 for N <= i < 2N
-
When T is 0, we have solved the problem.
Thus,
The solution to the problem is calculating the number T. The number of inversions i and j, such that 0 <= i < N and j > i where b[j] < b[i].
Note that we can infer there is no * optimal * way of solving a particular given array of A. We can safely select any negative number each time and perform the operation on that
The array will consist of all non-zero values in the same number of steps every time!
But, the test cases are such that the number of steps might be very large - most results not fit in 32-bit integers! So simply simulating will not solve the problem 
The number of inversions in b can be calculated in O(N * N) time.
Namely let 0 <= i < N, i < j < i + N. Then due to the condition b[k+N]=s+b[k] we have b[j+k * N]=b[j]+s * k. So for k >= 0 we have that b[i] and b[j+k * N] give an inversion if b[j]>b[j]+k * s. So the number of inversions that gives i with j, j+N, j+2 * N, … is equal to ceil( (b[i]-b[j])/s ), where ceil(x) is equal to the least integer not less than x.
But that will time-out within the time limits. There is a better solution still.
Set 2. Advanced solution
(This solution is all courtesy Anton. Thanks a ton! Most of the notes in this editorial are made by himself.)
- Rotate A such that b has all positive values.
Let b[0] = a[0] and b[i]=b[i-1]+a[i] (1 <= i < n).
Let s = b[n-1]. That is s is the sum of all a[i]'s.
Next we find such index i0 (0 <= i0 < n) such that b[i0] <= b[i] for 0 <= i < n.
That is b[i0] is the minimal value from all b[i]'s.
We can rotate A such that i0 is at the 0’th index. This way, the new array b, has only positive values.
- Sort b
But not just sort
We note that the solution still is the number of inversions in b.
We calculate the number of inversions in b, while sorting b. We notice that we now get a partially sorted array
s=b[n]<=b[n+1]<=b[n+2]…b[2n-1] and so on.
Let the number of inversions calculated be I.
- The formula for remaining inversions
Since 0=b[0]<=b1<=…<=b[n-1] the answer can be calculated in the following manner.
Let 0<=i<n. Find k such that b[k-1]+s < b[i] <= b[k]+s (b[-1] = -infinity).
The number of inversions in b, due to b[i], are
summation(0<=j<k, ceil( (b[i]-b[j])/s ) - 1 ).
Note that value of k can only increase when i steps to i+1.
Now, ceil( (a-b)/s ) = ceil(a/s) - ceil(b/s) + int(r(a) < r(b))
where r(a) = (a % s) > 0 ? (s - (a % s)) : 0
and int(x < y) is equal to 1 if x < y, and equal to 0 if x >= y.
Using this formula we can rewrite our formula as follows
summation(0<=j<k, ceil(b[i]/s) - ceil(b[j]/s) + int(r(b[i]) < r(b[j])) - 1) =
k*ceil(b[i]/s) - summation(0<=j<k, ceil(b[j]/s) ) - summation(0<=j<k, int(r(b[j]) <= r(b[i])) )
summation(0<=j<k, ceil(b[j]/s)) can be pre-calculated by formulas
sb[0] = 0
sb[k] = sb[k-1] + ceil(b[k-1]/s) (0<k<n).
The only left question is how to calculate the summation(0<=j<k, int(r(b[j]) <= r(b[i])) ) part.
- . Binary indexed tree to the rescue!
Let’s construct sorted array of all different values among r(b[i]) (0<=i<n) and denote them by
0<=r1<r2< …<r[m].
We must maintain a table R[x] which will tell us the index ‘i’, such that r[i] = x.
Let f 1 ,f 2 ,…f[m] be a binary-indexed tree for summation.
As was said before the value k will only increase when i steps to i+1.
So, every time we increment k, we make an addition query to our tree at R[r(b[k])].
The value of summation(0<=j<k, int(r(b[j]) <= r(b[i])) ) would now be the summation query for R[r(b[i])]!
Thus we obtain a solution with O(N log N) time complexity:
1st step is O(n)
2nd step is O(n log n) (merge sort)
3rd step is O(n)
4th step is O(n log n) (O(n) queries to the binary indexed tree each requires O(log n) operations).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.