PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
This 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 ( cut-the-knot 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 sub-games ( 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 non-zero. 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) non-negative 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(N2) solution. Note that the number of test cases are 1000, so you can precompute the grundy values for all possible N, either bottom-up ( dynamic programming ) or top-down ( 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 SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.