This week in competitive programming

There were no big online contests this week, but the last and strongest European ACM ICPC regional, the NEERC, happened on Sunday (problems, results, online mirror results, top 5 on the left). The two favourites, SPb ITMO 1 and Moscow SU Tapirs, did not disappoint - congratulations!

I've set problem G together with pashka. You can find the full statement on page 9 of the PDF, but the general idea was that you had to write a program that would always win as the second player in Gomoku against a pretty weak strategy. Of course, since the first player has a guaranteed win in this game, the strategy you're playing against has to be weak. More precisely, the strategy considered all possible moves, and evaluated the resulting position for each move, picking the move that leads to the best position modulo some random noise. When evaluating a position, the strategy considered each horizontal, vertical and diagonal of five cells, and tried to minimize the number of such rows where the other player has four marks and it had none. To break ties, it tried to maximize the number of such rows where it had four marks and the other player had none. To break ties again, it tried to minimize the number of rows where the other player had three marks and it had none, and so on.

The ITMO 1 team made the biggest progress in this problem, creating a strategy that won about 95% of the games. However, you had to win 100 games in order to get this problem accepted, and the chance of that was around 0.5%, and they didn't get so lucky. Here are three short videos: ITMO 1 winning a game, ITMO 1 losing a game, and the reference solution - spoiler alert! - winning a game (in all cases the contestant's strategy is playing blue circles):

    

I've also enjoyed problem E a lot - see the full statement on page 7 of the PDF. It was also centered around a game, this time a much simpler one: Rock-paper-scissors. You were given a description of a finite-state machine where each state has one move associated with it (rock, paper or scissors), and three transitions corresponding to three possible moves of the opponent. The initial state of that machine was unknown. You had to create another finite-state machine in the same format that would beat the first machine at least 99% times in the long run, irrespective of the first machine's initial state.

Can you see how to do it? How many states does your machine need in the worst case if the input machine has N states? Can you prove that such number of states is asymptotically minimal? Can you see a simple randomized solution with the same number of states?

You can try to submit those two problems, as well as 9 others, at the online mirror.

All other European regionals are also over by now: the SEERC (problems, results), the CERC (problems, results, Russian training camp mirror results), the SWERC (problems, results, online mirror results), and the NWERC (problems, results, online mirror results). Congratulations to Lviv NU Penguins, University of Zagreb, UPC 1 and University of Copenhagen Lambdabamserne on the victories! The intersection between different online mirrors is rather small, but the general feeling is that the two top NEERC teams are the strongest in Europe this season.

Thanks for reading, and check back next week!