PROBLEM LINKSDIFFICULTYEASY EXPLANATIONThis problem needs very basic knowledge of Game Theory, particularly Nim and Grundy. If you are not familiar with these terms, you can refer ( TopCoder tutorial on Algorithm Games here ) and for many interactive games online with good introduction, you can refer ( cuttheknot here ). The game here is joining some of the N points on a circle with chords such that, no two chords intersect each other, not even at their end points. Take a game with N points on a circle, if we make one move in this game ( i.e., draw a chord ), then two points are taken by this chord and depending on which two points are selected, the remaining N  2 points are split in to two subgames ( possibly empty ) and more over, they are independent of each other. We have to find the grundy value for the game with N points. A position is losing if the grundy value is zero and it is winning if its nonzero. Grundy value is the minimum excluded value among all the grundy values of the subgames that can be reached from the current game. For a game with N points, let the two subgames formed have X and Y points. All possible (X,Y) nonnegative integer pairs such that X + Y = N  2 can be reached. The low constraint on N ( 2 <= N <= 10000 ) allowed coders to try all possible subgames, leading to a O(N^{2}) solution. Note that the number of test cases are 1000, so you can precompute the grundy values for all possible N, either bottomup ( dynamic programming ) or topdown ( memoization ). You can refer my well commented solution below to understand it better and to see how simple the code is. { I hope Alice & Bob can rest for some time at least in India and Arjuna & Bhima can play games from now on. By the way, they are from the Elephant city ( Hasthinapur ) :) } SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 26 Nov '12, 13:45

hy can you tell me which test case my code is failing. i have matched many test cases myself by running your program on my pc and everything is fine. still it shows WA??? answered 06 Mar '15, 01:19

How come N=9 be a winning position for "Bhima"? Say Arjuna start the game and join the cord such that it gets divided into two subgames with N=3 and N=4. Now both N=3 and N=4 are winning positions for the player who starts. So whichever one part Bhima chooses first(3 or 4) will result in his victory in that part as in the end Arjuna is unable to make any further moves in that part. But now Arjuna will make his move first in the other part which Bhima had not chosen. So in that other part Arjuna will win and eventually will win the game. Please help me out @admin. answered 01 Nov '16, 13:45
