Monday, July 27, 2015

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 a1,a2,...,an, 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 aj with the value of ai. 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!

No comments:

Post a Comment