An all-at-once week

Codeforces came back during the June 12 - June 18 week with its Round 419 (problems, results, top 5 on the left, analysis). Only Radewoosh and yutaka1999 could get all problems right, and Radewoosh has booked his (semi-) permanent place on the front page of Codeforces with this victory: he is now in top 10 by rating. Well done!

AtCoder Grand Contest 016 took place on the next day (problems, results, top 5 on the left, analysis, my screencast). It's not as if tourist needs an unusual strategy to win, but he successfully demonstrated that the AtCoder rules actually make it reasonable to withhold submissions until one has a solution for the last problem they intend to submit. As a theory, here's how this strategy might have helped here: maybe Gennady already had all solutions implemented by the 68-th minute, but he saw that I have an incorrect attempt for one of the problems, and he was not sure in his solution for problem D. So he submitted everything else, and started testing the solution for D more thoroughly, as he knew that he'd have five minutes after I solve my last problem to still get the first place. Gennady, is this theory at least remotely close to reality? :)

The hardest problem of the round presented a peculiar combination of dynamic programming and nimbers, one that I don't recall seeing before. You are given an acyclic directed graph with n<=15 vertices and m arcs. Vertices 1 and 2 each contain a chip. Two players take alternating turns, each turn consisting of moving one of the chips along an arc of the graph. The player who can't make a valid move loses. We want to know which player wins if both play optimally. The problem so far would be very simple, of course, so here comes the twist: consider all 2^m subsets of the graph's arcs; for how many of them does the first player win if we keep only the arcs from this subset?

Thanks for reading, and check back soon for the next week's summary!