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

Someone Help me in finding the grundy number for the sub-game.
Автор mkagenius, 14 лет назад, По-английски
This is the problem , I was trying to solve:


I think , that each row  should be treated as a sub-game.
And we need to find a grundy-value for each row and then we need to Xor the values to get the result.

The problem I am facing is that I am not able to extract the grundy number from each sub game. 
Your Help will be highly appreciated.
Thanks.


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

14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
you want to calculated grundy for each suffix, then grundy-value for suffix will be computed as in the game NIM only g(0) = grundy-value following suffix (grundy-value following for empty suffix is 0).

P.S. sorry for the terrible english...
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
     code line:  ans = arr[j] - (arr[j] <= ans);

    Why this works ?

    whenever arr[j] <= ans , you are subtracting 1. otherwise arr[j] is the grundy-value.
    Why ?
    → Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Just apply the definition. The grundy number of a state is the smallest non-negative number that does not appear in any of the immediate children of the state.

So let F(i,j,k) be the grundy number for the ith row of numbers, and that the leftmost number is on the jth column and it has value k.

then F(i,j,k) = smallest non-negative number that did not appear in F(i,j,p) for 1 <= p < k and F(i,j+1,q) where the value of cell (i,j) = q.

However, this seems too slow, as the function takes N^4 time to compute and there are 1000 testcases. I believe that it can be sped up to N^3 amortised if you check for the smallest non-negative integer for some fixed j and use an array to keep track of the smallest non-negative integer. But as SPOJ seems to be a rather slow server, I am not sure if 125 million iterations will run in time :S
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
duplicate for english version:

you want to calculated grundy for each suffix, then grundy-value for suffix will be computed as in the game NIM only g(0) = grundy-value following suffix (grundy-value following for empty suffix is 0).

→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    "...code line:  ans = arr[j] - (arr[j] <= ans);
    Why this works ?
    whenever arr[j] <= ans , you are subtracting 1. otherwise arr[j] is the grundy-value.
    Why ?..."

    ans is a grundy-value for the following suffix and equal to g(0) for the current suffix. from value x i can move in 0 .. x-1, we need calculate g(arr[j]) which will match the grundy-value for the current suffix. The sequence depends from g(0) only.

    if g(0) = 0 then sequence 0 1 2 3 4 5 6... (numerated from 1).
    1: 1 0 2 3 4 5 6....
    2: 2 0 1 3 4 5 6...
    3: 3 0 1 2 4 5 6...
    ...
    7: 7 0 1 2 3 4 5 6 8 9...

    i.e. for x > g(0) grundy-value equal x, for 0 < x <= g(0) grundy-value equal x-1.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Hi,

      Sorry, I am not too sure about your explanation. I do not understand this part:

      "
      if g(0) = 0 then sequence 0 1 2 3 4 5 6... (numerated from 1).
      1: 1 0 2 3 4 5 6....
      2: 2 0 1 3 4 5 6...
      3: 3 0 1 2 4 5 6...
      ...
      7: 7 0 1 2 3 4 5 6 8 9..."

      May I know what does the sequence mean? Is it the value of each grid on that row? And in your example, are you considering prefixes instead of suffixes? What does the list of numbers at the bottom mean?

      Also, when I thought about the problem a bit more, I thought that the code shouold be:

      ans = arr[j] - (ans > 0);

      However, I tried submitting this and got WA. But I am not too sure where did I make my mistake. Can you help me?

      What I did was that I considered the case with only 1 row and N columns. Then this is identical to the Nim game with N piles, such that we need to finish all the stones on the ith pile before we can remove any stones on the i-1th pile.

      Let S[i] = number of stones on the ith pile.

      Let G[i] = Grundy number of piles of stones from i to N

      Suppose there is only one pile of stones. Then the grundy number of this pile is just the number of stones on that pile.

      Now suppose we want to calculate G[x]. Then we need to consider two cases:

      1) G[x+1] = 0. (Piles x+1 to N is a losing state)

      Then we know G[x] = S[x], since no matter what S[x] is it is a winning state (just remove all stones on that pile).

      2) G[x+1] > 0. (Piles x+1 to N is a winning state)

      Then suppose that S[x] = 1. Then G[x] = 0 as I can only removing one stone and that would lead to winning state for opponent.

      Suppose S[x] = 2. Then G[x] = 1, as I can remove 1 stone and go to S[x] = 1, which is losing state for opponent.

      Suppose S[x] = 3. Then G[x] = 2.

      ...

      Therefore, G[x] = S[x] - 1.

      Do you know what is wrong with my reasoning above? Thanks in advance!

      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        2) G[i+1] > 0, let it be G[i+1]=2
        then f[x] grundy-value for current suffix with x stones in current cell
        f[0] = G[i + 1] = 2
        f[1] = 0 (may be move to f[0]=2)
        f[2] = 1 (f[0]=2, f[1]=0)
        f[3] = 3 (may be move to f[0]=2, f[1]=0, f[2]=1, minimal non-negative which absent is 3)
        f[4] = 4
        ....
        → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        So, The generalized form would be:
        g[x] = smallest value not in the following set.
          ..{g[suffix],g[1],g[2],g[3],...,g[x-1]}
        which is same as ... {g[suffix] , 0,1,2,..,x-2}
        (assuming g[x] = x-1  (inductive assumption))
        Case:1::(g[suffix] >= x)
        so , if g[suffix] >= x  (let, x+k)then,
         g[x] = smallest value not in { x+k , 0 , 1, 2 , ..,x-2}
        so g[x] = x-1.
        (so , our assumption was true.)
        Case:2::(g[suffix] < x)
        so, if g[suffix] < x (let, x-k) then,
        let us see this case with example:
        20,7
        (only one row, last value is 7 and first 20)
        from 20 7.
        we can get to these configuration:
        [[[Here , we need to think inductively, that is assume g[x] = x, if x > g[suffix]  ]]]
        19 7(g[19] = 19)
        18 7(g[18] = 18)
        .....
        8 7 (g(8) = 8)  
        7 7(g[7]=6)  <=====note the change
        6 7(g[6]=5)
        .....
        2 7(g[2]=1)
        1 7(g[1] = 0)
        0 7(g[suffix] = 7)

        so all values from 0 to 19 is there ... g[20] = 20.
        (which is true from induction as we assumed this to come 20 since 20  > g[suffix] )

        ........this is some-what crapy way to describe the solution.
        Please let me know if something is not clear.
        Note: Induction is the Key to get to the solution.

        → Ответить