We say that a state is "losing" if the current player will lose if the opponent plays optimally, and a state is "winning" if the current player will win if they play optimally.

Subtask 1

Notice that if any move leads from the current state to a losing state, the current state is winning, since we can force the opponent to lose. Similarly, if we all moves from the current state lead to a winning state, the state is losing, since the opponent is guaranteed to win.

Employ a naive recursive approach using a function \(\text{win}(N, K)\) which represents whether or not \(N, K\) is a winning state, with the base case being \(\text{win}(1, K) = \text{false}\). Return true if any of \(\text{win}(N-1, K), \text{win}(N-2, K), \text{...} , \text{win}(N-K, K)\) is a losing state. Otherwise, return false.

Time complexity: \(O(K^N)\)

Subtask 2

The solution for subtask 2 uses a similar approach to subtask 1, but we use memoization to avoid repeated calls of \(\text{win}(N, K)\) by storing the result in an array.

Time complexity: \(O(NK)\)

Subtask 3

Notice that the states follow a cycle. For example, if \(K=3\), the losing positions are \(N=1, 5, 9, 13, \text{... etc}\). In fact, the general formula for a losing position is \(N \equiv 1 \text{ } (\text{mod } K + 1)\). This becomes clear when we take a look at values of the memoization array we used in subtask 2 for various values of \(K\). The reason for this is as follows:

First, we observe that if \(N=1\), the position is losing, since we are forced to take the last stick.

Thus, for \(N=2, 3, 4,..., \text{ or } 1+K\), the position is winning since we can simply remove sticks to leave our opponent with the last stick. However, if \(N=(K+1)+1\), no matter how many sticks we remove, the opponent is left with at least \(2\) sticks and they can simply leave us with the last, and thus it is a losing position.

Using similar logic, if \(N=(K+1)+2, (K+1)+3, (K+1)+4, ..., \text{ or } (K+1)+1+K\), the position is winning, since the player can remove sticks to leave the opponent with \((K+1)+1\) sticks. Thus, \((K+1)+2+K=2(K+1)+1\) is a losing position, since on the opponent's turn, they can always leave the player with \((K+1)+1\) sticks. We can continue this logic forever, arriving at the conclusion that the position \(N=i(K+1)+1, i \in ℤ_{\ge 0}\) is losing. This is equivalent to the general formula shown previously, \(N \equiv 1 \text{ } (\text{mod } K + 1)\).

We have now arrived at quite a simple solution for this problem: evaluate N % (K+1). If N % (K+1) = 1, the first player is not guaranteed to win. Otherwise, the first player is guaranteed to win, provided they play perfectly.

Note: Watch out for integer overflow!

Time complexity: \(O(1)\)