Codeforces 1065-C1/C2 Review: XOR Games and the Most Significant Bit

Introduction

This time, CF1065 C1/C2 gave us a particularly representative pair of XOR games.

During the contest, both problems seemed to be about manipulating arrays and simulating swaps. Their real structure, however, comes from three remarkably stable ingredients:

• A total XOR T that stays unchanged throughout the game.
• A most significant bit (msb) that determines which player’s XOR is larger.
• A “last critical index” that can change the outcome.

C1 is a single-bit game and C2 is a multibit game, but their underlying structure is closely aligned. C2 can even be seen as a natural generalization of C1.

I will present the article as a review with a structured analysis:

• C1: Understand the simplest XOR game (0/1).
• C2: Extend it to a general XOR game (≤10⁶).
• Finish with an overview of the entire XOR-game framework.

There will also be ASCII diagrams to help explain structures such as the critical index and the most significant bit.

Let us get started.

C1. Renako Amaori and XOR Game (Easy Version)

Problem Statement

Problem in English

We are given two arrays a and b of length n, with every element equal to 0 or 1.
The game lasts n turns:

• If i is odd, Ajisai takes the turn.
• If i is even, Mai takes the turn.

On turn i, the player may choose to:

• Swap a[i] and b[i], or
• Do nothing (pass).

After the game, the scores are:

• Ajisai’s score: a[1] ⊕ a[2] ⊕ ... ⊕ a[n]
• Mai’s score: b[1] ⊕ b[2] ⊕ ... ⊕ b[n]

If the scores differ, the player with the larger score wins. If they are equal, the game is a tie.

The Invariant Total XOR

Every swap exchanges a[i] and b[i] at the same index i.
This does not change the collection of all elements in the two sequences, so:

T = a 全体 ⊕ b 全体

Here, the Chinese labels mean “all elements of a” and “all elements of b.” This total stays unchanged throughout the game and forms the foundation of both C1 and C2.

We also have:

T = Ajisai_score ⊕ Mai_score

This means the final outcome depends only on T.

• If T = 0
  → The players’ final XOR values are exactly equal.
  → The game must be a tie.

• If T = 1
  → The players’ final XOR values cannot be equal.
  → There must be a winner.

This is the foundation of C1 and the key starting point for C2.

Next, let us review my mistaken approach to C1.

Reviewing the Wrong Approach: Assuming Counts at Odd and Even Positions Decide the Winner

During the contest, my first approach tried to determine the winner by “counting differing elements at odd and even positions”:

• If more positions with a[i] != b[i] occur at odd indices, where Ajisai can act,
  → Ajisai has more “influence over the game,” so I assumed Ajisai would win.

• If more differences occur at even indices, Mai’s turns,
  → Mai would win.

• If the counts are equal, I assumed a tie.

This sounds reasonable, but it is completely wrong.

C1 WA Code (My Contest Version)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include<bits/stdc++.h>
using namespace std;
int const maxn = 2e5 + 5;

int t, a[maxn], b[maxn];

void op(){
    int n, cnt_odd = 0, cnt_even = 0;
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> b[i];
        if(a[i] != b[i]){
            if(i & 1){
                cnt_odd++;
            } else{
                cnt_even++;
            }
        }
    }
    if(cnt_odd > cnt_even){
        cout << "Ajisai" << '\n';
    } else if(cnt_odd < cnt_even){
        cout << "Mai" << '\n';
    } else{
        cout << "Tie" << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while(t--){
        op();
    }
    return 0;
}

Why It Is Wrong

The fundamental problem is:
The winner of an XOR game is determined by a single critical index, rather than by a “count.”

In C1, all elements are 0/1. If the total XOR is T = 1, one player’s final score is larger than the other’s, and the ordering is determined by “the last index that can flip that bit.”

In other words:

Comparing XOR values is about the effect of the last move, rather than an accumulated advantage.

An ASCII diagram makes this easier to see.

Diagram: Scan Differing Positions from Back to Front

1
2
3
4
5
6
7

i = 9   a=1 b=1
i = 8   a=0 b=0
i = 7   a=1 b=0   ← 最后一个差异，决定胜负
i = 6   a=0 b=0
i = 5   a=1 b=1
i = 4   a=0 b=0
...

Diagram legend: The arrow marks “the last difference, which decides the winner.”

We can see that:

• Later indices have greater control over the final XOR result.
• If a player can act at i = 7, no later index can override that action.

Therefore:

• If the last differing position is odd → Ajisai acts there → Ajisai wins, as in the diagram.
• If the last differing position is even → Mai acts there → Mai wins.

No matter how many earlier differing positions exist, this last differing position overrides them.

Why Are Counts Misleading?

It does not matter how many times a[i] != b[i] occurs.
What decides the XOR comparison is:

Who is the last person able to change the relevant bit?

In C1, this final position is simply “the last differing position.”
XOR acts independently on each bit, and C1 has only one bit—just 0/1—so:

• If i = k is the last occurrence of a[i] != b[i],
• The player acting at k can choose whether their final XOR is 1 or 0.

That directly determines the winner.

The Mistakes to Remember

1. XOR magnitudes do not accumulate; the last critical bit controls the result.
2. C1 has only one bit, so we only need the “last differing position.”
3. The number of differences does not affect the winner at all.
4. The correct strategy must be based on “a sequential game + control over the last move.”

Now let us move to the correct C1 solution.

Correct C1 Solution: The Player at the Last Differing Index Wins

The central point in C1 is:
When the total XOR is T = 1, the final XOR comparison is entirely determined by the last position that can flip the bit.

As the error analysis showed, knowing the “last differing index” is enough to identify the winner.

Let us now describe this structure more rigorously.

1. When T = 1, the Last Differing Index Decides the Winner

In C1, every element is 0 or 1.
The final scores are:

• Ajisai_score = a[1] ⊕ ... ⊕ a[n]
• Mai_score = b[1] ⊕ ... ⊕ b[n]

Since T = Ajisai_score ⊕ Mai_score and T = 1,
one score must be 0 and the other 1.

The question becomes:

Who can decide whether a particular position contributes a 1 to the final XOR?

XOR’s Bitwise Independence Makes the Turn Order Crucial

For sequence a:

最终 a 的 XOR = (((a[1] ⊕ a[2]) ⊕ a[3]) ... ⊕ a[n])

The left-hand label means “the final XOR of a.” Analyzing from left to right:

• Changing a later element can override the effects of all earlier elements.
• Even if an earlier differing position tried to flip the result, a later differing position can flip it back.

The conclusion follows naturally:

In C1, the last position with a[i] != b[i] is the only position with final control.

2. ASCII Diagram

Here is the complete diagram—the same idea as before, now placed within the correct solution:

1
2
3
4
5
6
7
8
9

i = 9   a=1 b=1
i = 8   a=0 b=0
i = 7   a=1 b=0   ← 决胜点（最末一个差异）
i = 6   a=0 b=0
i = 5   a=1 b=1
i = 4   a=0 b=0
i = 3   a=1 b=1
i = 2   a=0 b=0
i = 1   a=1 b=1

Diagram legend: The arrow marks “the decisive point: the last difference.”

• Index 7 is the last differing position.
• 7 is odd → Ajisai takes that turn.
• By choosing “swap / do not swap,” Ajisai can decide whether a[7] becomes 1 or 0.

Ajisai can therefore decide whether their final XOR is 1
→ and decide the winner.

If the last differing index is even, Mai controls it.

3. The C1 Rule

Thus, for C1:

• Scan backward to find the last index i with a[i] != b[i].
• If none exists, T = 0 → tie.
• If one exists:
  • Odd i → Ajisai wins.
  • Even i → Mai wins.

This is the complete correct solution to C1.

4. C1 AC Code

Note:

The accepted code below is the implementation I wrote during the contest.
Its logic is correct, but the style reflects my own habits and differs slightly from the theoretical model developed in this article.
For C2, I will give a “standard implementation” that follows the article’s structure exactly.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include<bits/stdc++.h>
using namespace std;
int const maxn = 2e5 + 5;

int t, a[maxn], b[maxn];

void op() {
    int n, cnt_odd = 0, cnt_even = 0, cnt_1 = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        cnt_1 += a[i] ? 1 : 0;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
        cnt_1 += b[i] ? 1 : 0;
        if (!(cnt_1 & 1)) {
            cout << "Tie" << '\n';
            return;
        }
        bool last_person; //1->odd 0->even
        for (int i = n; i >= 1; --i) {
            if (a[i] != b[i]) {
                last_person = (i & 1);
                break;
            }
        }
        if (last_person) {
            cout << "Ajisai" << '\n';
        } else {
            cout << "Mai" << '\n';
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while (t--) {
        op();
    }
    return 0;
}

C2. Renako Amaori and XOR Game (hard version)

Problem Statement

Problem in English

This is the harder version of C1.
We are given two arrays a and b of length n, satisfying 0 ≤ a[i], b[i] ≤ 10^6.

The game still lasts n turns:

• If i is odd, Ajisai takes the turn.
• If i is even, Mai takes the turn.

On turn i, the player whose turn it is may choose to:

• Swap a[i] and b[i], or
• Do nothing (pass).

The final scores are:

• Ajisai’s score: a[1] ⊕ a[2] ⊕ ... ⊕ a[n]
• Mai’s score: b[1] ⊕ b[2] ⊕ ... ⊕ b[n]

The higher score wins; equal scores mean a tie.

Unlike C1, a[i] and b[i] are no longer restricted to 0/1. They can be as large as 10^6, containing more binary bits. T is no longer just 0 or 1, but a multibit integer.

The Invariant Total XOR: The Same Framework as C1

Exactly as in C1, each operation only swaps a[i] and b[i] at one position. It neither introduces a new number nor removes an existing one, so:

T = a 全体 ⊕ b 全体

The expression means the XOR of all elements of a and b, and remains invariant throughout the game.

We still have:

T = Ajisai_score ⊕ Mai_score

Therefore:

• If T = 0
  → The final scores are exactly equal.
  → The game must be a Tie.

• If T ≠ 0
  → The final scores must differ.
  → There must be a winner.

Up to this point, C2 and C1 share the same framework:
when the total XOR is 0, there is no uncertainty—it is a tie.
When it is nonzero, the question becomes: who can make the final value larger in their own favor?

The difference is that C1 involves only one bit, 0/1, while C2 involves a multibit integer.

Why Only the Most Significant Bit (msb) Matters

When T ≠ 0, T is a multibit integer, for example:

T = 0010 1000 0100₂

This means Ajisai’s and Mai’s final results differ at several bits.

But integer comparison has a crucial property:

The ordering of two integers is determined solely by their values at the highest binary bit where they differ.

In other words:

• Find the highest bit where Ajisai_score and Mai_score differ.
• The player with 1 at that bit beats the player with 0.
• Every lower bit is irrelevant.

Since:

Ajisai_score ⊕ Mai_score = T

a 1 at any bit of T means the players differ at that bit.
In particular, at the most significant set bit of T, called msb, one player’s score has a higher bit value than the other’s, and this bit decides the final comparison.

Here is an ASCII sketch of the bits of T:

1
2
3
4

bit11 bit10 bit9 ... bit3 bit2 bit1 bit0
  1     0    1        0    1    0    0
  ↑
  msb（最高有效位）

Diagram legend: msb means “most significant bit,” marked by the arrow.

At bit11, T is 1, meaning:

• Ajisai_score and Mai_score differ at bit11.
• bit11 is the first bit where they differ when scanning from high to low.

Therefore:

• Whoever can make their final bit11 equal 1 gains the advantage in the entire numeric comparison.
• Flipping lower bits, at bit10 and below, cannot overturn this conclusion.

Thus, although C2 has multiple bits, its game structure still reduces to control over the single bit msb:

C2 is, at its core, a C1-style game played at the most significant bit msb.

The remaining analysis must identify exactly who has the last opportunity to act on that bit, and therefore who makes its final decision.

Finding the Largest Index i_max That Can Affect msb

We already know:

• The most significant bit msb of T decides the winner.
• The players’ XOR values must differ at that bit.
• Whoever can make their final value at that bit 1 wins.

The questions now are:

Which indices i can affect msb?
Who is the last person able to affect it?

The Critical Condition

At index i, choosing to swap rather than pass flips msb if and only if:

((a[i] ⊕ b[i]) >> msb) & 1 == 1

This means:

• a[i] ⊕ b[i] has a 1 at msb.
• Swapping a[i] and b[i] changes the contribution at that bit.
• This index can therefore affect the highest decisive bit of the final scores.

We call such an index:

“An effective index that affects msb.”

Why Must We Find the Largest Such Index?

The game proceeds in order from 1 to n, so turns at larger indices occur later.
Suppose the following five indices can affect msb:

i = 2, 5, 8, 11, 14

Only one truly decides the winner:

• The last one, 14.
• It can override the effect of every earlier decision.
• Earlier influences are overridden by a later change, just as in C1.

In other words:

i_max = 最后一个能影响 msb 的下标
That is, the last index able to affect msb is the only critical point in this problem.

ASCII Diagram (#3)

Consider this example:

1
2
3
4
5
6

i = 12   (a⊕b 在 msb 位为 1)
i = 11   (a⊕b 在 msb 位为 0)
i = 10   (a⊕b 在 msb 位为 1)
i =  9   (a⊕b 在 msb 位为 1)   ← i_max（最后一个能影响 msb 的位置）
i =  8   (a⊕b 在 msb 位为 0)
...

Diagram legend: Each parenthesis states whether a⊕b has a 1 or 0 at msb. The arrow labels i_max as “the last position that can affect msb.”

Even though i = 12 and i = 10 can also affect msb,
they are ultimately “overridden” by the operation at i = 9:

• Turn 9 is the last opportunity to change msb.
• No later index can affect msb.
• The player at i = 9 can therefore decide the winner.

The Correspondence with C1

We can now see that C2 matches C1 exactly in structure:

One way to understand this is:

• C1 is a “one-dimensional game.”
• C2 is a “multidimensional game split by bit,” but only the highest dimension decides the winner.

Determining the Winner from i_max

The rule is simple:

• If i_max is odd
  → Ajisai acts.
  → Ajisai can make their msb equal 1.
  → Ajisai wins.

• If i_max is even
  → Mai acts.
  → Mai can make their msb equal 1.
  → Mai wins.

This is the final conclusion for C2.

C2 Algorithm and Complexity Analysis

Combining the analysis into a complete implementation gives roughly these steps:

1. Read n and arrays a, b.
2. Calculate the total XOR T:
   • T ^= a[i]
   • T ^= b[i]
3. If T = 0:
   • Output Tie immediately, since the final scores must be equal.
4. If T ≠ 0:
   • Find the most significant bit msb of T within bit positions 0 ~ 20.
   • This is the only bit that determines the winner.
5. Scan backward through indices i = n ... 1:
   • Check whether (a[i] ⊕ b[i]) has a 1 at msb.
   • If so, record that i as i_max and stop scanning.
6. Output the winner according to the parity of i_max:
   • Odd i_max → Ajisai.
   • Even i_max → Mai.

Complexity Analysis

• Calculate the total XOR T: O(n).
• Find msb: a bit scan taking O(log T), approximately constant here—about 20.
• Scan backward for i_max: O(n).
• Overall time complexity: O(n).
• Space complexity: O(n), for storing a and b.

For n up to 2 * 10^5, this comfortably passes all tests.

C2 AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include<bits/stdc++.h>
using namespace std;

int t;

void op() {
    int n, xor_sum = 0, msb;
    cin >> n;
    vector<int> a(n + 5), b(n + 5);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        xor_sum ^= a[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
        xor_sum ^= b[i];
    }
    if (!xor_sum) {
        cout << "Tie" << '\n';
        return;
    }
    for (int i = 20; i >= 0; --i) {
        if (1 & (xor_sum >> i)) {
            msb = i;
            break;
        }
    }
    for (int i = n; i > 0; --i) {
        if (((a[i] ^ b[i]) >> msb) & 1) {
            cout << ((i & 1) ? "Ajisai" : "Mai") << '\n';
            return;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while (t--) {
        op();
    }
    return 0;
}

XOR Properties and the Game Structure: A Final Review

From C1, the 0/1 case, to C2, the multibit case, the entire article revolves around one central theme:

XOR’s structure—invariants, bitwise independence, and the decisive most significant bit—
together with the rule that, in a sequential game, “the last person able to change the critical bit wins.”

Let us bring the complete framework together.

1. Three Core Properties of XOR

Only three basic XOR properties do the real work in these two problems:

• Bitwise independence: High and low bits do not affect one another.
• Invariant XOR: Swapping positions does not change the total XOR.
• The highest differing bit decides integer order: This lets C2 focus on the single bit msb.

The most important is the third:
Once the difference at the most significant bit is fixed, lower bits cannot change the final ordering.

The central task in XOR games is therefore often:

Find the last position that can decide the critical bit.

2. C1: Control over the Last Move in a Single-Bit Game

In C1:

• Every element is 0 or 1.
• The final XOR has only one bit.
• The last index with a[i] != b[i] completely determines the winner.

This is a typical “sequential game + last move wins” structure.

3. C2: Multiple Bits, but Only the Highest Bit Needs Attention

In C2:

• Elements contain more bits.
• The total XOR T is a multibit integer.
• The final ordering still depends only on the most significant bit msb of T.

C2 therefore amounts to:

Run C1’s logic on the bit msb.

Specifically:

• Find the last i where (a[i] ⊕ b[i]) has a 1 at msb.
• The player acting at that i has the deciding move.
• Odd index → Ajisai.
• Even index → Mai.

This is completely parallel to C1.

4. A General Approach to a Class of XOR Games

These two problems suggest a general framework for a common class of XOR games:

1. Find an invariant: Is the total XOR fixed?
2. Determine the tie condition: A total XOR of 0 generally means a tie immediately.
3. Find the critical bit: Usually msb.
4. Locate the critical index: The last position that can affect that bit.
5. Output the winner according to whose turn it is.

Many seemingly complicated XOR games can be broken down into this structure.

5. What This Review Leaves Us With

Beyond solving C1 / C2, this article provides a unified perspective for future problems of this kind:

• When facing an XOR game, first look for an invariant.
• Then ask whether it can be split by bit.
• If so, the most significant bit is usually central.
• Determine whether the turn order decides the winner.
• Look for “the last position that can flip the critical bit.”

XOR itself is not complicated, but understanding its role in games requires a clear grasp of “bitwise independence + sequential control.”

That is everything for this article.