What is the reason behind the algorithm in solving Nim Sum 2

Правка en2, от ganesh_6, 2022-01-06 18:03:28

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";
    }
}
Теги c++, gametheory, games

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский ganesh_6 2022-01-06 18:03:28 1 (published)
en1 Английский ganesh_6 2022-01-06 18:03:05 987 Initial revision (saved to drafts)