Official

C - 01 Game Editorial by evima


Let us divide the squares into (maximal) contiguous intervals of empty squares, which we will call components. Since the whole game is the sum of games for respective components, if we find the Grundy number of the game for each component, we can also find the Grundy number of the whole game (and particularly the winner) as their XOR.

It can be proved by induction that the Grundy number of the game for each component is as follows, where \(n\) is the length (that is, the number of empty squares) of that component.

  • If the component is sandwiched between different digits, the Grundy number is \(0\).
  • If the component is sandwiched between equal digits, the Grundy number is \(1\).
  • If the component touches just one digit, the Grundy number is \(n\).
  • If the component does not touch digits, the Grundy number is \(n \bmod 2\).

posted:
last update: