A showdown week

The Nov 30 - Dec 6 week started with TopCoder SRM 674 on Tuesday (problems, results, top 5 on the left). The top fives this week have many people in common, as NEERC participants were going through the final preparations before the big contest. In the SRM, subscriber from the SPb ITMO team claimed the first place, and Um_nik from the Ural FU team claimed the third place, while xudyh in second place is also from a very strong ACM team from Tsinghua - which in shocking news is skipping the World Finals next year.

Codeforces Round 334 happened later on the same day (problems, results, top 5 on the left, editorial), and once again subscriber was at the top - congratulations! The third place went to Zlobober who's also representing a strong NEERC team - this time from Moscow SU.

Problem E in this round caught my attention, but I was a little bit too slow and finished my solution a few minutes after the end of the round. Here's what it was about: you're adding weighted edges one by one to an undirected graph, and after adding each edge we want to know the answer for the following question: what's the smallest number A such that there exists a subset of edges, such that each edge in the subset has weight at most A and each vertex is incident to an odd number of edges from the subset? There are 100000 vertices and 300000 edges.

There's a very nice post (spoiler alert!) on Codeforces describing various approaches to solving this problem. I've implemented something very similar to winger's approach, only splitting the larger of the two segments in half instead of always splitting the first segment in half. In general I think about this family of approaches for solving offline dynamic connectivity problems as "Burunduk1's master's thesis", although I'm not entirely sure if that is an accurate description :)

And finally, ACM ICPC 2015 NEERC itself took place on Sunday (problems, results, top 5 on the left, editorial, video broadcast recording in Russian, online mirror results). A few teams have battled for the top spot, but in the end the Ural FU team has managed to solve one problem more than everybody else, and will be one of the favorites for the 2016 World Finals in Thailand!

There were many nice problems in the problemset, but my favorite is problem J. The judges have a hidden binary string of 1000 zeroes and ones, and you have to guess it using at most 1500 attempts. For each attempt, you output some string of 1000 zeroes and ones, and the judge responds with one of three answers: either your guess is correct (and that means you've won); it's incorrect but _exactly_ half (500) of all characters are correct; all other incorrect situations grouped together. At first sight it seems impossible to make any progress when you only get interesting replies if you guess exactly 500 characters correctly, but it turns out this information is enough to guess the hidden string very fast.

Thanks for reading, and check back soon for the Dec 7 - Dec 13 week summary!