BIGPIZA - Editorial

PROBLEM LINKS

Practice
Contest

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 ) :slight_smile: }

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

1 Like

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???

http://www.codechef.com/viewsolution/6400269

can anyone please explain me the solution without using the grundy number.

initially I feared of grundy number and so asked someone to explain about it.
But now I have learnt about it, this is really powerful tool in gametheory.

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 sub-games 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.