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.

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

"...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 ?..."Sorry, I am not too sure about your explanation. I do not understand this part:

"

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!

3(may be move to f[0]=2, f[1]=0, f[2]=1, minimal non-negative which absent is 3)g[suffix],g[1],g[2],g[3],...,g[x-1]}g[suffix], 0,1,2,..,x-2}inductive assumption))Case:1::(g[suffix] >= x)Case:2::(g[suffix] < x)20,7[[[Here , we need to think inductively, that is assume g[x] = x, if x > g[suffix] ]]]note the changeg[suffix]= 7)0 to 19is there ...g[20] = 20.g[suffix])Keyto get to the solution.why g[x]=x-1 ?