PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Utkarsh Gupta
Tester: Satyam, Jatin Garg
Editorialist: Devendra Singh
DIFFICULTY:
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];
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()
{
// Version 2
int n=readInt(2,100000,'\n');
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)
A[i]=readInt(1,1000000000,'\n');
else
A[i]=readInt(1,1000000000,' ');
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);
int T=readInt(1,1000,'\n');
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); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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();
}