← All solutions

Shortest judge solution: 1220 bytes. Shortest team solution (during contest): 1888 bytes.

This was conceptually one of the hardest problems in the problemset, although the implementation was actually relatively simple.

Let’s begin by focusing on a single river. So, we pick a river and want to push it as high up the ranklist as possible. Obviously, we always choose this river’s name at any confluence, all the way to the sea. After this, our river has some length L. Now, the problem is to choose other river names at confluences, so that as few rivers as possible end up longer than L.

Let’s call a river long if it’s longer than L, and short if it’s not. We aim to minimize the number of long rivers (which is equivalent to minimizing the places where a short river becomes long). Let’s look at any confluence not involving our chosen river.

• If at least one of the rivers entering the confluence is long, then we can safely choose it to continue (and terminate the other river).
• If both rivers are short, we can always choose the shorter of the two.

This gives us an O(n²) solution to the problem — for each river, calculate its length, and then apply the algorithm above to determine the length of all other rivers.

Now, let’s work on making this work for all rivers at one go.

First, observe that the value L for any given river is simply the distance from the source of this river to the sea. This can be calculated by a standard tree recursion going from the sea in O(n) time for all the rivers.

Now, for each river R, we aim to answer the question “If we always choose R as the river at the confluences on its path to the sea, how many rivers of length larger than L do we have to form?”. This question is difficult to answer for all the rivers at the same time. However, it is actually equivalent to the question “How many rivers of length larger than L do we have to form?” with no additional constraints. To see this, take the optimal naming choice to get as few as possible rivers longer than L described above. Take any confluence where we did not choose the name R. Notice that if we choose the name R at this confluence instead, the number of long rivers does not grow — since no matter how many times we choose R, it is not going to become longer than L, and the lengths of other rivers could only have decreased. Thus, what we have to answer is “how many rivers longer than L do we have to form?” for each value L. We will answer all such questions at one go, ordered by increasing L.

At each time we will keep the current value L. Additionally, for each confluence point and each river source, we will remember it to be in one of the three states:

• At least one of the rivers entering this confluence is long (river sources cannot be in this state). This confluence is irrelevant from the point of view of rivers starting to be long.
• Both rivers entering this confluence are short, or it’s a river source, but the resulting river will become long before it reaches the next confluence point.
• Both rivers entering this confluence are short, or it’s a river source, and the resulting river is still short when it reaches the next confluence point.

In the second and third cases, we choose the shorter of the two rivers entering the confluence to continue.

We begin with L = 0. All river sources are in the second state, all the confluences are in the first state, and we have N long rivers in the system.

When L grows, the only thing that changes is that rivers that were long with the previous value of L can now become short, possibly changing the state of some confluence point or river source from the second to the third; this can in turn change the state of some confluence from the first to the second case. This, in turn, can lead us to reconsider the choice of the river we continue in the confluence point (and possibly trickle down to changing the state of a confluence downstream, and so on).

So, we will do the following. We will keep the states as described above. Additionally, for each point in the second state, we will identify the value of L at which it will flip over to the third state, and keep a priority queue of those points. We repeatedly pick the lowest L value, flip the state of the point, and propagate changes downstream. Note that a single vertex will change state from the first to the second only once, and from the second to the third only once — so the total runtime will be O(n log n), where the log is for priority queue retrieval and insertion.