Two Tanks
Contest: Educational Codeforces Round 145 (Rated for Div. 2)
Difficulty rating: 2400
Tags: binary search, dp, implementation, math

There are two water tanks, the first one fits $$$a$$$ liters of water, the second one fits $$$b$$$ liters of water. The first tank has $$$c$$$ ($$$0 \le c \le a$$$) liters of water initially, the second tank has $$$d$$$ ($$$0 \le d \le b$$$) liters of water initially.

You want to perform $$$n$$$ operations on them. The $$$i$$$-th operation is specified by a single non-zero integer $$$v_i$$$. If $$$v_i > 0$$$, then you try to pour $$$v_i$$$ liters of water from the first tank into the second one. If $$$v_i < 0$$$, you try to pour $$$-v_i$$$ liters of water from the second tank to the first one.

When you try to pour $$$x$$$ liters of water from the tank that has $$$y$$$ liters currently available to the tank that can fit $$$z$$$ more liters of water, the operation only moves $$$\min(x, y, z)$$$ liters of water.

For all pairs of the initial volumes of water $$$(c, d)$$$ such that $$$0 \le c \le a$$$ and $$$0 \le d \le b$$$, calculate the volume of water in the first tank after all operations are performed.

Input format:
The first line contains three integers $$$n, a$$$ and $$$b$$$ ($$$1 \le n \le 10^4$$$; $$$1 \le a, b \le 1000$$$) — the number of operations and the capacities of the tanks, respectively.

The second line contains $$$n$$$ integers $$$v_1, v_2, \dots, v_n$$$ ($$$-1000 \le v_i \le 1000$$$; $$$v_i \neq 0$$$) — the volume of water you try to pour in each operation.

Output format:
For all pairs of the initial volumes of water $$$(c, d)$$$ such that $$$0 \le c \le a$$$ and $$$0 \le d \le b$$$, calculate the volume of water in the first tank after all operations are performed.

Print $$$a + 1$$$ lines, each line should contain $$$b + 1$$$ integers. The $$$j$$$-th value in the $$$i$$$-th line should be equal to the answer for $$$c = i - 1$$$ and $$$d = j - 1$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Consider $$$c = 3$$$ and $$$d = 2$$$ from the first example:

- The first operation tries to move $$$2$$$ liters of water from the second tank to the first one, the second tank has $$$2$$$ liters available, the first tank can fit $$$1$$$ more liter. Thus, $$$\min(2, 2, 1) = 1$$$ liter is moved, the first tank now contains $$$4$$$ liters, the second tank now contains $$$1$$$ liter.
- The second operation tries to move $$$1$$$ liter of water from the first tank to the second one. $$$\min(1, 4, 3) = 1$$$ liter is moved, the first tank now contains $$$3$$$ liters, the second tank now contains $$$2$$$ liter.
- The third operation tries to move $$$2$$$ liter of water from the first tank to the second one. $$$\min(2, 3, 2) = 2$$$ liters are moved, the first tank now contains $$$1$$$ liter, the second tank now contains $$$4$$$ liters.

There's $$$1$$$ liter of water in the first tank at the end. Thus, the third value in the fourth row is $$$1$$$.

Example input:
3 4 4
-2 1 2

Example output:
0 0 0 0 0 
0 0 0 0 1 
0 0 1 1 2 
0 1 1 2 3 
1 1 2 3 4

Example input:
3 9 5
1 -2 2

Example output:
0 0 0 0 0 0 
0 0 0 0 0 1 
0 1 1 1 1 2 
1 2 2 2 2 3 
2 3 3 3 3 4 
3 4 4 4 4 5 
4 5 5 5 5 6 
5 6 6 6 6 7 
6 7 7 7 7 8 
7 7 7 7 8 9

Editorial:
Consider a naive solution. Iterate over all pairs $$$(c, d)$$$ and apply all operations. The complexity is $$$O(a \cdot b \cdot n)$$$. The constraints obviously imply that it's too much. What can we cut from it? Well, surely $$$O(n)$$$ will still remain there. Both of $$$a$$$ and $$$b$$$ also should. So we can probably only hope to turn this $$$O(ab)$$$ into $$$O(a + b)$$$. Let's try that.
Notice that no matter what operations are applied, $$$c + d$$$ never changes. You can also peek at the examples and see that the patterns are suspiciously diagonal-shaped in the matrix. Let's try to solve the problem by fixing $$$c + d$$$ and calculating the answer for all values of $$$c$$$.
I will call the fixed $$$c + d$$$ variable $$$\mathit{cd}$$$. Consider case where $$$\mathit{cd} \le a$$$ and $$$\mathit{cd} \le b$$$. Here, all $$$\mathit{cd}$$$ can fit into both $$$a$$$ and $$$b$$$, so we can avoid caring about one restriction on the operations. We'll think what to do with large volumes later.
If there are no operations, the answer for each initial $$$c$$$ is $$$c$$$ for all $$$c$$$ from $$$0$$$ to $$$\mathit{cd}$$$. Now consider an operation $$$x$$$ for some $$$x > 0$$$. For $$$c = 0$$$, nothing changes. Actually, for all $$$c \le x$$$ the result of the operation is the same as for $$$c = 0$$$. Hmm, but if the result is the same, it will remain the same until the end. Same from the other side. The answers for $$$x < 0$$$ and $$$d \le -x$$$ also get merged together. To me it kind of looks like a primitive form of DSU on these volume states: you merge some prefix of the answers together and merge some suffix of the answers together.
If the state was merged to either $$$c = 0$$$ or $$$d = 0$$$, then it's easy to calculate the actual answer for that state. What happens to the remaining states? Well, since they weren't merged anywhere, the operation for them was applied fully: if $$$x$$$ was requested, all $$$x$$$ was poured.
How to deal with multiple operations then? I propose the following idea. When applying an operation, we only want to know which of the previously non-merged states become merged. Basically, we can squish all previous operations into one: just sum up the signed amounts of water. Since they all were applied fully to the non-merged states, it's completely valid. After the squish, check for the new merges.
You can actually study the structure of the answers and see that they go like that: $$$[l, l, \dots, l, l + 1, l + 2, \dots, r - 1, r, \dots, r, r]$$$ for some values of $$$l$$$ and $$$r$$$ such that $$$l \le r$$$. It isn't that important, but it makes the code easier. You can basically calculate the length of the merged prefix, the length of the merged suffix, then calculate the answer at the end of the prefix in $$$O(n)$$$ and restore all answers from it.
We neglected larger values of $$$\mathit{cd}$$$ earlier, time to return to them. Another kind of limit to each operation is added: when $$$x$$$ extra water doesn't fit in another tank. Well, it doesn't change that much. It only makes more prefix/suffix merges. To come up with the exact formulas, I followed these points. Something merges on an operation $$$x$$$, when any of these holds:
• $$$c < x$$$ (not enough water in the first tank);
• $$$b - d < x$$$ (not enough space in the second tank);
• $$$d < -x$$$ (not enough water in the second tank);
• $$$a - c < -x$$$ (not enough space in the first tank).
Replace all $$$d$$$ with $$$\mathit{cd} - c$$$, and you get the constraints for prefix and suffix merges.
Overall complexity: $$$O(n \cdot (a + b))$$$.