PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
This one is a typical algorithmic game theory problem. Those who are not familiar with this topic may read this excellent tutorial on topcoder. We can solve this using basic Grundy and NIM theory. We can pre-compute the grundy values of all possible states the game can be in and then for each testcase, xor the corresponding grundy values and if the result is non-zero, Nancy ( first player ) wins, else Zeta wins. First thing to note is, K ≤ N, as allowing a player to remove more stones than actually present is useless, so K = minimum(N,K). Let G(N,K) be the grundy value of the state where N stones are present in the pile and at most K stones can be removed. If we remove 1 ≤ p ≤ K stones in this step, the resultant state is G(N-p,p). We have the following recurrence,
G(N,K) = mex{ G(N-1,1), G(N-2,2), G(N-3,3), . . . , G(N-K,K) }
But this doesn’t look good, as it may take O(N) time to find each of the all N2 grundy values, leading to O(N3) time. If you visualize this on the grid, G(N,K) and G(N+1,K) are closely related.
G(N,K+1) = mex{ G(N-1,1), G(N-2,2), G(N-3,3), . . . , G(N-K,K), G(N-K-1,K+1) }, depends on just one more additional value than G(N,K).
We can find the grundy values of each row of G by maintaing the same boolean visited array and values may only increase as we move left to right. This can be done in O(N) time per row, so the overall complexity is O(N*N). Draw a grid on paper and see how this works.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.