Problem Statement:
On the eve of New Year in Dholakpur, Chota Bheem and Chutki are playing a game, described as follows.
There are two plates full of Laddus. Both can eat L (L>=1) laddus from any one plate or L laddus from both the plates in each step. They play the game alternatively and the last one to eat the laddu will be the winner.
As Chota Bheem wants to impress Chutki, he wants to make Chutki the winner. You have to help Chota Bheem in deciding who should play first.
Constraints:
1 <= Test cases(T) <= 105
0 <= a,b <= 106
As i could only come up with an O(TN2) approach which used O(N2) space(where N is max(a,b)), I wrote a brute force to see if any pattern existed but failed to find one.
What am i missing here ?
Thanks!
P.S : You can find the problem statement here.
Auto comment: topic has been updated by SarvagyaAgarwal (previous revision, new revision, compare).
We have (0,x),(x,0)&(x,x) as winning states. Now refer case (1,2),from here we can end up only at one of the three winning states so this is a losing state . Further any pair (1,x)(or(x,1)) where x>2 is a winning state because given this state you can always push your opponent to (1,2).Any state (2,x) or (x,x+1),x!=1, can also be dealt with in a similar way. Now take next state (3,5)(smaller (3,x)'s have already been evaluated).We see this is a losing state. So (3,x) is losing state only if x=5.This completes job for (5,x) pairs as well(Why?).Notice all pairs of form (x,x+2) also becoming winning (x>3) . So next in turn (this will be the last) is (4,7),Again running, a small brute force ensures this as a losing sate. Pattern? (1,2)-(2,1)| (3,5)-(5,3)| (4,7)-(7,4)| (6,10)-(10,6)| and so on so these are the only losing states for all other pairs,they will be winning states.
Yeah but how to relate these two values ? I can't see a pattern . 3,5 and 4,7 can be thought of as b = 2 * a - 1 but 6,10 can't . I think we need an O(1) formula for this .
You can pre-process and then answer in O(1). here is the code to generate initial "loss pairs". Once this is calculated check ans[x]==y(for inputs x and y),in each test case and answer in O(1).The idea is that each number will have exactly one loss counterpart.
this is the list of losing positions
(0, 0), (1, 2), (3, 5) , (4, 7), (6, 10), (8, 13)...
and their inverses, so the pattern (that could also be seen from the problem directly) is obvios if you take the difference and remember that you cant repeat numbers, and that the next pair has the least possible numbers :). The difference (y — x) are:
0, 1, 2, 3, 4, 5
So I guess the next terms are:
(9, 15), (11, 18), (12, 20), (14, 23)...
and they can in fact be generated with an O(n) program :)
I don't understand how the output of second test case is Chtki?
a=1,b=3
bheem can eat 2 ladoos from second plate. Or is it that both bheem/chutki is correct output?
The first player picks 1 from the second plate. Whatever second player does,he loses. 1. He picks 1 from second plate(1 1 first player wins) 2. He picks 1 from first plate (0 2 first player wins) 3. He picks 1 from both plates (0 1 first player wins) No other move.
If first player picks 1 from 1st plate, he still loses, so why can't bhem go first?
Both play optimally !
I thought bhem wanted to lose -_- .
If bheem wanted to lose he could always go first and take all from any plate :P
That is why I was confused. The statement doesn't say bheem plays to win.
What a nice result :)
How did you get the clue?
I read this. There's hardly any classic game theory problem that isn't discussed in this masterpiece.
Deleted