Sunday, December 8, 2013

This week in competitive programming

The weekdays featured just one contest, TopCoder SRM 599 on Wednesday (problems, results, top 5 on the left, my screencast). The hard problem was: you are given a directed graph with at most 50 vertices and at most 8 edges (so most vertices don't have any adjacent edges at all), and a rooted tree with the same number of vertices. How many ways are there to map the vertices of the graph to the vertices of the tree (one-to-one) such that each edge of the graph corresponds to ancestor-descendant pair in the tree? One funny aspect of this problem is the complexity of the solution. If 50 is N and 8 is M, then the expected solution complexity was O(N*5M), the solution that the authors were trying to fail was O(N*9M) (more details from the problem author at Codeforces), and I've managed to come up with a O(N*7M) solution they didn't expect, and barely squeeze in the time limit.

The weekend featured elimination rounds for two annual contests. On Saturday, the first official round of the Kotlin Challenge took place (problems, results, top 5 on the left). This is a brand new competition with problems in Russian, final round in St Petersburg in April 2014, and only one allowed programming language - Kotlin. I'm pretty sure almost all contestants at the top of the scoreboard didn't know the language before, but it appears that it's conventional enough and learning to do simple things using it is not hard. Even if you missed this round, you still have a chance to register and participate in the next round this Wednesday, but keep in mind that all tasks and judges communication is in Russian.

For 24 hours between Saturday and Sunday, the first round of the Facebook Hacker Cup took place. Since they don't publish the problems and the scoreboard, I assume they don't want to encourage discussion so I won't go deeper here :)

Thanks for reading, and see you next week!

No comments:

Post a Comment