Official

C - Zero XOR Editorial by evima

Table of contents

  1. Intended solution
  2. Proof
  3. Hints for coming up with the solution
  4. Sample Codes


1. Intended solution

The answer can be found by a case-by-case analysis as follows. (See 2. Proof for the proof.)

If \(N\) is odd:

The first player always wins.

If \(N\) is even:

First player wins if (s)he can make the XOR of the cookies remaining on the desk \(0\). Otherwise, the second player wins (☆).

In other words, let \(v = A_1 \ \text{XOR} \ A_2 \ \text{XOR} \ \cdots \ \text{XOR} \ A_N\). If one of \(A_1, A_2, \cdots, A_N\) is equal to \(v\), the first player wins. Otherwise, the second player wins (★). See the section 1.2 for the validity of this rephrasing.

Therefore, the following program solves the problem. Note that, when \(N\) is even, a naive check using ☆ takes \(O(N^2)\) time and is too slow, so we need to use ★.

#include <iostream>
using namespace std;

int N, A[400009];
int v = 0;

int main() {
	// Step #1. Input
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];
	
	// Step #2. Compute A[1] xor A[2] xor ... xor A[N]
	for (int i = 1; i <= N; i++) v ^= A[i];

	// Step #3. Branching and output
	if (N % 2 == 1) {
		cout << "Win" << endl;
	}
	else {
		bool winning = false;
		for (int i = 1; i <= N; i++) {
			if (A[i] == v) winning = true;
		}
		if (winning == true) cout << "Win" << endl;
		else cout << "Lose" << endl;
	}
	return 0;
}


1.2. Why ☆ and ★ are equivalent

It follows from \(a \ \text{XOR} \ x \ \text{XOR} \ x = a\), where \(a\) is the XOR of the cookies other than the \(i\)-th one, and \(x\) is the \(i\)-th cookie. The figure below illustrates this relationship.

※ The properties of XOR make \(a \ \text{XOR} \ x \ \text{XOR} \ x = a\) hold for general non-negative integers \(a\) and \(x\), too.


2. Proof

The validity of the intended solution can be proved as follows.


Step 1: Does the game end in two moves?

We can prove that the game never ends in exactly two moves when \(N\) is odd, from the reason below.

Here, the game is said to end in two moves when, following the first move by the first player, the second player plays a move that makes the XOR \(0\) and wins.

For the game to end in two moves, it is necessary that the following condition holds.

  • For every \(i\) \((1 \leq i \leq N)\), there is a way for the second player to make the XOR \(0\) after the first player takes the \(i\)-th cookie. (◆)

Assume that ◆ holds, and the XOR of the remaining cookies becomes \(0\) when the first player takes the \(i\)-th cookie and then the second player takes the \(P_i\)-th cookie \((i \neq P_i)\). Then, from the properties of XOR, the XOR of the remaining cookies will also become \(0\) when the first player takes the \(P_i\)-th cookie and the second takes the \(i\)-th.

This holds for all \(i\) \((1 \leq i \leq N)\), so there should be \(N/2\) pairs of form \((i, P_i)\). However, since \(N\) is odd, at least one cookie must be left over (see the figure below). Therefore, ◆ does not hold, and the game never ends in two moves.


Step 2: When \(N\) is odd

To begin with, consider the case \(N=7\). From the property seen in Step 1, we can prove that the first player always wins.

  • When there are \(7\) cookies, the first player can win with the next move, or (s)he will get another turn with \(5\) cookies remaining.
    • When there are \(5\) cookies, the first player can win with the next move, or (s)he will get another turn with \(3\) cookies remaining.
    • When there are \(3\) cookies, the first player can win with the next move, or (s)he will get another turn with \(1\) cookie remaining.
    • When there is \(1\) cookie, the first player can win with the next move. Therefore, the first player always wins.

The case with a general odd \(N\) can be proved similarly: after repeatedly applying the property, there will be eventually one cookie, where the first player wins.


Step 3: When \(N\) is even

In this case, if the first player cannot end the game with the first move, the second player will be in the same situation as the one in Step 2.

Thus, unless the first player can win in the first turn, the second player wins.


3. Hints for coming up with the solution

It is pretty hard to derive the solution above and prove it. However, in these contests, you can get the score by getting AC, even without proving it. It may be helpful to do some experiments in some test cases to find some clues.

Experiments in large cases with \(N=4\) or larger take long if done by hand, so it is advisable to write codes that solve the problem naively or generate test cases.

Below is a C++ program that solves the problem with brute-force.

#include <iostream>
#include <vector>
using namespace std;

// returns true if the first player wins with the cookies vec[0], vec[1], ..., vec[vec.size()-1]
bool solve(vector<int> vec) {
	// if XOR is 0, the second player wins
	int All_XOR = 0;
	for (int i = 0; i < vec.size(); i++) {
		All_XOR ^= vec[i];
	}
	if (All_XOR == 0) {
		return false;
	}

	// otherwise...
	for (int i = 0; i < vec.size(); i++) {
		// take the i-th cookie
		vector<int> nex;
		for (int j = 0; j < vec.size(); j++) {
			if (j != i) nex.push_back(vec[j]);
		}
		bool ret = solve(nex);
		if (ret == false) return true; // first player wins
	}
	return false; // second player wins
}

int main() {
	// input
	int N; cin >> N;
	vector<int> A(N, 0);
	for (int i = 0; i < N; i++) cin >> A[i];

	// output
	bool Answer = solve(A);
	if (Answer == true) cout << "Win" << endl;
	else cout << "Lose" << endl;
	return 0;
}


4. Sample Codes

posted:
last update: