This week in competitive programming

As advertised, the week started with IOI 2014 (problems, results, top 5 on the left). I like the problem "Game" a lot, since it's both interesting to solve and has a very simple but unusual setting. Two players are playing a game on N vertices. On each turn, the first player picks a pair of vertices, and the second player has to either draw an edge connecting them, or declare that there's no edge connecting them. The first player asks about each of N*(N-1)/2 pairs exactly once, and his goal is to figure out whether the graph will be connected after the game ends; the second player's goal is to keep the connectedness (ugly word, but is there a better choice?) of the graph unknown until the very last answer. N is up to 1500, time limit for the entire game is 1 second.

IOI and other high school competitions are well-known for tasks where the contestant has to implement one player of a game, and the judges provide the other player. However, a usual setting in games like this one would be for the competitor to be the player asking questions, and the jury to be the player giving answers - but in this case it's exactly the opposite: the contestant had to implement a strategy for the second player that would always win. Can you see such strategy?

The problems in general turned out a bit too easy, and did not allow to determine the single winner - three competitors solved all of them. Congratulations Scott, Ishraq and Yinzhan! (Scott did stand out by achieving the perfect score just 2 hours into the first day and just 3 hours into the second day)

On the weekend, Codeforces Round 257 gathered a big crowd of 3000+ participants (problems, results, top 5 on the left). Congratulations to semiexp on the victory!

Thanks for reading, and check back next week!

Tweet