2171C1 - Ajisai vs Mai (Simple Version)

Problem Understanding

This is the simplified version of the game where the elements of arrays $A$ and $B$ are likely binary ($0$ or $1$). The goal is to determine the winner based on the differences between the two arrays.

Approach

Key Insight

Unlike the hard version (C2) which deals with general integers and checks bits from MSB to LSB, this version deals directly with the values (likely representing a single bit layer or boolean states).

The game logic simplifies to:

1. Count Differences: Calculate the total number of positions where $A[i] \neq B[i]$. Let this be $C1$.
2. Tie Condition: If the total count of differences $C1$ is even, the game ends in a Tie.
3. To Determine Winner: If $C1$ is odd, the winner is decided by the largest index $i$ where $A[i] \neq B[i]$.

Winning Criteria

If $C1$ is odd:

• Find the largest index $i$ (iterate backwards from $n-1$) where $A[i] \ne B[i]$.
• Check the parity of the position $(i+1)$:
  • If $(i+1)$ is odd, Ajisai wins.
  • If $(i+1)$ is even, Mai wins.

Note: The code explicitly checks (a[i] & b[i]) == 0 along with a[i] ^ b[i]. For binary inputs ($0$ and $1$), if $A[i] \neq B[i]$, then one is $0$ and the other is $1$, so their bitwise AND is always $0$. This condition essentially confirms they are distinct binary values.

Algorithm Steps

1. Input Reading: Read arrays $A$ and $B$.
2. Difference Counting:
   • Iterate through the arrays.
   • Increment counter $C1$ if $A[i] \neq B[i]$ (specifically checks b[i]==1 && a[i]==0 and vice-versa).
3. Check Tie:
   • If $C1 \% 2 == 0$, output “Tie”.
4. Find Winner:
   • Iterate backwards from $i = n-1$ to $0$.
   • Find the first index where $A[i] \neq B[i]$.
   • Output “Ajisai” if $(i+1)$ is odd.
   • Output “Mai” if $(i+1)$ is even.
   • Break immediately after finding the deciding index.

Complexity Analysis

• Time Complexity: $O(N)$ - One pass to read/count differences, and at most one reverse pass to find the deciding index.
• 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);

    ll C1 = 0;
    for(ll i = 0; i < n; i++){
        cin >> a[i];
    }
 
    for(ll i = 0; i < n; i++){
        cin >> b[i];
        // Count differences (assuming binary inputs 0/1)
        C1 = (b[i] == 1 && a[i] == 0) ? C1 + 1 : C1;
        C1 = (b[i] == 0 && a[i] == 1) ? C1 + 1 : C1;
    }

    // If total differences count is even, it's a Tie
    if(C1 % 2 == 0){
        cout << "Tie\n";
        return;
    }

    // Find the largest index i where they differ
    for(ll i = n - 1; i >= 0; i--){
        // Logic: if differing (xor) and mutually exclusive (and == 0)
        // For 0/1, differing implies mutually exclusive.
        bool is_different = (a[i] ^ b[i]); // true if different
        bool is_exclusive = ((a[i] & b[i]) == 0); // true if not both 1 (always true if different 0/1)

        if(is_exclusive && is_different){
            if((i+1) % 2 != 0){
                cout << "Ajisai\n";
            } else {
                cout << "Mai\n";
            }
            break;
        }
    }
}

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