This week in competitive programming

The main event of this week, of course, was the ACM ICPC 2014 World Finals in Yekaterinburg (problems, results, top 5 on the left). I've passed on the joy on just being a spectator, and tried to solve the problems in real-time instead - but during the moments I was able to look at the scoreboard, it was surprisingly emotional to see my alma mater, Moscow State University, at the top of the standings. It's really sad that we're in second place for the fourth time but have never won.

The problemset was quite interesting, as usual at the World Finals, but quite heavily biased towards geometry problems. Two tedious geometry problems (J and L) went unsolved - but you can look at the excellent explanations in Bruce Merry's blog. Problems A and H were also unsolved at the contest, but they were solved at the online mirror. There's some more solution explanation at TopCoder forums, including some firsthand explanations by one of the judges - SnapDragon. And finally, here's an explanation of problem H by Gawry in Polish. Google Translate seems to give a rough idea, and it's very similar to my solution: for every "suffix" of the field (rows below a certain one), we calculate three w times w (w is up to 20) matrices, describing what happens if we enter this suffix at position i: the probability of us leaving the suffix up at position j if we enter it at position i, the probability of us finishing in the first line of the suffix at position j if we enter it at position i, and finally the probability of us finishing somewhere in the suffix but not in the first line, if we enter it at position i, and go down from it for the last time from position j.

The twelve medals were split like this: four went to Russia, three went to Mainland China, and one each to Taiwan, Japan, Poland, Croatia and Slovakia. The picture of the champions on the left is from their official VK page. Congratulations to all medalists and to all participants of the World Finals - getting there is a great achievement by itself!

I hope to see most of you again next year in Morocco :)

When most teams were back at home, TopCoder held SRM 626 (problems, results, top 5 on the left, my screencast). Somewhat standard easy and hard problems were complemented with a beautiful medium problem: you are given a directed graph with 50 vertices where each arc has two costs: expensive one and cheap one, where the cheap cost can be negative and expensive one is always non-negative. What is the cheapest path from vertex A to vertex B that uses cheap arcs at most K times?

Egor won the round by finding two challenge opportunities in a mostly dry challenge phase - congratulations! It was only fitting that the round was held on his birthday :)

Thanks for reading, and check back next week!

Tweet