A Young week

Lacking the usual Codeforces and TopCoder rounds, this week has nevertheless provided some great problems to solve. On Friday, Yandex.Algorithm 2016 Final Round pitted the best 25 in the world against each other for the fame and roughly $5000 first prize (problems with Yandex login, results, top 5 on the left, online mirror results, analysis, my screencast). Egor has won with a sizeable margin mostly thanks to quick and correct solutions to the very tricky problems B and F - great job!

Nobody has managed to solve problem E during the round, which is a pity since the solution is quite beautiful. Here's what the problem asked: consider sequences of 2n parentheses of n different types such that there's exactly one opening and exactly one closing parenthesis of each type. A sequence is considered good if the parentheses can be colored with two colors in such a way that the subsequences formed by each color are balanced parenthesis sequences. How many good sequences exist for the given n? n is up to 500.

A Japanese competition website AtCoder has recently started supporting English, and ran AtCoder Grand Contest 002 on Sunday (problems, results, top 5 on the left, analysis, my screencast). The Code Jam-like penalty system allows one to solve the problems in arbitrary order, and semiexp took full advantage of that by starting with the fourth problem, and still being the fastest to finish. Congratulations!

Problem E was a nice game analysis task. Two players were playing on a Young diagram by placing a token in the top left corner, and then taking turns in moving it. At each move, a player can move the token either down or to the right. The player who can't make a move loses. Who's going to win if both play optimally? There are at most 10⁵ rows, each at most 10⁹ in length.

I've mentioned quite a few problems last week, one of which was: you are given an undirected graph with at most 1000 vertices and at most 1000 edges, such that each vertex has at most three adjacent edges. Each vertex also has a weight, and you need to pick at most K edges maximizing the total weight of vertices covered by (adjacent to at least one of) the picked edges. The interesting aspect is that K is really small: at most 7. So you're allowed algorithms exponential in K, but polynomial in the size of the graph.

The key to solving this problem is the following observation. Consider the edge e that has the highest sum of weights of its ends. Taking e unconditionally into the answer would be greedy which does not always work. But let's think a bit more why it might not work. Consider the case where the optimal answer does not contain e. If that answer also does not contain any other edges incident to the ends of e, then we can add e to that answer, remove any other edge, and obtain another answer with the same or greater score, as e has the highest sum of weights. That means the optimal answer should contain either e, or one of the edges adjacent to its ends. And since the degree of each vertex is at most 3, that means we have at most 5 edges to choose from!

Having made this observation, we can complete the solution in several possible ways. The most straightforward way is to put all edges into a heap using the total weight of uncovered edges as the key, allowing us to find the maximum edge quickly, and thus completing our search roughly in 5⁷ operations. Another way is to take the same argument slightly further by noticing that all edges of the answer must be among the 5*7=35 edges with the highest total weight of the ends, as otherwise there will be at least one edge there that does not have common endpoints with any edge of the answer, and thus replacing the cheapest edge with it would improve the answer.

Thanks for reading, and check back next week!