Monday, April 7, 2014

This week in competitive programming

TopCoder SRM 615 took place on Friday (problems, results, my screencast, top 5 on the left). The medium problem asked a somewhat classical but still interesting question: given an undirected graph with at most 50 vertices, at most 50 edges, and relatively small integer edge lengths (up to 10000), is there a path from vertex 1 to vertex 2 that is exactly T long (where T can be very big, up to 1018)? The path can of course pass through the same vertex or edge many times.

This question turned out to be really tough - it was only solved correctly by 17 contestants, compared to more than 100 contestants solving the hard problem which was supposed to be more difficult. I guess the point value for this problem was set so low because it's standard, so the judges assumed people would know how to solve it?..

Open Cup has returned on Sunday with its 12th stage (results, top 5 on the left). This round had wider participation than usual with strong teams from the United States and China in the standings. 39 teams that will participate in the ACM ICPC World Finals in June were participating, and here's the link to standings filtered to only those teams.

And finally, Codeforces wrapped up the weekend with their Round 240 (problems, results, top 5 on the left). I didn't solve the round myself, so I don't have anything to say about the problems. The round's winner was decided on challenges, which are always a big gamble in the Codeforces format where you have to choose between spending time on challenges early in the contest (while the points for each unsolved problem are ticking down) and solving the problems first (while the easy challenges are taken away by others). Personally, I think that challenging early makes sense only if you're looking for a concrete mistake that you can spot in several seconds, so that you can gain a lot if the mistake turns out to be widespread, or give up quickly if people don't seem to make that mistake.

Thanks for reading, and see you next week!