ganesh_6's blog

By ganesh_6, history, 15 months ago, In English

I know Nim Game, Nim Sum (xor sum) and the theorem, lemmas behind that. Also, I solved the After solving that, I moved to I could not figure out the solution. So, I found one solution online and could not figure out the nuances behind the working of the algorithm. I can see that he has used a[i]%4 which is used for one pile game to find out the winner. However, in this case he combined Nim Game 1 algorithm and 1 pile game algorithm to derive the solution. Please explain the reason behind working of this?

using namespace std;

string solve(int n, vector<int> heaps){
    for(int i=0;i<n;i++)
    int xr=0;
    for(int i=0;i<n;i++)
        return "first";
        return "second";
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

tl;dr: The terms for you to google are Grundy numbers and the Sprague-Grundy theorem.

I wrote a blog explaining this a few years ago:

Jump to "Extension on Nim and Grundy Numbers"

I do intend to rewrite this blog sometime this year since my college-level writing is not the best. But if you find it unsatisfactory, you can just google for other articles using the above keywords