Zarg's blog

Help with problem on Game Theory
By Zarg, 11 years ago, In English

http://www.spoj.com/problems/MATGAME/

I have been trying to solve this problem on spoj. I calculated grundy number for every row and than took their xor. I am getting wrong answer but am unable to find an error.

int ex = 0;
for(int i = 0; i < n; i ++)
{
    int g = ar[i][m-1];
    for(int j = m-2; j >= 0; j --)
    {
    if(g == 0)
        g = ar[i][j];
    else
        g = ar[i][j] - 1;
    }
    ex = ex ^ g;
}
if(ex) printf("FIRST\n");
else   printf("SECOND\n");

This is the code. Any help is greatly appreciated.

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

»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

A good discussion on this problem exists here.

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

http://www.codechef.com/problems/SNCK01 Check this link.

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

This part of your code logic is wrong (the else part):

if(g == 0) g = ar[i][j]; else g = ar[i][j] — 1;

The else part in your code is valid only when ar[i][j]<=g

=)

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

    thanks guys.. I got my mistake :)

    As said, computation of g was wrong.

    → Reply