Another speaking week

Just like the previous week, the fun of May 8 - May 14 week started on Thursday with a Codeforces round, this time with Playrix Codescapes Cup (problems, results, top 5 on the left, analysis). Even an incorrect submission for E could not stop tourist, as he still won thanks to solving problem G and having much more points than everybody else on F. Well done!

The next round of the week was also a named Codeforces round - this time Tinkoff Challenge Final Round (problems, results, top 5 on the left, analysis, my screencast with commentary). This time explaining everything aloud did not lead to a disastrous performance for me (finally!). Maybe the quality of explanations suffered :) V--o_o--V was still significantly faster, so congratulations on the victory!

Problem D was a nice exercise in discovering a reliable way to detect a relatively simple pattern. You are given a connected undirected graph with at most 300000 edges. You suspect that this graph was constructed in the following manner: we started with a graph with no edges and assigned each vertex an integer label, then connected all pairs of vertices for which labels differed by at most one. Your goal is to return a set of labels that could have been used to construct the given graph, or report that there isn't any.

Later on Saturday, Google Code Jam Round 2 has narrowed the field to just 500 competitors (problems, results, top 5 on the left, analysis). Congratulations to jsannemo on the victory - quite impressive form for the KTH team before the upcoming World Finals, with this win and simonlindholm's win a week earlier.

Yandex.Algorithm 2017 Round 1 took place early on Sunday (problems, results, top 5 on the left, analysis, my screencast). Um_nik was flawless on the five easier problems and correctly noticed the fact that problem E was also, in fact, not very hard. Well done!

Just 80 minutes later, Russian Code Cup 2017 Elimination Round has revealed the 55 finalists (problems, results, top 5 on the left, analysis, my screencast). LHiC did not make any mistakes, and that turned out to be the key to getting the first place. Congratulations!

And finally, Distributed Google Code Jam Round 1 wrapped up the week (problems, results, top 5 on the left, analysis). mk.al13n was ten minutes faster than the rest of the pack in this still quite unusual format with parallel computations. Great job on the victory!

In my previous summary, I have mentioned an AtCoder problem: you are given two trees on the same set of vertices, one blue and one red. You want to convert the blue tree into the red one, step-by-step. At each step, you must take any path consisting of blue edges, add a red edge connecting its endpoints, but remove one of the edges of the path. After n-1 steps all blue edges will be removed, and n-1 red edges will be added, and you want those edges to form the required red tree.

The key idea in this problem is: let's look at the process from the end. Before the last step, we have just one blue edge connecting vertices, say, A and B, so our only option is to remove that edge and add a red edge connecting A and B. Now in the next-to-last step, we must either do the same, or make use of the last blue edge: for example, we can remove blue edge A-C, and add red edge B-C. After some staring at the paper, one can figure out what does this mean: first, we need to find an edge that is both blue and red for the last step, and then we need to contract it - unit its ends together into one vertex. Then, we need to find an edge that is both blue and red in the resulting graph (it might either be blue and red in the beginning, or be a result of a merge of different blue and red edges during the contraction), and contract it again, and so on until the graph is just one vertex.

Now it becomes clear that it doesn't really matter in which order we do the contractions, as they never make things worse. So we should just repeatedly perform any available contraction. There's some technical mastery involved in making the process run in O(n*polylog(n)) time, but that part is relatively standard and I don't want to focus on it too much. You can check the analysis for more details.

Thanks for reading, and check back soon for the last week's summary!