A Kuhn's week

The Dec 10 - Dec 16 week was livelier than a few previous ones. Codeforces Round 526 started the fun right on Monday (problems, results, top 5 on the left, analysis). Radewoosh continued his string of excellent results, was the only contestant to solve five problems, got the first place with a huge margin and also overtook tourist for the first place in the rating list — very well done!

TopCoder SRM 744 took place on Friday (problems, results, top 5 on the left, my screencast, analysis). Trying to learn from my experience in the TCO final, when approaching the hard problem I have decided to not implement relatively straightforward solutions involving either heavy-light decomposition or propagating piecewise-linear functions up the tree, but instead think a bit more to come up with an easier to implement solution. The strategy has almost backfired as I got my "simple" solution to work with less than two minutes into the contest. However, it did work in the end as a few other contestants going for the straightforward but complicated implementation approaches have failed because of subtle bugs (for example, ainta was above me after the coding phase but his solution failed as he should've used a multiset instead of a set, presumably inside the representation of a piecewise-linear function or something similar).

Here's that problem: you are given a rooted tree with 100000 vertices. Each vertex has a demand d_i and a cost c_i. Your goal is to assign some non-negative value v_i to each vertex so that the demand of each vertex is less than or equal to the sum of values on the path from this vertex to the root of the tree, and the sum of c_i*v_i is minimized. What's the easiest to implement approach, in your opinion?

AtCoder Grand Contest 029 followed on Saturday (problems, results, top 5 on the left, my screencast with commentary, analysis). The problemset was relatively approachable this time, so to win one had to be fast and to minimize incorrect attempts. LHiC executed very well on both fronts and got first place with the margin of 12 penalty minutes. Well done!

I was submitting my last problem around 88-th minute for the first time, but got time limit exceeded on just one testcase. My solution involved Dinic's maximum flow algorithm that I have copy-pasted from a previous solution. Later I submitted the same solution in C++ and it passed in just 0.5s, while the time limit is 4s. Maybe somebody can tell why Java is more than 8x slower this time?

Of course, later I tried submitting Kuhn's maximum matching algorithm in Java instead, which is supposed to be quadratic in the worst case, but it actually passed within the time limit :)

Reducing the problem to maximum matching is also quite fun. Here's the statement: you are given n vertices, and n-1 sets of those vertices, each of size at least 2. Your goal is to pick exactly two vertices in each of the n-1 sets in such a way that if we draw the n-1 edges connecting each chosen pair to each other, we get a tree. n is at most 100000, and the total size of the given sets is at most 200000.

Open Cup 2018-19 Grand Prix of Peterhof took place on Sunday (results, top 5 on the left). Compared to a few previous rounds, the Moscow SU team has cut down dramatically on incorrect attempts, and thus got their first win of the season. Congratulations!

Problem G was a nice dynamic programming exercise. Two players are playing a game on a rooted tree with 100000 vertices. They make moves in turn. In each move of the first player, she colors one of the leaves of the tree black (initially all leaves are colored white). The root of the tree also initially contains a token. In each move of the second player, she can move the token from a vertex to any adjacent vertex. The second player wins if she moves the token to a leaf that is still white. The first player wins when all leaves are colored black and the second player has not yet won. Who will win if both players play optimally? Can you see a way to avoid traversing the entire ~2¹⁰⁰⁰⁰⁰ state space?

Finally, Codeforces ran Avito Cool Challenge 2018 later on Sunday (problems, results, top 5 on the left, analysis). tourist was a bit slower than LHiC but was able to find two challenges and regain the first place in the round, and with it the first place in the rating list. Congratulations!

Thanks for reading, and check back for more!