 # SPLITORDEC - Editorial

Author: utkarsh_25dec
Testers: tabr, iceknight1093
Editorialist: iceknight1093

TBD

# PROBLEM:

Chef and Chefina play a game on N piles of stones.
On their turn, a player either removes one stone from a pile, or splits a pile into two strictly smaller piles.

Chef starts first. Under optimal play, who wins?

# EXPLANATION:

tl;dr

Let x be the number of piles with an even number of stones, and y be the number of piles with exactly one stone.

Chefina wins if and only if both x and y are even.

There are a couple of different ways to come up with a solution to this problem.

Grundy numbers

The ‘easiest’ way (but also the way that requires some knowledge) is to directly apply the Sprague-Grundy theorem and compute Grundy numbers.

It’s clear that each pile is independent, so we can simply compute the grundy number of a single pile, then xor everything together and check whether the final result is non-zero.

Let g(x) denote the grundy number of a pile of x stones.
If you compute grundy numbers for a few small pile sizes using, say, brute-force, you might notice the following pattern:

• g(0) = 0
• g(1)= 1
• For x \geq 1, g(2x) = 2 and g(2x+1) = 0.

This allows us to compute g(x) for any x in \mathcal{O}(1) time, and the problem is immediately solved.

A direct strategy

Let’s first try to solve for a single pile of stones.

• If the pile has 0 stones or 1 stone, the winner is obvious.
• If the pile has a positive even number of stones, Chef can always win by splitting it into two equal-sized piles, and then mirroring Chefina’s moves.
• If the pile has an odd number of stones (and \geq 3), Chef can never win.
• If Chef removes one stone from the pile, it has an even number remaining so Chefina wins with the previous strategy.
• If Chef splits the pile, the one of the resulting piles will be odd and the other even.
• If the odd pile has size \geq 3, Chefina splits the even pile into 2 equal parts and passes the turn to Chef, who again cannot win: he loses on the smaller odd pile recursively, and he loses on the split even piles since Chefina mirrors his moves there.
• If the odd pile has size 1 and the even pile has size 2, Chefina makes the piles (1, 1) and hence wins.
• If the odd pile has size 1 and the even pile has size x\geq 4, Chefina splits the even pile into 1 and x-1. Now if Chef takes one 1 Chefina takes the other; and otherwise Chef has to play on a smaller odd pile which is again losing.

This tells us that on a single pile, Chef wins if it’s either a single stone or even-sized.
Further, Chefina’s winning strategy often relies on mirroring Chef’s moves.

Let’s attempt to generalize this to multiple piles.

• If there’s an even number of 1-stone piles, Chef can win half of them and Chefina wins the other half, so it’s in Chefina’s favor since she’ll make the last move.
• If there’s an even number of even-sized piles, once again they win half each so it’s in Chefina’s favor.

In particular, if there’s an even number of 1-sized piles and an even number of even-sized piles, Chefina will always win.

It turns out that Chef can always win them!

Proof

Suppose there are x piles of size 1 and y of even size.
If (x+y) is odd, it’s obvious that Chef can always win since he has strictly more winning piles.

Now, suppose x and y are both odd.
There’s at least one even-sized pile, so take it; let it have K stones.

• If K = 2, remove one stone from it. This increases x by 1 and decreases y by 1, so they’re both even. It’s Chefina’s turn, so she loses.
• If K \geq 4, split into two piles of sizes (1, K-1). Again, this increases x by 1 and decreases y by 1, so once again x and y both become even and Chefina loses.

# TIME COMPLEXITY

\mathcal{O}(N) per testcase.

# CODE:

Setter's code (C++)
//Utkarsh.25dec
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}

if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}

return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}
int sumN=0;
void solve()
{
sumN+=n;
assert(sumN<=300000);
int A[n+1];
int even=0,one=0;
for(int i=1;i<=n;i++)
{
if(i==n)
else
if(A[i]%2==0)
even++;
if(A[i]==1)
one++;
}
if(even%2==0 && one%2==0)
cout<<"CHEFINA\n";
else
cout<<"CHEF\n";
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
while(T--)
solve();
assert(getchar()==-1);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct input_checker {
string buffer;
int pos;

const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";

input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}

int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}

assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
// cerr << res << endl;
return res;
}

string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}

int readInt(int minv, int maxv) {
assert(minv <= maxv);
assert(minv <= res);
assert(res <= maxv);
return res;
}

long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
assert(minv <= res);
assert(res <= maxv);
return res;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}

assert((int) buffer.size() == pos);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
input_checker in;
int sn = 0;
while (tt--) {
sn += n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
}
int b = 0;
for (int i = 0; i < n; i++) {
if (a[i] == 1) {
b ^= 1;
} else if (a[i] % 2 == 0) {
b ^= 2;
}
}
if (b) {
cout << "CHEF" << '\n';
} else {
cout << "CHEFINA" << '\n';
}
}
assert(sn <= 3e5);
return 0;
}

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
grundy = 0
for x in a:
if x == 1: grundy ^= 1
if x%2 == 0: grundy ^= 2
print('Chef' if grundy > 0 else 'Chefina')

3 Likes

How to prove :-
grundy (2 *x + 1) = 0 and grundy (2 * x) = 2 ?

Use induction.
g(0) and g(1) are trivial, and are base cases.

If x is even, the set whose mex is to be computed includes g(x-1) = 0 and g(1)\oplus g(x-1) = 1.
For 1 \lt i \lt x, we have g(i) \oplus g(x-i) = 0 since i and x-i will have the same parity (and inductively, the same grundy values). The mex of this set is clearly 2, since it contains only 0 and 1.

If x is odd, then the set you compute includes g(x-1) (which is 2 inductively) and every g(i)\oplus g(x-i) for 1 \leq i \lt x.
i and x-i have different parities, so their grundy values are never equal (again, inductively). In particular, g(i)\oplus g(x-i) will be non-zero.
This means you’re computing the mex of a set that doesn’t contain 0, of course it has mex 0.

g(2k + 1) = 0 can also be seen differently (see the “direct strategy” section of the editorial, where I give Chefina a winning strategy for when the pile size is odd).

One question I have .
There are two cases for n > 1.
A. Find Grundy (n-1)
B. Split n in two sets

When we’re calculating Grundy (n) for second case
We’re taking set as :-

{ ( g(x-i) xor g(i) ) U ( g(x-i-1) xor g(i+1) ) … }

I’m confused when we need to take xor and when to take union . Can you explain in which case one need to be apply when calculating Grundy numbers.

I feel like you’re not quite familiar enough with grundy numbers, because the xor part and the union part are both necessary and completely different: you xor integers and union sets.
I recommend going through the cp-algorithms blog linked in the prereqs, because your question is answered there.

To quote the relevant part,

Applying this to our case, a state is a pile with x stones.
We need to consider every possible move from this state, and put the grundy numbers of them all into a set (“union”), after which we compute the mex of the resulting set.

Making a move might result in a state with more than one pile (in our case, it’ll be two piles), and they’re all independent. So, to calculate its grundy number we need to take the xor of the grundy numbers of the resulting piles.

“If there’s an even number of even-sized piles, once again they win half each so it’s in Chefina’s favor.”

This part is not clear to me. Chef may choose not to win! [eg. 2 → 1(Chef) → 1(Chefina)] Also, Chef/Chefina may perform consecutive operation on the same pile.

If a player wins a pile, they perform the final move on it (in particular, it means they always have a move to make, so they aren’t losing the game as a whole by winning that pile).

If Chef chooses to lose a pile, then Chefina has even more winning piles; so she can never lose anyway.

Doesn’t matter whether they do or don’t, the piles are completely independent.
If Chef plays a winning move on one pile, Chefina plays a winning move on another pile (which will always exist in the cases that Chefina wins).
If Chef plays a losing move on a pile, Chefina will play the winning move on that pile.
It doesn’t matter if they make 5 moves on one pile, then switch to a different one and make 7, then switch again and …

The notion of independence is quite important in games like this, so try to get used to it.

Yes, but I don’t understand how? Cheffina can only win piles which she starts as far I understand.

My doubt was what if Chef plays two consecutive moves on the same pile?

Thanks I got it.

Not true! You gave a counterexample yourself, where Chef starts a pile but then loses it (with non-optimal play).
It really doesn’t matter who started a pile, the only thing that matters is its current state: is it winning or losing?

I think it’s easier to understand if you take an example.
Suppose there are two piles of even size.
Chef decides to play a winning move on, say, the first.
Then Chefina will play a winning move on the second.

Now, no matter what happens to the rest of the game, Chefina can guarantee that she will win either the first pile or the second pile, because they’re both in a losing state now.
Chef must play a move on one of them, which is losing by definition of it being a losing state and so Chefina will have a winning move on that pile.

Same thing, doesn’t matter because of independence.

My impression is that you haven’t fully grasped how winning and losing states in a game work exactly.
Unfortunately, this isn’t the easiest problem to learn that, because while I gave a strategy, the reality is that a formal proof of why this strategy works kinda depends on the Sprague-Grundy theorem and more generally the fact that the piles are independent (which is a staple of many game theory problems).
It’s unfortunately not always possible to nicely describe a simple strategy for a game (even for a game as ‘simple’ as nim), so grundy numbers are quite important and useful.

I recommend studying the cp-algorithms blog linked in the prerequisites; and maybe some other sources too like this pdf.

1 Like

Thanks for providing the notes, that will help.