mkagenius's blog

Someone Help me in finding the grundy number for the sub-game.
By mkagenius, 14 years ago, In English
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.


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

14 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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).

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    "...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.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      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!

      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        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
        ....
        → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        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.

        → Reply