This week in competitive programming

Saturday night was the competition time this week, starting with TopCoder SRM 647 (problems, results, top 5 on the left, my screencast). The hard problem had a very simple and interesting statement, might've looked as a relatively straightforward maximum flow application, but it came with an unexpected twist that foiled many experienced competitors. You were given a directed graph where each arc has a cost, one of the vertices is marked as starting point, and one as ending point. You needed to pick a subset of arcs with the smallest total cost such that every path from the starting point to the ending point (including paths that pass through the same vertex or arc more than once) passes through arcs from this subset exactly once.

The idea that we can use minimum cut theory to find this subset looks natural. But just applying minimum cut algorithms on the given graph doesn't fit the bill: it is indeed guaranteed that we will cross every cut at least once when walking from the starting point to the ending point, but we might also cross a cut twice or more, and this is not allowed by the problem statement. The usual recipe in situations like this is adding auxiliary infinite arcs to the graph which will essentially limit the set of cuts we look at, since the minimum cut will obviously contain no infinite arcs. Can you see how to add infinite arcs to this graph to solve the problem?

Just a few hours later Facebook Hacker Cup 2015 Round 2 narrowed the field of competitors to just one hundred algorithmists (problems with Facebook login, results with Facebook login, top 5 on the left, my screencast). Once again, the really punishing scoring model meant making sure that the solutions are correct was more important to qualifying than solving problems fast. Nevertheless congratulations to Ivan on claiming the first place! The competition at the ACM ICPC World Finals is going to be very fierce this year.

 

Somewhat orthogonally, here are a couple of pictures from my recent touristic visit to London. Quite different skies and quite different surroundings, London is full of everything :) Thanks for reading, and check back next week!