Two player game:
Given two numbers x and m. Grid is built in the following fashion:
x x+1 x+2 … x+m-1
x+1 x+2 x+3 … x+m
...........
...........
x+m-1 x+m x+m+1 … x+2m-2
Each cell is a pile and the value in each cell is the number of stones in that pile. Alice and Bob are playing the game. In each turn, a player removes any non-zero number of stones from any one pile. Game ends when all the piles become empty. Last player to make a move wins. Both of them play optimally. Alice starts the game. You have to tell who the winner will be.
Constraints:
1 <= T <= 10^5
0 <= x,m <= 10^18
I liked this question.
My approach - It is similar to game of nim. So the xor of all the values will give the answer. Apart from the diagonal the rest of the values will get cancelled( The upper triangle and the lower triangle). So we are left with the diagonal.
Pattern of diagonal is x, x + 2, x + 4 … x + 2 * m - 2
As an extension of the xor of a range of numbers we can obtain the result of the about series.
Let f(x) where x is an even number, be xor of numbers (0, 2, 4…x)
ar = {x, 2, x + 2, 0};
f(x) = ar[(x / 2) % 4]
for even x : ans would be f(x + 2 * m - 2) ^ f(x - 2)
for odd x : All the numbers in the series will have 1 as the least significant bit. We will scrape it off. therefore x = x - 1. Then we will obtain the result as x is even now. If m is odd we will add 1 to the answer.
I hope this is correct.
I also have a similar approach . Your solution seems correct to me . I think we can use this as one of our easy problems .
Ya. The question is fine. We can use it as one of the easy problems.