A uniform combination week

Most teams have returned home from Beijing by the end of the Apr 23 - Apr 29 week, and the other contests returned in full swing. AtCoder Grand Contest 023 took place on Saturday (problems, results, top 5 on the left, analysis). The round was won by none other than the newly minted World Champion cospleermusora (also known as V--o_o--V and overtroll). yutaka1999 was also able to solve all problems, but required 30 more minutes to do so. Congratulations to both!

Problem F was very cute. You are given a tree with 200000 vertices, each containing a number, either 0 or 1. We need to put all its vertices in some order in such a way each vertex except the root appears to the right of its parent. We will then write out a sequence of 0s and 1s corresponding to numbers in the vertices in this order. What is the minimum possible number of inversions in this sequence? An inversion is a pair of positions such that the number in the left position is 1, and the number in the right position is 0.

Maybe I enjoyed this problem because I have set a problem in the past which involved the same strategy for producing a string from a tree.

VK Cup 2018 Round 3 happened on Sunday (problems, results, top 5 on the left, parallel round results, analysis). The ICPC champions, this time two of them, kept with their champion-y ways and solved two more problems than everybody else. Unbelievable!

I found problem C exceedingly beautiful. You are given 100000 numbers up to 2⁶⁰. You need to put them in such order that the xors of all prefixes of the resulting sequence form a strictly increasing sequence themselves.

Right after the Codeforces round ended, Google ran Code Jam 2018 Round 1B (problems, results, top 5 on the left, analysis). overtroll has continued his impressive form (see above) with another victory, this time with a healthy margin of 12 minutes. Well done!

In my previous summary, I have mentioned a World Finals problem: there are n people, each starting with 1 gem. The following operation is repeated d times: take one of the gems uniformly at random, and split it into two gems (so the person holding it will have one more gem). After doing all that we order all people by the number of gems they have in decreasing order, and add up the number of gems of the first r people in that order. What is the expected value of that sum? n and d are at most 500.

The first part of the solution is understanding the sequence generation process. At the first sight, it looks rather complicated, with the probability to get a new gem for each person changing along the way. However, let's look at the process from the following angle: let's put all gems for all people in one sequence, and every time a gem is divided we'll insert a new gem to the right of it. We'll also distinguish the original gems — the ones people start with — from the newly generated ones.

We start by having n original gems, and we can notice now that at each step we simply insert a new gem into a position in our sequence that is picked uniformly at random, except from the position before the first original gem which is never used. This in turn makes it clear that the resulting sequence starts with an original gem, and then has a sequence of n-1 original gems and d new gems picked uniformly at random from all C(n-1+d,d) such sequences. Each person gets all gems from their original gem to the next original gem in this sequence.

A uniformly chosen combination is a well-known object which is easy to work with, which allows us to proceed with solving the problem using either dynamic programming or more combinatorics, as outlined in the semi-official analysis.

Thanks for reading, and check back around the next weekend for more!