A week without branching and the best problem of 2019

Codeforces Round 616 took place last week (problems, results, top 5 on the left, analysis). Three contestants could solve five problems, but tourist's solution for the hardest problem F was so fast that he got almost a thousand points more. Congratulations on the win!

In my previous summary, I have mentioned a TopCoder problem: there are n=2*a+b pieces of string, out of which a have both ends red, a have both ends green, and b have one red and one green end, so we have n red ends and n green ends in total. We will randomly pair the red and green ends in one of n! possible ways, and tie the corresponding ends together. What is the expected number of cycles we will get? a and b are up to a million.

The first idea is to notice that if we pair just one green end with just one red end, then one of the two things can happen:

• either they have belonged to two different strings, in which case we have effectively replaced two strings with one, and the colors of its ends correspond to the colors of the other ends of the original two strings, or
• they have belonged to the same string, in which case we have formed a cycle.

In either case, the problem reduces to the same problem with n-1 strings, which means that a dynamic programming solution is on the cards. However, since both a and b are up to a million, a naive dynamic programming approach would have on the order of 10¹² states, which is too much.

However, we still have the freedom of choosing which pair of green and red ends we use for reducing the problem to size n-1. If b>0, then we will choose which green end is one of the red ends of the first green-red string paired with. The key fact is that no matter which string (green-green, or green-red) we attach to the red end of a green-red string, the new string is of the same type, since we just "extend" its green end effectively! Moreover, if we tie this string to itself (the probability of which is 1/n), we also just reduce the number of green-red strings by one. Therefore we always go from the state (a,b) to the state (a,b-1) this way, and there is no branching:

f(a,b)=f(a,b-1)+1/(2*a+b)

When b=0, we have only red-red strings and green-green strings, and thus all our choices for the first move are symmetric: we will tie a red-red string and a green-green string to obtain a red-green string. Therefore there is no branching as well:

f(a,0)=f(a-1,1)

Now we can unroll this recursion to get a simple formula that can be computed in O(a+b).

I have also ran a poll for the best problem of 2019. You can see the results on the left, and the best problem with 68 out of 174 votes is the problem Split the Attractions from IOI 2019 by LGM and Saeed_Reza. Congratulations to them and to all problemsetters of 2019!

Here is what that problem is about: you are given a connected undirected graph with n vertices and m edges, and you are also given three positive integers a,b,c such that a+b+c=n. Your goal is to split all vertices of the graph into three parts, the first of size a, the second of size b, and the third of size c, in such a way that at least two of those parts are connected using only the graph edges within the part. n<=100000, m<=200000.

Thanks for reading, and check back for more.