CCGAME - Editorial

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')
4 Likes

6 posts were merged into an existing topic: Updates on curtailing plagiarism

can someone explain to me, that if the second person is playing optimally why can’t he just choose to make the opposite of the first player’s move resulting in infinite draw match? I mean there is nothing mentioned that it can result in an infinite draw.

1 Like

Because of the condition 1 <= i < j <= n , it does’nt allows i to be j in the next move and vice-versa ( i.e. j to be i ).

3 Likes

Opposite is not applicable here due to this condition { 1 <= i < j <= n }

example :
Range → 1, 2, 3…(10==N)

if A chooses (4 as i) & (7 as j) for operation,
satisfies above condition { 1 <= 4 < 7 <= n }

then,
if B reverse chooses (7 as i) & (4 as j) for operation,
doesn’t satisfies above condition { 1 <= 7 < 4 <= n }

Hope you got it…!!

3 Likes

Thanks man, didn’t even notice a subtle line that explained it all.

1 Like

Hey I read about the sprague-grundy theorem and I understood why the state is winning if the xor sum of that state is non-zero by induction. But in that explanation the problem was kind of different like a player will choose the ith pile and can remove the positive stones from that pile but he didn’t add any stones in other pile like this question. So how can we model this problem to handle scenario of adding stones to another pile after removing from one pile and also in cp-algorithm explanation, a player can remove multiple stones and here we can remove only one stone at a time so I am confused. Please if anyone can just give some intuition about how to model this problem it will really help.

2 Likes

Let’s take one stone from some pile let’s say we take from the ith pile and call it StoneA. This stone can be shifted to i+1th pile or i+2 pile … nth pile. This simulation can be treated as a nim game. (How?) The stone which we considered earlier has n-i choices for piles where it can shift (i+1th pile to nth pile).
So let’s represent the n-i choices as stones and shifting the StoneA by one pile(in the original pile) is equivalent to removing 1 stone from the pile of moves that we just considered! And we can remove only n-i stones which satisfy the condition that the StoneA can be moved by n-i steps.
This stone movement is independent of any other stone’s movement(so a subgame). Hence each stone movement can be represented by a nim game internally based on moves. To get the final result we Xor all the subgames to get the result of the final game.
If A[i] is odd every stone in this pile has the same internal nim game so instead of doing (result^(n-i) A[i] times we can simply do (result^(n-i)) as an even number of (n-i) will get canceled due to Xor.
If A[i] is even as stated above it is result^0.

(Please correct me if I’m wrong)
Happy Coding!

6 Likes

if A[i]=10 and n-i=5…then how
overall contribution of this position 0??

Understood. You’re brilliant!! This should have been a part of the editorial solution!

1 Like

If A[i] is odd every stone in this pile has the same internal nim game so instead of doing (result^(n-i) A[i] times we can simply do (result^(n-i)) as an even number of (n-i) will get canceled due to Xor.
If A[i] is even as stated above it is result^0.

can you explain this part more details!!
thank you

Look at pile i → it has A[i] stones each stone is having his own nim game going on. This means we have A[i] columns of n - i piles each which can be solved by xoring as per the original nim game solution. easy to check if A[i] is even we are simply xoring n - i even number of times n-i ^ n - i is 0. so unless A[i] is odd lets not waste our time. The thing i learned is that the final answer will depend on the xor of all these small nim game results!!!

Please please correct me if i understood this wrong!

Look at pile i → it has A[i] stones each stone is having his own nim game going on. This means we have A[i] columns of n - i piles each which can be solved by xoring as per the original nim game solution. easy to check if A[i] is even we are simply xoring n - i even number of times n-i ^ n - i is 0. so unless A[i] is odd lets not waste our time. The thing i learned is that the final answer will depend on the xor of all these small nim game results!!!

Please please correct me if i understood this wrong!

can someone explain it in simple terms. I did not understand how this problem is transformed into standard nim game ?