SarvagyaAgarwal's blog

Need help with Game Theory !
By SarvagyaAgarwal, history, 8 years ago, In English

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.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by SarvagyaAgarwal (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      int ans[maxn];// initialize with 0
int ctr=1;
for(int i=1;i<=maxn;i++)
{
if(ans[i]==0)// not yet calculated
{
ans[i] = i+ctr;
ans[i+ctr]=i;
ctr++;
}
}
      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

What a nice result :)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did you get the clue?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I read this. There's hardly any classic game theory problem that isn't discussed in this masterpiece.

      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Deleted

→ Reply