Mantouiqui's blog

Help : Game Theory / Grundy Number
By Mantouiqui, 10 years ago, In English

I am trying to solve this problem : http://www.spoj.com/problems/MATGAME/

I read all the available entries. I can't figure out where is mistake in my code.

Strategy used:

  1. Calculated grundy value for each possible cell entry

void solve() {

grundy[0] = 0;

for(int i = 1; i <= 51; ++i) {

    memset(used, false, sizeof(used));

    int mex = 0;
    for(int j = 1; j <= i; ++j)
        used[grundy[i - j]] = true;

    while(used[mex])
        ++mex;

    grundy[i] = mex;
    for(int j = i + 1; j <= 51; ++j)
        grundy[j] = grundy[i];
}

}

  1. Then for each row calculated it's grundy number and xor-ed them.

int main() {

solve();

int test, n, m, item;                           // n rows, m columns
scanf("%d", &test);

while(test--) {

    scanf("%d%d", &n, &m);                   
    int gr_overall = 0;                        // NIM sum

    for(int i = 0; i < n; ++i) {

        int mex = 1;                          // Tried mex = 0 also gives WA
        memset(used, false, sizeof(used));

        for(int j = 0; j < m; ++j) {
            scanf("%d", &item);
            used[grundy[item]] = true;         // Marking grundy number for each cell
        }

        while(used[mex]) ++mex;                // Calculating minimum value

        gr_overall ^= mex;                     // Calcualting NIM sum

    }

    if(gr_overall) cout << "FIRST" << endl;
    else cout << "SECOND" << endl;

}

return 0;

}

Please help. Thank you.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The way you are calculating the grundy for the row is wrong.

Here is a simple test case your program fails:

1 
1 2 
1 2

In this case the output would be "SECOND", since the first player must remove 1 from the first column and the second player can remove 2 from the second column to win the game, but your program outputs "FIRST".

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    So how to calculate it?? I also tried mex = 0 as start but it is also giving WA.

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

      You have to use the definition of grundy numbers to calculate it.

      The grundy of a position is the mex of the grundy of all reachable positions from the one you are analyzing.

      You can try figuring the way to calculate it using observation. Try calculating it for small cases like:

      1
1 2
1 2

      Position [0]: (1 2) Reachable positions: (0 2)

      Position [1]: (0 2) Reachable positions: (0 1), (0 0)

      Position [2]: (0 1) Reachable positions: (0 0)

      By the definition, the grundy of (0 0) is 0. So the grundy of (0 1) is 1, the grundy of (0 2) is 2 and the grundy of (1 2) is 0.

      Another tip: Try thinking about what happens when you add a new column to the left of a row.

      Calculate the grundy for (0 5), then calculate it for (1 5) and (10 5) and analyze the results .

      → Reply