← All solutions

Problem authors:
Matthias Ruhl and Derek Kisman
Solved by 72 teams.
First solved after 32 minutes.
Shortest team solution: 513 bytes.
Shortest judge solution: 407 bytes.

Define the “joint order” on the containers that are still on the two stacks as follows. Assume a₁, . . ., a_k are the containers on the first stack, from bottom to top, and b₁, . . ., b_l are the containers on the second stack from bottom to top. Then the “joint order” is a₁, . . ., a_k, b_l, . . ., b₁.

Take any two containers i and j. Notice that at any point in the unloading process, before either i or j are loaded onto a truck, the joint-order interval between i and j contains the containers that were in the interval between i and j before the loading started, minus the containers that were already loaded onto the trucks.

Let us now say we have two containers a_i and a_i+1, and we want to know how many containers we will need to move before unloading a_i+1. The answer is exactly the set of containers in the joint-order interval a_i, a_i+1.

So, now we need to figure out the expected number of containers that are in the joint-order interval a_i, a_i+1 at the time when we try to unload a_i+1. We want to check for some container v what is the probability that v is in this interval.

If v got unloaded before a_i, the probability is zero. Otherwise, the probability is equal to the probability that v is in the joint-order interval at the beginning of the loading. And this probability is 0 if v < min(a_i, a_i+1) in the unloading order, and 1/2 if v > min(a_i, a_i+1) in the unloading order.

Actually calculating the number of containers smaller than min(a_i, a_i+1) that are also loaded after a_i can be done in O(log n) for a single container using a data structure that supports point updates and range sums, such as a range tree or a Fenwick tree.