## IPSC 2008

## Solution to Problem G – Game on Words

The problem statement asks us to win the game against our server. A game position is completely determined by
the current string S. For each string we can say if it is winning (i.e. player to move can win the game) or losing
(i.e. player to move will lose the game if his opponent plays optimally).

Standard reasoning from the combinatorial game theory can be applied:

We say that the position represented by a string S is winning if there is a letter α such that string Sα is a
valid string (not in the wordlist, but a prefix of some word in the wordlist) and the position Sα is losing. It
means that the current player can force his opponent into a losing position.

We say that a position S is losing if for each letter α the string Sα is either an invalid string (it is in the
wordlist or it is not a prefix of any word in the wordlist), or the position Sα is winning. It means that
the current player is forced to immediately lose the game or to create a winning position for his
opponent.

This recursive definition is valid because the game is finite – its length is bounded by the longest word in the
wordlist.

We are only interested in positions that correspond to prefixes of words in the wordlist. A conceptually nice
way how to compute which of them are winning is to insert all the words in the wordlist into a trie. The vertices
of the trie then correspond to all the positions in the game that interest us. We can compute which ones are
winning for example using a DFS traversal of the trie. (This directly corresponds to simply applying the
recursive definition mentioned above.)

To solve the hard test case we have to play in such a way that minimizes the length of gameplay (otherwise
you will hit he submission limit). To do this, we can extend the above definition. For each position we will
compute the number of moves remaining, given that the winning player tries to minimize, and the losing player
tries to maximize it.

Implementation of this idea leads to an algorithm which uses time proportional to size of the
wordlist for precomputation, and constant time to determine the optimal move for a given position.
A simpler implementation without the trie, representing each position simply by its string, was
sufficient.