2171C2 - Ajisai vs Mai (Bitwise Game)

Problem Understanding

We are given two arrays $A$ and $B$ of size $n$. We need to determine the winner of a game (or a comparison) based on specific bitwise properties. The game can result in a win for “Ajisai”, “Mai”, or a “Tie”.

Approach

Key Insight

The game relies on finding the most significant bit (MSB) where the two arrays differ in a “meaningful” way. Specifically, we look for the highest bit position $k$ (from 29 down to 0) where the total count of differences between $A[i]$ and $B[i]$ is odd.

If the total count of differences at bit $k$ is even, the differences effectively “cancel out” (likely mimicking a Nim-sum or XOR sum property equaling 0), and we move to the next lower bit.

If we find such a bit $k$ where the difference count is odd, this bit position decides the winner.

Winning Condition

Once the deciding bit $k$ is found (where the count of indices with $A[i]$ having a different $k$-th bit than $B[i]$ is odd):

1. We look for the largest index $i$ such that $A[i]$ and $B[i]$ differ at this bit $k$.
2. The winner is determined by the parity of this index ($1$-based):
   • If $(i+1)$ is odd (i.e., $i = 0, 2, 4, \dots$), Ajisai wins.
   • If $(i+1)$ is even (i.e., $i = 1, 3, 5, \dots$), Mai wins.

If checking all bits from 29 to 0 yields no such bit (i.e., for every bit position, the number of differing pairs is even), then the result is a Tie.

Algorithm Steps

1. Iterate Bits: Loop from bit $k = 29$ down to $0$.
2. Count Differences: For each bit $k$, count how many indices $i$ satisfy (A[i] >> k) & 1 != (B[i] >> k) & 1. Let this count be $C1$.
3. Check Parity:
   • If $C1$ is even, continue to the next lower bit.
   • If $C1$ is odd, this is the deciding bit. Proceed to determining the winner and break.
4. Determine Winner:
   • Iterate backwards from $i = n-1$ to $0$.
   • Find the first index $i$ where the $k$-th bit differs.
   • If $(i+1)$ is odd, output “Ajisai”.
   • If $(i+1)$ is even, output “Mai”.
   • Stop checking further.
5. Tie Case: If the loop finishes without finding any such bit, output “Tie”.

Complexity Analysis

• Time Complexity: $O(30 \cdot N)$. We iterate through roughly 30 bits, and for each bit, we may iterate through the array of size $N$. This simplifies to $O(N)$.
• Space Complexity: $O(N)$ to store the input arrays.

Code

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

void solve(){
    ll n;
    cin >> n;

    vector<ll> a(n),b(n);
    for(ll i = 0; i < n; i++){
        cin >> a[i];
    }

    for(ll i = 0; i < n; i++){
        cin >> b[i];
    }
 
    bool flag = true;
    for(ll k=29; k >= 0; k--){
        ll C1 = 0;
        // Count pairs differing at bit k
        for(ll i = 0; i < n; i++){
            // Check if k-th bits differ
            if ( ((b[i] >> k) & 1) != ((a[i] >> k) & 1) ) {
                C1++;
            }
        }
        
        // If count is odd, this bit decides the winner
        if(C1 % 2 != 0){
            flag = false;
            // Find the largest index i contributing to the difference
            for(ll i = n - 1; i >= 0; i--){
                bool different_at_k = ((b[i] >> k) & 1) != ((a[i] >> k) & 1);
                
                if(different_at_k){
                    if((i+1) % 2 != 0){
                        cout << "Ajisai\n";
                    } else {
                        cout << "Mai\n";
                    }
                    break;
                }
            }
            break; // Found the deciding bit, stop.
        }
    }
    
    if(flag == true){
        cout << "Tie" << "\n";
    }
}

int main(){
    ios::sync_with_stdio(false); 
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}