Блог пользователя SarvagyaAgarwal

Автор SarvagyaAgarwal, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 .

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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++;
      }
      }
      
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Deleted