This week in competitive programming

The week was relatively silent with just two rounds, both on Thursday. Most competitions decided against having rounds this weekend, most probably because many of the top competitors were traveling to one of the most important competitive programming event of the year - the ACM ICPC World Finals, this time in Yekaterinburg. I will try to post some updates from the event in my blog.

TopCoder SRM 625 was the first to go (problems, results, top 5 on the left, my screencast). Like in SRM 617, the most memorable moment of the match happened during the challenge phase, where I had to come up with a challenge case against an obviously incorrect solution. This time it was not very difficult, but still cute. The medium problem had a quite complicated statement which I can't really explain in a few words - so please read it if you want to understand the problem :) The problem boiled down to finding a minimum cut where both the vertices and the edges had capacities and could be cut. The correct way to do that is to duplicate each vertex of the graph, direct all incoming arcs to the first copy, all outgoing arcs from the second copy, and connect the first copy to the second copy with an arc of capacity equal to the capacity of the vertex. This way we reduce the vertex capacity case to the edge capacity case, and then we can use the standard maximum flow algorithm to find the minimum cut. The solution in question (TopCoder login required to view) skipped the duplication, and instead just propagated the capacity of the vertex to all adjacent arcs - if an adjacent arc had a higher capacity, it was reduced to the capacity of the vertex. It's not that hard to come up with a challenge case in the graph formulation - but a bit harder in the problem's grid formulation. Can you challenge this solution?

And of course, congratulations to Bruce on the convincing victory!

Codeforces Round 253 featured problems from one of the World Finals competitors, Boris from SPb ITMO team (problems, results, top 5 on the left). Gennady "tourist" won the match and was the only contestant to solve the problem "Gena and Second Distance". The background story of this problem, quite ironically, told that Gena (a reference to tourist himself) doesn't want to solve this problem and asks you to do it instead of him. Apparently he still had to do it after all :)

Thanks for reading, and check back tomorrow for some World Finals updates!