A week before IOI

Codeforces Round 313 has set the tone for an active week after a few very calm ones (problems, results, top 5 on the left). Only TooSimple and qwerty787788 have managed to solve all problems, but the former has picked much better problem solving sequence, and thus won convincingly - great job, and great preparation for the upcoming IOI in Kazakhstan!

TopCoder SRM 663 took place 25 hours later (problems, results, top 5 on the left, my screencast). Subscriber has found two crucial challenges and claimed the victory - great job! Of course, the challenge phase would have much less importance had myself or anybody else managed to solve the hardest problem: we have n binary variables a₁,a₂,...,a_n, each initialized randomly, independently and uniformly to 0 or 1. Then, we repeatedly pick two random indices i and j such that i < j, and set overwrite a_j with the value of a_i. This process will stabilize as soon as all variables have the same value. Before that happens, what's the expected number of times the given sequence of variable values (n numbers, 0 or 1 each, corresponding to the n variables in order) appears?

I've spent an awful lot of time digging in various wrong directions, and with just about 10 minutes to go in the coding phase a good idea came to my mind: simulate the probability of getting each sequence of 0s and 1s for a small value of n after each step. This simulation revealed a very unexpected observation (which can be proved by induction): the probability of seeing any given sequence at any given step depends only on the number of 0s/1s in the sequence, and not on the positions of those 0s and 1s!

Can you figure out the rest? It is relatively easy, but I needed quite some time to finish the implementation after the round - it took me maybe 20 more minutes to get working.

VK Cup 2015 Finals have also happened today, but the results or problems are not available online yet - we can just look at Daria' twitter so far.

Thanks for reading, and check back next week!

Tweet