This week in competitive programming

This week's contests started with TopCoder SRM 622 early on Thursday (problems, results, top 5 on the left). The medium problem was a nice (spoiler alert!) greedy algorithms practice. You're given a tree with edge lengths and a constant M, and need to remove some edges to separate the tree into the smallest number of connected parts in such a way that each part's diameter is at most M. A diameter of a graph is the maximum of lengths of all shortest paths between its nodes. Can you see how and why it can be solved greedily? Even the official editorial suggests to use dynamic programming here :)

This round also made SPb SU 4 an all-target (3000+ TopCoder rating) team: Dima, rating 3027, 18th in the world, Egor, rating 3019, 20th in the world, and Pasha, rating 3001, 24th in the world. Congratulations!

The weekend had a bunch of elimination rounds for "big" contests. I guess it's not that much of a coincidence - most contests have elimination rounds in spring and onsite finals in autumn. The first to go was Google Code Jam 2014 Round 2 on Saturday (problems, results, top 5 on the left). It narrowed the field from 3000 competitors still hoping to win the grand prize to 500 - just one online round left before the finals in Los Angeles!

Early on Sunday, Yandex.Algorithm 2014 Elimination Round 1 became the first test of various strategies for the blind/open format (results, top 5 on the left). Unfortunately the problems are not visible to those who's not logged in, so it doesn't make much sense to discuss them here. As for the strategies, this time getting a good result required solving six problems correctly and at least 2-3 of them blindly.

Later on Sunday, Russian Code Cup 2014 Quaification Round 4 (problems, results, top 5 on the left) was the last chance for everybody to qualify for the Elimination Round. Congratulations to Fefer.Ivan on solving all problems correctly almost half an hour before everybody else!

And finally, Codeforces Round 250 rounded up the busy Sunday (problems, results, top 5 on the left). The round had a very standard problem as problem C - to count the number of triangulations of a non-convex polygon - but it still held a surprise! The usual solution splits the problem into two parts: first, we solve the tedious geometric problem to find whether each diagonal is inside the polygon. Then, we use dynamic programming that counts the number of triangulations of each sub-polygon formed by taking consecutive edges of the polygon plus one diagonal. The dynamic programming transition is obtained by considering which will be the third vertex of the triangle containing the diagonal as its side, and thus separating the problem into two analogous problems.

bmerry, though, has managed to avoid the geometric part almost completely! Here's his code: codeforces.com/contest/438/submission/6768704. Instead of checking that the triangle has valid diagonals as its sides, he just checks that the triangle is oriented correctly. Initially, this doesn't seem a sufficient condition, since the polygon is non-convex and thus even a correctly oriented triangle might intersect another side of the polygon. However, it turns out that in such cases there will be zero triangulations of the part that has a self-intersection. In other words, we'll find no way to find the next triangle some way down the dynamic programming. Is there an easy way to prove that?

Thanks for reading, and see you next week!