This week in competitive programming

Last Monday, the Summer 2014 Petrozavodsk training camp came to its conclusion (day 1, day 2, day 3, day 4, day 5, day 6, day 7, day 8, day 9, overall stats, top 5 on the left). Some of the best Russian, Ukrainian, Belarusian, Romanian, Armenian and Kazakhstani teams started their preparation for the new ACM ICPC season that will end with the World Finals in Marrakech in May 2015. Unfortunately, for the first time in my memory, several very strong teams including the World Finals gold medalists Moscow State University team did not participate due to a schedule conflict: many contestants opted for summer internships in technology companies and could not come to Petrozavodsk. Nevertheless, the remaining teams still tried their best to solve problemsets that are often harder than the World Finals themselves. The team of Gennady Korotkevich (he was joined by different ITMO students at each contest) got a clear overall first place by winning most contests, but note that there's still no decision whether Gennady will take part in official ACM ICPC contests in this season (or this decision is a tightly kept secret). The Moscow Institute of Physics and Technology team with the team members from two different last year teams placed clear second, winning two contests and performing well in most others — they will definintely be a team worth watching.

TopCoder SRM 632 took place on Friday afternoon (problems, results, top 5 on the left, my screencast). The medium problem involved a nice graph theory observation: one needed to find the maximum flow in a graph which has different integer powers of 3 as edge lengths. Can you see how we can use the fact that the edge lengths are so exponentially different to create a simple solution?

Codeforces Round 265 rounded up the week on Sunday night (problems, results, top 5 on the left). Tourist has continued his 2014 unbeaten run in Codeforces — great job! — but this time the fight was really close. Both myself and Gennady followed essentially the same strategy during the round, solving 4 out of 5 problems in A, C, B, D order, and looking to find bugs in solutions of other contestants for problem A in between to score some challenge points. Gennady has managed to find 6 incorrect solutions for A while I stopped at 3 incorrect solutions for A and one incorrect solution for B, and those two extra challenges have earned him the first place. The system test showed that there were no incorrect solutions for problem A in my room left standing, so I didn't have a chance to catch Gennady just by challenging solutions for problem A.

However, that same room scoreboard does show my chance to get ahead of Gennady: 3 submissions have failed the system test for problem C. During the round, I have submitted a very simple solution for problem C and thus didn't expect others to submit incorrect ones — it was a big mistake in my thinking. The solutions for C were very short and easy to understand, and thus spotting the incorrect ones could have been easy. What's more, several contestants scored a lot of challenge points by challenging problem C, so I could have noticed that problem C is vulnerable by looking at their stats during the round — but it did not occur to me to do that. Lesson learned: next time I'll do my best to use all information that I have access to, including which problems are being actively challenged by others.

In other news, the round featured a very difficult technical problem E that was solved by just one contestant. Coincidentally, this problem also featured a graph with exponential edge lengths: you were given a graph with at most 100000 vertices, 100000 edges, and each edge length was an integer power of two between 2 and 2¹⁰⁰⁰⁰⁰ (this time the edge lengths were not necessarily different). You were asked a very simple question: to find the shortest path from one vertex to another, suggesting that Dijkstra's algorithm is the way to go. But how does one handle such enormous edge lengths?

Thanks for reading, and check back next week!

Tweet