G - Generalized Subtraction Game Editorial by en_translator
First of all, you may jump at Grundy’s number if you know it. That is, you can solve this problem if you can find all \(g_1, g_2, \dots, g_n\), where \(g_n\) is the Grundy number when there are only \(n\) consecutive integers on the table. However, this solution costs \(\mathrm{O}(N^2 (R - L))\) time, so we think it is a bit difficult to get AC. (You may solve this way with some optimizations using some properties of this problem.)
This problem features a strategy called the Tweedledum-Tweedledee Strategy. Let’s take the following example:
There are \(2N\) cards numbered \(1, 2, \dots, N\), and \(N+2, N+3, \dots, 2N+1\) on the table. What is the optimal strategy if the game starts with this state?
In the example above, in fact, the second player always wins. Specifically, if the first player chooses \((x, y)\), you make a move \((x+N+1, y)\) or \((x-(N+1), y)\), whichever is valid; then you can always win.
Likewise, in some games, it is good idea to correspond every opponent’s move \(A\) with your move \(A'\) one-to-one, always perform the moves that mimics opponent’s, and win. This is the so-called Tweedledum-Tweedledee Strategy.
This problem can be solved by mimicking strategy in most cases. That is, you may choose to move first and equate the sequence of cards in the first move. This can be achieved by choosing some \(y\) such that \(N \bmod 2 = y \bmod 2\), and choose appropriate \(x\) corresponding to \(y\).
You cannot use the Tweedledum-Tweedledee strategy strategy if \(L = R\) and \(N \bmod 2 \neq L \bmod 2\). In that case, you can solve it by finding the Grundy’s number in a total of \(\mathrm{O}(N^2)\) time.
posted:
last update: