PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Ashley Khoo
Testers: Abhinav Sharma, Venkata Nikhil Medam
Editorialist: Nishank Suresh
DIFFICULTY:
1888
PREREQUISITES:
Nim and the Sprague-Grundy theorem
PROBLEM:
Chef and Cook play a game on an array A, alternating turns with Chef starting first. In one move, the player may choose indices 1 \leq i \lt j \leq N, subtract 1 from A_i, and add 1 to A_j. The player who cannot make a move loses.
Who wins with optimal play?
EXPLANATION:
A couple of observations allow us to reduce the given game to a standard game of nim, whose solution is well-known (and is linked above).
Reduction
For simplicity, let us say that we have N piles of stones, the i-th pile initially having A_i stones.
A move consists of moving a single stone from one pile to a later pile.
Looking at it this way, the movement of each stone is clearly independent, and so corresponds to a separate game.
Now, let’s look at a single stone that is initially at position i. There are N-i possible moves that can be made to its position — add 1, add 2, \ldots, add N-i. As you might notice, this is exactly the same as having a pile of N-i stones and playing a game of nim on it!
This gives us the desired reduction to nim: for each 1 \leq i \leq N, we have A_i piles of N-i stones, and then we simply find the solution to this nim game.
The above reduction to nim creates A_1 + A_2 + \ldots + A_N piles in total, which is too large to store in memory. However, since checking who wins a game of nim depends only on the bitwise XOR-sum of all the piles’ sizes, and we have the property x\oplus x = 0 for any x (\oplus denotes bitwise XOR), we can do the following:
- If A_i is even, it contributes an even number of N-i to the overall XOR-sum. This makes the overall contribution of this position 0.
- If A_i is odd, it contributes an odd number of N-i to the overall XOR-sum. The overall contribution of this position is thus just N-i.
This gives us the final solution: compute the XOR of N-i across all i such that A_i is odd; let this value be X. Chef wins if X is non-zero, and Cook wins otherwise.
TIME COMPLEXITY:
\mathcal{O}(N) per test case.
CODE:
Setter (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n;
int arr[105];
signed main(){
cin.tie(0);
cout.tie(0);
cin.sync_with_stdio(false);
int TC;
cin>>TC;
while (TC--){
cin>>n;
rep(x,1,n+1) cin>>arr[x];
int res=0;
rep(x,1,n+1) if (arr[x]&1) res^=(n-x);
if (res==0) cout<<"Cook"<<endl;
else cout<<"Chef"<<endl;
}
}
Tester (nikhil_medam, C++)
// Tester: Nikhil_Medam
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
int t, n, x;
int32_t main() {
cin >> t;
while(t--) {
cin >> n;
int ans = 0;
for(int i = 1; i <= n; i++) {
cin >> x;
if(x & 1) {
ans ^= (n - i);
}
}
if(ans == 0) {
cout << "Cook" << endl;
}
else {
cout << "Chef" << endl;
}
}
return 0;
}
Editorialist (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
x = 0
for i in range(n):
if a[i]%2 == 1:
x ^= n - 1 - i
print('chef' if x > 0 else 'cook')