×

# HELP : Game Theory / Grundy Number

 0 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: 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]; }  } 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. asked 19 Mar '14, 18:46 2★codemex 1●1●2 accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×323
×140
×56
×13

question asked: 19 Mar '14, 18:46

question was seen: 1,746 times

last updated: 20 Jun '16, 03:51