ACM ICPC World Finals 2018

On April 19th 2018, the world finals of ACM ICPC took place. This is the largest collegiate level programming contest where teams of three take on tough algorithmic problems in five hours.
This year, the contest took place in Beijing (click here to view the problems and here to view the final standings). This year’s contest was tough with the first place team, Moscow State University, being the only team to get 9 out of the 11 problems. In this summary, I’ll go over one of the harder problems, problem D, that requires a key insight that makes the problem approachable to solve.
In the problem there is an island with n people, each of which who has a single gem. There are d number of nights, and every night, one gem uniformly at random will split into two, meaning that the person who owns the gem will gain another gem. In particular, this scheme makes the rich get richer, as having more gems makes it more likely to gain more gems in the future. At the end of d nights, you sort the people by the number of gems they own and sum up the number of gems held by the top r people. The problem is to compute the expected value of this sum, given n, d, and r. Each of these numbers maximum value is 500.
To solve this problem let’s consider the case when there are only two people on the island. Consider the distribution of the gems that the first person will have after d nights.
For d = 1, the probability that the first person has 1 gem is ½, and the probability they have 2 gems is ½.
For d = 2, the probability that the first person has 1 gem is (½ * ⅔) = ⅓, 2 gems is (½ * ⅓ + ½ * ⅓) = ⅓, and 3 gems is (½ * ⅔) = ⅓.
At this point, you can start to guess that this distribution is uniform (i.e. the probability person 1 will end with k gems for k=1,2,...,d+1 is equal to 1/(d+1)).
Let’s visualize another way to see why this might be the case. Consider a necklace of beads. Initially there are only two beads, one is labeled “1” and the other is labeled “2”. Now, you will add d unlabeled beads into this circle, one by one. At each iteration, you will uniformly at random choose one bead on the necklace and insert an unlabeled bead immediately clockwise to it. We can see this is a bijection to our original problem (i.e. the number of gems person 1 has will be equal to the number of beads that is clockwise after bead 1 and before bead 2).
Now, consider this process in reverse. Initially, we start out with d+2 unlabeled beads. At each iteration, we will remove a random bead until we are left with two beads. At this point, we can randomly label the beads 1 and 2. We can see this process is the same just in reversed time, but if we look at the final two beads, it is equally likely they are in any two positions on the necklace with d+2 beads. Thus by this bijection, we can see the distribution for how many gems each person gets is uniform.
To generalize this further, we can start with n beads on the necklace, with labels 1,2,...,n and repeat the same process of inserting a bead d times. We can see the distribution of gems to the people is also uniform (i.e. the probability that person 1 gets a_1 gems, person 2 gets a_2 gems, …, person n gets a_n gems where a_1+a_2+...+a_n = d is equally likely).
At this point, the problem becomes a more standard dynamic programming problem, for which I will not go into details for now.
Hope you enjoyed reading the summary of one of the problems from the world finals!