ONEORALL - Editorial

PROBLEM LINK:

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

Author: utkarsh_25dec
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

2420

PREREQUISITES:

Observation, careful case analysis

PROBLEM:

Chef and Chefina play a game on N piles of stones, the i-th pile having A_i stones. Chef starts and then they alternate moves.
On their turn, a player can:

  • Remove one stone from a pile; or
  • Remove one stone from every pile
    This can only be done if every pile has at least one stone remaining.

With optimal play, who wins?

EXPLANATION:

When N = 1, each player can only remove one stone at a time.
In this case, clearly Chef will win if and only if A_1 is odd.
This should hint at the fact that parity is potentially important.

Each player has two possible moves: removing one stone, or removing N stones.
Let’s analyze what happens for different parities of N.

Odd N

When N is odd, every move will remove the same parity of stones (since 1 is also odd).

So, if the total number of stones was initially odd,

  • After Chef makes a move, it’ll be even
  • After Chefina makes a move, it’ll be odd

In particular, this means Chefina can never win, since an odd number of stones remaining means that there’s at least one stone remaining; so she certainly can’t be the one making the last move.

Similarly, if the total number of stones was initially even, Chef can never win.

So, when N is odd, Chef wins if the total number of stones is initially odd, and loses otherwise.

Even N

When N is even, removing one stone flips the overall parity, while removing N stones keeps the parity.

As noted in the previous case, if a player can ensure that on their turn there’s an odd number of stones remaining, they will always win.
A little analysis should tell you that this is possible when:

  • The total number of stones is odd; or
  • The smallest pile has odd size

That is, if S = sum(A_i) and M = \min(A_i), then Chef wins if S is odd or M is odd, and loses otherwise.

Proof

We’ll show that if both S and M are even, Chef cannot win.
There are two possibilities:

  • Suppose Chef removes one stone from every pile. Then, since M was even, every pile will still have at least one stone in it.
    So, Chefina can also remove one stone from every pile, and it’s back to Chef’s turn with both S and M still being even.
  • Suppose Chef removes one stone from a single pile. Then,
    • If this was from a pile with M stones, it will now have M-1 stones, and that’s the new minimum.
      Chefina can also remove one stone from this pile to make the new minimum M-2, which is once again even.
    • If this was from a pile with \gt M stones, Chefina is now in a position where the total number of stones is odd but the minimum pile size is still even, being M.
      This means there will still exist a pile with \gt M stones, and Chefina can remove one stone from it without affecting the minimum.
      Once again, it’s Chef’s turn with both the number of stones and minimum pile size being even.

So, when both S and M are even, Chefina can always find a move and hence never loses.

Now for the other cases:

  • If S is odd and M is odd, Chef can remove one stone from a pile of size M. This makes it Chefina’s turn with both S and M now being even, and so she loses.
  • If S is odd and M is even, as noted in Chefina’s strategy above there will exist a pile with \gt M stones, so Chef can remove one from it and hence put Chefina in a losing position.
  • If S is even and M is odd, Chef can remove one stone from every pile. This reduces S by N (and hence maintains its parity) while reducing M by 1 (hence making it even). Once again, Chefina loses.

So, if either S or M are odd, Chef will win. Otherwise, Chefina wins.

Both cases are easily dealt with in \mathcal{O}(N), since we only need to compute the sum and/or minimum of all the A_i.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Author'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 <= 5e5);
    int A[N+1];
    ll total = 0;
    int mini = 1e9;
    for(int i = 1; i <= N; i++)
    {
        if(i==N)
            A[i] = readInt(1, 1000000000, '\n');
        else
            A[i] = readInt(1, 1000000000, ' ');
        total += A[i];
        mini = min(mini, A[i]);
    }
    if(N%2 == 1)
    {
        if(total % 2 == 1)
            cout << "CHEF\n";
        else
            cout << "CHEFINA\n";
        return;
    }
    if(total%2 == 1 || mini%2 == 1)
    {
        cout << "CHEF\n";
        return;
    }
    if(mini%2 == 0)
    {
        cout << "CHEFINA\n";
        return;
    }
}
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,5000,'\n');
    while(T--)
        solve();
    assert(getchar()==-1);
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester's code (Python)
#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);
        }
    }

    string readOne() {
        assert(pos < (int) buffer.size());
        string res;
        while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
            res += buffer[pos];
            pos++;
        }
        return res;
    }

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

    int readInt(int min_val, int max_val) {
        assert(min_val <= max_val);
        int res = stoi(readOne());
        assert(min_val <= res);
        assert(res <= max_val);
        return res;
    }

    long long readLong(long long min_val, long long max_val) {
        assert(min_val <= max_val);
        long long res = stoll(readOne());
        assert(min_val <= res);
        assert(res <= max_val);
        return res;
    }

    vector<int> readInts(int size, int min_val, int max_val) {
        assert(min_val <= max_val);
        vector<int> res(size);
        for (int i = 0; i < size; i++) {
            res[i] = readInt(min_val, max_val);
            if (i != size - 1) {
                readSpace();
            }
        }
        return res;
    }

    vector<long long> readLongs(int size, long long min_val, long long max_val) {
        assert(min_val <= max_val);
        vector<long long> res(size);
        for (int i = 0; i < size; i++) {
            res[i] = readLong(min_val, max_val);
            if (i != size - 1) {
                readSpace();
            }
        }
        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() {
    input_checker in;
    int tt = in.readInt(1, 5000);
    in.readEoln();
    int sn = 0;
    while (tt--) {
        int n = in.readInt(1, 1e5);
        in.readEoln();
        sn += n;
        auto a = in.readInts(n, 1, 1e9);
        in.readEoln();
        sort(a.begin(), a.end());
        long long s = accumulate(a.begin(), a.end(), 0LL);
        if (n % 2 == 1) {
            if (s % 2 == 0) {
                cout << "CHEFINA" << '\n';
            } else {
                cout << "CHEF" << '\n';
            }
        } else {
            if (a[0] % 2 == 1) {
                cout << "CHEF" << '\n';
            } else {
                if (s % 2 == 0) {
                    cout << "CHEFINA" << '\n';
                } else {
                    cout << "CHEF" << '\n';
                }
            }
        }
    }
    cerr << sn << endl;
    assert(sn <= 5e5);
    in.readEof();
    return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    if n%2 == 1:
        print('Chef' if sum(a)%2 == 1 else 'Chefina')
    else:
        S, M = sum(a), min(a)
        print('Chef' if S%2 == 1 or M%2 == 1 else 'Chefina')
1 Like

I also solved with same approach. I tried to solve it initially with grundy numbers with NIM game. But I couldn’t approach the problem with GAME THEORY. Is there a way to solve the problem with Game Theory, rather than using just math ?

The game is impartial so each state surely has an associated grundy number.
I haven’t tried to actually compute them so I’m not aware of there being any nice pattern in them.

That aside, I’d argue that invoking the Sprague-Grundy theorem is way more mathy than the elementary casework I presented :slightly_smiling_face:

1 Like

You can compute the Grundy numbers inductively, in a similar way to figuring out who wins the game.

If N is odd, all moves change the overall parity of the number of stones, so the Grundy number is the same as the parity, that is, 0 for even parity and 1 for odd parity.

If N is even, the position can be characterized by the ordered pair (M,P) of the minimum pile size M and the overall parity P (0 or 1). If M=0, all moves change the parity, so the Grundy number is the same as the parity. Otherwise, from each (M,P) position there are always moves to (M-1,0) and (M-1,1); there is always a move from (M,1) to (M,0); and, unless all piles are of size M, there is always a move from (M, 0) to (M, 1). Working from smaller to larger M, you can see that the Grundy number of (M, P) is P if M is even, or P+2 if M is odd.

4 Likes

for an hour i thought we could remove any number of stones from a single block or 1 stone from each block!!!