A week after a month

The last week of September was rather busy. The competitions started right on Monday with TopCoder SRM 699 (problems, results, top 5 on the left, analysis, my screencast). At the end of the coding phase, it seemed unusually easy for the recent TopCoder standard, with 8 submissions for the Hard problem. However, the system testing phase showed that even though the general idea of a solution is not hard to see, figuring out all details correctly within the 75-minute round is nearly impossible. matthew99a has thus earned his third SRM victory thanks to super fast solution for the 500, and a solid 100 challenge points to boot. Congratulations!

AtCoder Grand Contest 005 has followed on Saturday (problems, results, top 5 on the left, analysis - scroll down for English). tourist seemed to have started 10 minutes late, so there were some doubts as to who would win initially, but he quashed all of those by finishing all problems within an hour of starting. Amazing job!

The last problem was a great demonstration of the power of combinatorics. You are given a tree with n<=200000 vertices. Now we consider all C(n,k) ways to pick k vertices of the tree, and for each of them we consider the "convex hull" of the k vertices: the smallest part of the tree that connects all of them together. Your goal is to find the sum of the sizes of those convex hulls over all C(n,k) ways. What's more, you need to find n sums: for each value of k between 1 and n. Each sum must be computed modulo 924844033.

Intel Code Challenge Elimination Round started just 15 minutes after the end of AGC (problems, results, top 5 on the left, analysis), so it's super impressive that anta shows in the top 5 of the both events. However, he could not come close to FatalEagle, who has earned his first Codeforces victory thanks to solving all problems and finding 9 successful challenges while doing so. Congratulations!

The second stage of Open Cup 2016-17, Grand Prix of Eurasia, has wrapped up the week (results, top 5 on the left). Problem 1 looked very daunting initially, but as one unraveled it the actual solution turned out pretty and short. You are given an array with n<=100000 numbers, and want to find the segment of that array with the largest sum. That would be too easy, of course, so there's an added twist: you're allowed to do at most k<=10 swaps of two numbers in the array before picking a segment.

In my previous summary, I've mentioned another tricky Open Cup problem: you are given a connected undirected graph with at most 2000 vertices and 2000 edges, where each edge needs to be colored either red or blue. You need to do the coloring using a single alternating walk: you start in some vertex, then keep moving along the edges, coloring the first edge you pass red, the second blue, the third red again, and so on. You are allowed to pass the same vertex and even the same edge twice, and when you pass the same edge multiple times, the last color used stays. Is it possible to obtain the required coloring?

It seems hard to approach this problem because it seems that we can do anything: if we color an edge with the wrong color, we can come back later and use the correct color again, so it's not clear how to see if we're making good progress. The main observation is to look at this process from the end. The last edge we traverse must be colored with its intended color. The edge we traverse before it must also be colored with its intended color, unless it's the same edge. More generally, at each point we have some set of edges we've already traversed, which can now be traversed with any color, and the remaining edges which must be first traversed with their intended color, and our goal is to traverse each edge at least once.

Also, since can always go back and return to any vertex we've already visited with the same parity, the whole concept of a walk is a bit misleading now. We just have a set of (vertex, parity) pairs we can reach, and a set of edges that we've traversed at least once, and are gradually expanding both sets. If two vertices a and b are connected using an untraversed edge with color c, and we have reached (a, c), then we can traverse the edge, and reach (b, 1-c) pair. If the edge is already traversed, then we can also use it to reach (b, c) from (a, 1-c).

To put the solution together, we will maintain a queue of possible moves. When processing a move in the queue, we will add new moves that were made possible by this move to the queue. It's important here to remember that the new moves are of two types: those starting in the new vertex we've reached, and those that use the edge we just traversed with the other color, both in the reverse and in the same direction - many teams have forgotten to account for the latter. And of course we must start from some vertex and some parity - but since the graph is just 2000 in size, we can just iterate over all starting - more precisely, finishing :) - (vertex, parity) pairs.

Thanks for reading, and check back soon for the next week's summary! I promise, "soon" does not mean a month this time :)

Tweet