ganesh_6's blog

What is the reason behind the algorithm in solving Nim Sum 2
By ganesh_6, history, 3 years ago, In English

I know Nim Game, Nim Sum (xor sum) and the theorem, lemmas behind that. Also, I solved the https://cses.fi/problemset/task/1730 After solving that, I moved to https://cses.fi/problemset/task/1098 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?

#include<bits/stdc++.h>
using namespace std;

string solve(int n, vector<int> heaps){
    for(int i=0;i<n;i++)
    {
        heaps[i]%=4;
    }
    int xr=0;
    for(int i=0;i<n;i++)
    {
        xr^=heaps[i];
    }
    if(xr)
    {
        return "first";
    }
    else{
        return "second";
    }
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
3 years 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: https://codeforces.net/blog/entry/66040

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

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When you do %4 it isn't changing anything the outcome is still the same. The only difference is that now it becomes just like nim game 1 because everything is below 4 and you can remove 1, 2, or 3. This is essentially nim game 1 where you can remove anything from any pile. Now you can do nim sum just like in nim game 1.

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

    and why is it so that doing %4 does not change the outcome?

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

      Because for one heap multiple of 4 is always losing. All other remainders are winning. When you do mod it gets the smallest number of sticks and doesn't change the remainder. Now it goes back to any old nim sum where you can remove any number of sticks. Check out 11.5.1 of guide to cp.

      → Reply