SPLITORDEC - Editorial

[iceknight1093]

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: utkarsh_25dec
Testers: tabr, iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Sprague-Grundy and elementary game theory (optional)

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.

What about the other cases?
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];
vector <int> adj[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 readString(int l,int r,char endd){
    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){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
int sumN=0;
void solve()
{
    int n=readInt(1,100000,'\n');
    sumN+=n;
    assert(sumN<=300000);
    int A[n+1];
    int even=0,one=0;
    for(int i=1;i<=n;i++)
    {
        if(i==n)
            A[i]=readInt(1,1000000000,'\n');
        else
            A[i]=readInt(1,1000000000,' ');
        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);
    int T=readInt(1,1000,'\n');
    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;
    }

    string readOne() {
        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);
        string res = readOne();
        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);
        int res = stoi(readOne());
        assert(minv <= res);
        assert(res <= maxv);
        return res;
    }

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

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

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

    void readEof() {
        assert((int) buffer.size() == pos);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    input_checker in;
    int tt = in.readInt(1, 1000);
    in.readEoln();
    int sn = 0;
    while (tt--) {
        int n = in.readInt(1, 1e5);
        in.readEoln();
        sn += n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            a[i] = in.readInt(1, 1e9);
            (i == n - 1 ? in.readEoln() : in.readSpace());
        }
        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);
    in.readEof();
    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')

[mukul_rawat24]

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

[iceknight1093]

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).

[mukul_rawat24]

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.

[iceknight1093]

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,

@cp-algo

To calculate the Grundy value of a given state you need to:

• Get all possible transitions from this state
• Each transition can lead to a sum of independent games (one game in the degenerate case). Calculate the Grundy value for each independent game and xor-sum them. Of course xor does nothing if there is just one game.
• After we calculated Grundy values for each transition we find the state’s value as the
  \text{mex} of these numbers.
• If the value is zero, then the current state is losing, otherwise it is winning.

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.

[debk]

“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.

[iceknight1093]

@debk

Chef may choose not to win!

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.

@debk

Chef/Chefina may perform consecutive operation on the same pile.

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.

[debk]

@iceknight1093

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

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

@iceknight1093

If Chef plays a losing move on a pile, Chefina will play the winning move on that pile.

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

[mukul_rawat24]

Thanks I got it.

[iceknight1093]

@debk

Cheffina can only win piles which she starts as far I understand

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.

@debk

My doubt was what if Chef plays two consecutive moves on the same 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.

[debk]

Thanks for providing the notes, that will help.