 # GAMEOFPILES2-Editorial

Setter: Utkarsh Gupta
Tester: Satyam, Jatin Garg
Editorialist: Devendra Singh

1905

# PREREQUISITES:

Basics of Game Theory, Game of Piles 1

# PROBLEM:

There are N piles where the i^{th} pile consists of A_i stones.

Chef and Chefina are playing a game taking alternate turns with Chef starting first.
In his/her turn, a player can choose any non-empty pile and remove exactly 1 stone from it.

The game ends when exactly 2 piles become empty. The player who made the last move wins.
Determine the winner if both players play optimally.

# EXPLANATION:

Let sum represent the total number of stones in all the N piles and ones and twos represent the total number of piles having exactly 1 and 2 stones respectively.
The problem can now be solved by dividing it into three cases:
Case 1 : There are at least two piles which have exactly 1 stone each.
Removing a stone from a pile that contains exactly 1 stone is a definite losing move as the opponent can then remove a stone from another pile that contains 1 stone and win the game. Therefore the players will keep removing stones until all piles contain exactly 1 stone each.
\therefore if\: sum - N is odd the winner is Chef otherwise Chefina;
Case 2 : There is exactly one pile that contains exactly 1 stone.
If the sum is odd chef can remove a stone from pile that contains a single stone. Now the game reduces to Game of Piles 1 with N-1 remaining piles where the game ends when exactly one pile becomes empty and Chefina starts first and Chef wins when sum-1 is even or sum is odd. If the sum is even but there is a pile which contains exactly 2 stones then chef can remove a stone from that pile (this now reduces to case 1) and win the game if sum-1-N is even or sum-N is odd otherwise removing a stone from the pile containing 1 stone or 2 stones becomes a losing move for chef. Chefina can remove a stone from the pile containing 1 stone in the next move and win the game by applying the same strategy after that as in Game of piles 1.
\therefore if\: sum is odd or twos\geq 1 and sum-N is odd then the winner is Chef otherwise Chefina.
Case 3 : There is no pile that contains exactly 1 stone.
The parity of sum becomes same as original after every move made by Chefina and as soon as a pile becomes empty the game is reduced to Game of piles 1 again. If the parity of sum is initially odd the parity of sum when one one pile becomes empty is also odd and chef needs to move first. Therefore from the strategy of Game of piles 1 we have,
if\: sum is odd the winner is Chef otherwise Chefina.

# TIME COMPLEXITY:

O(N) for each test case.

# SOLUTION:

Setter's solution
``````//Utkarsh.25dec
#include <bits/stdc++.h>
#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()
{
// Version 2
sumN+=n;
assert(sumN<=200000);
long long A[n+1]={0};
ll sum=0;
int cnt=0;
int cnt2=0;
for(int i=1;i<=n;i++)
{
if(i==n)
else
sum+=A[i];
if(A[i]==1)
cnt++;
if(A[i]==2)
cnt2++;
}
// Case 1:
if(cnt==0)
{
if(sum%2==1)
cout<<"CHEF\n";
else
cout<<"CHEFINA\n";
return;
}
// Case 2:
if(cnt>=2)
{
if((sum-n)%2==0)
cout<<"CHEFINA\n";
else
cout<<"CHEF\n";
return;
}
// Case 3:
if(cnt==1)
{
if(sum%2==1)
cout<<"CHEF\n";
else
{
if(cnt2==0)
cout<<"CHEFINA\n";
else
{
if((sum-1-n)%2==0)
cout<<"CHEF\n";
else
cout<<"CHEFINA\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";
}
``````
Editorialist's Solution
``````#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
void sol(void)
{
int n, ones = 0, twos = 0;
ll sum = 0;
cin >> n;
vll v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i];
ones += (v[i] == 1);
twos += (v[i] == 2);
sum += v[i];
}
if (ones > 1)
{
if ((sum - n) & 1)
cout << "CHEF\n";
else
cout << "CHEFINA\n";
}
else if (ones == 1)
{
if (sum & 1)
cout << "CHEF\n";
else
{
if (twos == 0)
cout << "CHEFINA\n";
else if ((sum - n) & 1)
cout << "CHEF\n";
else
cout << "CHEFINA\n";
}
}
else
{
if (sum & 1)
cout << "CHEF\n";
else
cout << "CHEFINA\n";
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}
``````
2 Likes

There is an error in the problem.
for test case 1 2 4 chefina should be the correct output but it gives output as chef

I had a doubt, what if the piles are 1 3 3 4 4?
since sum is odd but sum-N is even, then according to statement 2, it must be player 2 who will win. But 1 3 3 4 4 is otherwise I believe. Am I doing anything wrong? Please elaborate.

x = [1, 2, 4]
In this case, Chef will remove the first stone from x and the problem reduces to finding the winner for x = [2, 4] with Chefina starting the game.
Lets say after some steps played optimally by both of them, x becomes [2, 2]. Chefina will be forced to remove one stone from any pile which will make x = [1, 2] and Chef will now remove 1 stone from x and ends up winning.

I hope I was able to explain it properly.