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 :)
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!
0 komentar:
Post a Comment