In this subchapter, we will work on a real ICPC problem, namely problem F from NWERC 2024, Flowing Fountain.

Problem Please read the problem description Flowing Fountain.

Test Cases

In addition to the two sample inputs in the problem description, write a couple of test cases yourself. In particular,

A fountain that only contains containers with size increasing from top to bottom,
1. where you pour the champagne only into the top container
2. where you have some other pouring scheme
Only of decreasing size with some reasonable pouring scheme.
Some other test cases you come up with, in particular edge cases.

An inefficient solution

On the surface, this is a simple simulation process. We can maintain an array capacity and an array content; the latter is initialized with zeroes. At each pouring, we change content[i] and if capacity[i] is reached, we look for the next bigger container $j \gt i$. Thus, a query of the form + l x will take $O(n)$ steps in the worst case. This solution will surely be deemed to slow by an online judge, but it will be a good starting point.

Exercise Implement the inefficient $O(nq)$ solution outlined above and create a couple of test cases.

Efficient solution

Call a level full if the amount of champagne it contains equals its capacity. So when capacities are [2 4 3 5] and amounts are [2,2,3,1] then level $1$ and $3$ are full but level $2$ and $4$ aren't. For each level $l$, define ${\rm target}(l)$ to be the level into which the champagne would flow if we pour into level $l$; let ${\rm target}(l) = n+1$ if it would pour on the floor. Observe that ${\rm target}(l) \ne l$ if and only if $l$ is full. A group is a set of levels that all have the same target. Write ${\rm group}(l)$ to denote this group. For a group $g$, let ${\rm bottom}(g)$ be the bottom element in the group - the one that is the common target of all $l \in g$.

When pouring into level $l$, find $g = {\rm group}(l)$.
Find $b = {\rm bottom}(g)$.
Pour into $b$. If $b$ spills over, we have to find the next greater element from $b$; call this $c$.
Merge the group $g$ with the group of $c$. The bottom of the new group will be ${\rm target}(c)$.

The two main tasks - (1) find to which group an element belongs (a find operation) and (2) merge two groups (a union operation) can be achieved by a union-find data structure. The most well-known is probably union-by-rank, which you can read about in Chapter 7.5 of TI-1. If you don't read German, just google "union by rank" and you'll find ample material.

Theorem The data structure union-by-rank requires at most $O(\log n)$ steps per operation (find or union).

There is a natural improvement to union-by-rank called path compression (see Chapter 7.6 of TI-1) that achieves almost constant amortized time per query. It's challenging to analyze but trivial to implement; in fact, for the Flowing Fountain problem we seem not to need it - my solution with union-by-rank but without path compression still was accepted.

Stupid mistakes a made. So finally I got my code for the flowing fountain accepted at open.kattis.com. It took me a while. Here, I want to talk about my (stupid) mistakes, so you can avoid them.

Debug messages. To check whether my solution did the correct thing, I had a line
```
        print(str(amounts))
```
that, after each pouring of champagne, would print the array of amounts per level. No, I wasn't going to be so stupid as to submit a program that still outputs debug messages, so I changed the line to
```
        debug_print(str(amounts))
```
and in debug_print I could control with a single boolean variable verbose whether outputs happen. So my output was indeed correct. But my program was too small. I didn't understand why. When I ran big but simple instances, I discovered that my program had quadratic performance. No surpise! I was converting a size-$n$-array to a string after each query! My time complexity was roughly $\Theta(nq)$ with $n$ being the number of levels and $q$ the number of queries. Naturally, I assumed my data structure was insufficient (union with path-compression but without rank) so I tried hard to construct an example where this data structure performs poorly, to no avail.

Moral: Write large test cases, all the way up to the stated bounds (here: 300,000 levels). You'll need a program that generates those test cases, naturally.
RecursionError: maximum recursion depth exceeded. This is a python thing. Python does not allow very deep recursion. And the most natural way to implement a union-by-rank with path compression data structure is with recursion. Once I wrote an iterative solution, it got accepted.
Moral: Avoid recursion in python. Or, use sys.setrecursionlimit(400000), but whether this is allowed might depend on the specific judge or contest. open.kattis.com seems to allow it, and indeed it accepted my recursive solution.