Codeforces 455B - A Lot of Games

Problem Statement:
455B - A Lot of Games

Solution:
An interesting game theory problem. As usual, game theory problems tend to be pretty creative. First of all, we need to build a prefix tree using all the strings, which can be done in \(O(N)\). The root of the tree is an empty string, which is also the initial state of the game. The tree hence represent the graph of valid moves on each state of the game. We want to know, assuming both players play optimally, whether First can force his way to win and also whether he can lose a given game. We can use Sprague Grundy Theorem, but for this particular problem it is not necessary, as we can use a simple dynamic programming reasoning. First denote win[u] and lose[u] as the table which tells us whether the current player who has to move at state u can eventually win or lose. Suppose we want to fill up win[u], we check all states v that is directly pointed by u, and win[u] is only true if and only if there is a state with win[v] which is false. This reasoning also applies for filling up lose[u].