How to solve this .. please suggest.

This is from past hackerearth challenge.That is not live.Please help me to solve this. I tried a lot but could not solve.

Rahul and Rashi are bored with playing the game of Nim, particularly after Rahul gained a thorough understanding of game theory, and would always win.

Now, they are going to play on a variation. 
There are only 2 piles of coins. Each player can make the following move:

Pick K ( ≥ 1) coins from pile 1.
Pick K ( ≥ 1) coins from pile 2.
Pick K ( ≥ 1) coins from pile 1 as well as pile 2.
As with the older version, the person unable to make a move shall lose. Can you help analyse this game for the novice, Rashi.

Input Format:

The first line contains an integer T, denoting the number of test cases to follow.
The next T lines each contain two integers N1 and N2, separated by a single space, denoting sizes of first pile and second pile respectively.

Output Format:

The output file should contain exactly T lines.
Output Play, if Rashi would win as the first player and Don't Play, if she shall lose.


1 ≤ T ≤ 105
0 ≤ N1, N2 ≤ 106

Sample Input (Plaintext Link)
1 1
0 2
1 2
Sample Output (Plaintext Link)
Don't Play
1 Like

@anu1234 Here you go, It’s gonna be a little long answer, but try being patient you’ll get the answer in the end :stuck_out_tongue: There are two kinds of positions, winning and losing. To find whether a position {i,j} is winning or loosing, we draw a 2-D grid. All configuration of the form {i,i} or {0,i} or {i,0} are winning positions and we mark them in the grid. Initially, the grid looks like

'*' indicates yet to be determined.
'L' indicates a loosing position.
'W' indicates a winning position.

L W W W W W W...
W W * * * * * * * .......
W * W * * * * * * .......
W *  * W * * * * *.......
W *  *  * W * * * *......
W *  *   *  * W * * ......
Considering 0 based indexing in the grid, position i,j in the grid indicates the configuration {i,j} of the game (i remaining in H1 and j remaining in H2). 

Consider any losing position say {1,2}(it can be easily seen that 1,2 is a losing position), then all those positions from which we can move to (1,2) are winning positions because we know the player that plays the move on reaching (1,2) will surely lose. Is this clear?(If not, you may ask in the comment).
Thus, for this losing position, all points in the grid of the form:

Winning positions:
(1+i,2+i)-> we can reach (1,2) by taking i from each heap
(1+i,2) -> take i from 1st heap will lead to config. (1,2)
(1,2+i)  -> taking i from second heap will lead to configuration (1,2)
Similarly, (2,1) is also a losing move and thus (2+i,1+i)(2,1+i)(2+i,1) are  winning positions.

Now, we can easily see here that if we know one losing move, we can get all other winning positions possible from this move and mark them as W in the grid. How, our grid will look like can be seen here. This, was just the tutorial mentioned in short.

As mentioned, The problem is standard Wythoff’s game and the standard solution with good space and time optimization is here: The strategy of the game revolves around cold positions(losing ones) and hot positions(winning ones). Our main objective is just to determine which positions are hot and which are cold :P. This classification can be done this way, (from wiki):

1.) (0,0) is a cold position.
2.) Any position from which a cold position can be reached in a single move is a hot position.
3.) If every move leads to a hot position, then a position is cold.

We already know all configurations of the form (0,i) or (i,0) or (i,i) are winning positions. Some of the cold positions are: (0,0) (1,2), (3,5) etc… These configurations represented by say (n,m) form a regular pattern which is determined this way: let (nk, mk) be the k’th cold position. Then, all such cold positions form the Beatty sequences. In short it is the sequence of integers formed by the taking the floor value of positive multiples of the given irrational numbers. We’ll however, be dealing with integers here.

So, far so good I suppose, have patience :).

Specifically, if K is any natural number, then

nk= k*(golden ratio)
and mk= nk +k

or more clearly, if we take nk to be some value i, then mk is (i+k).
and this is generated using the following code:

int k=0;   // start with the losing state (0,0) and assuming we are finding k'th losing state
for(int i=0; (i+d)<=MAX;i++)
  if(!used[i] && !used[i+k]) 
    cout<<"losing state : "<<i<<" "<<i+d<<endl;
    used[i+k]=1;  // mark the move as used 

What the above code does is, we start with some initial losing state (0,0). In the configuration (nk, mk, i in the above code refers to nk and (i+k) refers to mk. Recall the above wiki lines which told how the cold positions look like. Why are we marking the states as used? This is because, lets say we have the losing state (2,1), the next possible state without the use could have been (2,4)( i=2 and d=2) but we can reach the state (2,1) by taking 3 coins from heap2. Thus, this state is the winning state. This is actually the interpretation of the second points of the above wiki lines (“Any position from which a cold position can be reached in a single move is a hot position.”).

Now, we have all states which are losing and which are winning, we can judge who’ll be the winner in just constant time look-up. For fully working code, you may refer this.
(PS: This is not my code, my code was a brute force one, i’ll post here if you want, just let me know, I was looking several codes of this hackerearth problem when I went across this, and then the whole concept, but i just accidently forgot to take note of the person who’s code is this. I’d have opted to give you credits here :), thanks a lot man!! :slight_smile:

I tried my best explaining, any faults or comments are most welcomed.

Thanks, for reading such long and being patient :slight_smile:

1 Like

Nice explanation…damn_!!!

1 Like

nic explanation