PROBLEM LINK:
Author: Roman Rubanenko
Tester: Tuan Anh
Editorialist: Florin Chirica
DIFFICULTY:
hard
PREREQUISITES:
sqrt decomposition
PROBLEM:
You’re given two arrays. On first one, we add arithmetic progression on on some intervals of it. We need to output, for each position, minimal number of operations (done in the order given in the input) needed to make element from the first array greater or equal to one from the second array.
QUICK EXPLANATION:
One possible solution is sqrt decomposition. We add each step sqrt progressions at a time. Using a clever progressing, we can compute the resulting array in O(n). We check positions that respect the wanted conditions. For each, we “undo” the sqrt operation done and brute force one more time sqrt operations. This way, for each position, we find exact number of operations after which element from the first array became greater or equal to the one from the second one.
EXPLANATION:
An easy simplification
Let’s do for beginning an easy simplification. Instead of using two arrays A and B, we can solve the problem with a single array X. Denote by X[i] = A[i] - B[i]. Now, when performing an operation, instead of adding the amount to the array A, we’ll add it to the array X. After some operations, some terms of X become positive. The first moment when X[i] becomes positive represents the first operation when A[i] >= B[i]. Why? Suppose delta is the amount added until X[i] becomes greater or equal to 0.
X[i] + delta >= 0
A[i] - B[i] + delta >= 0
A[i] + delta >= B[i]
which is exactly what we were interested in.
Now the problem is: given an array X, find for each i the minimal number of operations such as X[i] >= 0. From here, there are multiple approaches possible. I’ll just describe my favorite one:
SQRT Decomposition
The idea is to process sqrt(n) operations at a time. We perform sqrt(n) operations, then see what happens, then perform some more sqrt(n) operations, again see what happens and so on.
Let’s find a quick way to see how our array X will look after sqrt(n) operations. In order the solution to pass TL, we need to do this in O(n), giving O(n * sqrt(n)) time.
We need a trick: suppose we have operations like increase all elements from x-th to y-th by a value val. We can get final form of the array in O(n + numberOfOperations).
Let’s use an auxiliary array A. When we are given an operation defined by x, y and val, we do:
A[x] += val;
A[y + 1] -= val;
Then, answer on position i, after all operations, is A[1] + A[2] + … + A[i]. Draw it on the paper and you’ll see why it works.
Now we add an arithmetic progression defined by l, r, x and y (like in the statement). Obviously, all elements from l to r need to be increased by x. This, can be done as above.
Now, element from position l needs to be increased by y, element from position l + 1 by 2 * y and so on. Let V be the array, if considering only operations involving y (adding y, 2 * y, 3 * y and so on).
For an operation l, r, x, y, one can easily notice that V[i] = V[i - 1] + y, for each i between l + 1 and r. Now, answer for position i is A[1] + A[2] + … + A[i] + V[i].
What happens if two numbers y and y2 need to be added at V at position i? Well, we simply do V[i] = V[i - 1] + y + y2. Hence, the problem reduced to: add value y from all elements from l+1 to r. How to do this? Yes, one more array (suppose it’s Y):
Y[l + 1] += y;
Y[r + 1] -= y;
Now, V[i] = V[i - 1] + Y[1] + Y[2] + … + Y[i] and answer for position i of X[i] is V[i - 1] + Y[1] + Y[2] + … + Y[i] + A[1] + A[2] + … + A[i]. This way, we can get O(n) to recognize an array after sqrt(n) steps.
What now? Some elements become >= 0 after sqrt(n) operations. This means, somewhere in these sqrt(n) operations, we fount the answer for the elements. But how to find out exactly the moment when this happened?
Suppose X[i] becomes >= 0 after sqrt(n) operations. We can “undo” those sqrt(n) operations. Then, we can simply simulate again those sqrt(n) operations, only for element from position i.
What’s the complexity for this step? Obviously, each element can become >= 0 for the first time exactly one time (after this, we’re not interesed anymore). So, we get at most n elements. For each, we simulate at most sqrt(n) operations. Hence, this step is also O(n * sqrt(n)) and whole solution is O(n * sqrt(n)).
If you have another approach, please share it in the comments section!
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution to be updated soon
Tester’s solution