XORGAME1 - Editorial

[iceknight1093]

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: q_ed
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Tries

PROBLEM:

There’s an array A of length N.
First, Alice will choose two indices i and j, and set A_i := A_i\oplus A_j.
Then, Bob will choose two indices i and j, and set A_i := A_i\oplus A_j.

This happens exactly once.
Alice wants to maximize A_1 \oplus \ldots\oplus A_N, while Bob wants to minimize it.
Find the final value if both players play optimally.

EXPLANATION:

Let X = A_1 \oplus\ldots\oplus A_N denote the bitwise XOR of the array.

When a player makes the move (i, j), the value of X changes to X\oplus A_i \oplus (A_i \oplus A_j) = X\oplus A_j.
Note that this is independent of i.

Let Alice’s move be denoted by (i_1, j_1) and Bob’s move by (i_2, j_2).
Suppose we fix (i_1, j_1). Let’s figure out what Bob will do.

The current XOR is X\oplus A_{j_1}.
Bob’s options are as follows:

1. Choose j_2 = i_1. Note that the current value at index i_1 equals A_{i_1} \oplus A_{j_1} after Alice’s initial move.
   In this case, the resulting XOR is X\oplus A_{j_1} \oplus (A_{i_1} \oplus A_{j_1}) = X\oplus A_{i_1}.
2. Choose j_2 \ne i_1. This element wasn’t changed by Alice’s move.
   In this case, the resulting XOR is X\oplus A_{j_1} \oplus A_{j_2}.

So, if (i_1, j_1) is fixed, the best Bob can do is \min(X\oplus A_{i_1}, X\oplus A_{j_1} \oplus A_{j_2}) across all j_2 \neq i_1.

---

Let’s fix only the index j_1 and attempt to figure out what the optimal choice of i_1 for Alice should be.

Let j_2 be the index such that X \oplus A_{j_1} \oplus A_{j_2} is minimized.
Then, observe that for any choice of i_1 such that i_1 \neq j_2, Bob will reach exactly the score \min(X\oplus A_{i_1}, X\oplus A_{j_1} \oplus A_{j_2}).
Specifically, one expression there is a constant across all choices of i_1, so Alice should just choose whichever i_1 (other than j_2) maximizes X\oplus A_{i_1}.

Finding j_2 is a standard problem, and can be solved in \mathcal{O}(\text{bits}) using a bit-trie (if you don’t know how, read this.)
Once j_2 is known, we want to find i_1 \neq j_2 that maximizes (X\oplus A_{i_1}).
There are many ways to do this; the simplest is to just compute the overall maximum of (X\oplus A_i) across all i, as well as the second maximum. If j_2 equals the index of the maximum, take the second maximum; otherwise just use the maximum.

This allows us to solve for all i_1 \neq j_2.
What about i_1 = j_2?

Well, that’s a single operation - so we can just simulate it.
Suppose you have a bit-trie that contains all the elements of A (which is needed for the subtask of finding j_2 above anyway).
Alice performing the operation (j_2, j_1) simply results in A_{j_2} being deleted from the trie and A_{j_2} \oplus A_{j_1} being inserted into it; after which Bob only wants to know the minimum value of
(X\oplus A_{j_1}) \oplus y for some y existing in the trie; which we already have a function for anyway.
Make sure to reset the trie to its initial state after the query (which is just one insertion and one deletion again.)

This way, we’re able to process a single index j_1 in \mathcal{O}(\text{bits}) time and find Alice’s best possible score for it.
Try all choices of j_1 and take the best answer among them.

TIME COMPLEXITY:

\mathcal{O}(N\log\max(A)) per testcase.

CODE:

Editorialist's code (C++)

// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

struct Trie {
    vector<int> ct;
    vector<array<int, 2>> ch;
    Trie() : ct(1, 0), ch(1, {-1, -1}) {}
    void create() {
        ct.push_back(0);
        ch.push_back({-1, -1});
    }
    void insert(int x) {
        int node = 0;
        for (int bit = 30; bit >= 0; --bit) {
            ++ct[node];
            int b = (x >> bit) & 1;
            if (ch[node][b] == -1) {
                create();
                ch[node][b] = size(ct) - 1;
            }
            node = ch[node][b];
        }
        ++ct[node];
    }
    void erase(int x) { // Assumes x exists
        int node = 0;
        for (int bit = 30; bit >= 0; --bit) {
            --ct[node];
            int b = (x >> bit) & 1;
            node = ch[node][b];
        }
        --ct[node];
    }
    array<int, 2> query_min(int x) {
        int node = 0, res = 0, val = 0;
        for (int bit = 30; bit >= 0; --bit) {
            int b = (x >> bit) & 1;
            if (ch[node][b] == -1 or ct[ch[node][b]] == 0) {
                val += (1^b) << bit;
                res += 1 << bit;
                node = ch[node][1^b];
            }
            else {
                val += b << bit;
                node = ch[node][b];
            }
        }
        return {res, val};
    }
};

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector a(n, 0);
        for (int &x : a) cin >> x;

        Trie T;
        int x = 0;
        for (int i = 0; i < n; ++i) {
            T.insert(a[i]);
            x ^= a[i];
        }

        int mx1 = a[0], mx2 = a[1];
        if ((x^mx1) < (x^mx2)) swap(mx1, mx2);
        for (int i = 2; i < n; ++i) {
            if ((x^a[i]) >= (x^mx1)) {
                mx2 = mx1;
                mx1 = a[i];
            }
            else if ((x^a[i]) >= (x^mx2)) mx2 = a[i];
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            auto [mn, val] = T.query_min(x ^ a[i]);
            int best = mn;
            if (val == mx1) best = min(best, x ^ mx2);
            else best = min(best, x ^ mx1);

            T.erase(val);
            T.insert(val ^ a[i]);
            best = max(best, T.query_min(x ^ a[i])[0]);
            T.erase(val ^ a[i]);
            T.insert(val);
            ans = max(ans, best);
        }
        cout << ans << '\n';
    }
}

Author's code (C++)

#include <bits/stdc++.h>
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}
template <typename T, std::size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& arr) {
    os << "[";
    for (std::size_t i = 0; i < N; ++i) {
        os << arr[i];
        if (i < N - 1) {
            os << ", ";
        }
    }
    os << "]";
    return os;
}
template<typename T> std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
    os << "{ ";
    for(const auto& elem : s) {
        os << elem << " ";
    }
    os << "}";
    return os;
}
template<typename T> std::ostream& operator<<(std::ostream& os, const std::multiset<T>& s) {
    os << "{ ";
    for(const auto& elem : s) {
        os << elem << " ";
    }
    os << "}";
    return os;
}

template<typename T> std::ostream& operator<<(std::ostream& os, std::queue<T> q) {
    // Print each element in the queue
    os << "{ ";
    while (!q.empty()) {
        os << q.front() << " ";
        q.pop();
    }
    os << "}";
    // Print a newline at the end
    return os;
}
template<typename T> std::ostream& operator<<(std::ostream& os, std::deque<T> q) {
    // Print each element in the queue
    os << "{ ";
    while (!q.empty()) {
        os << q.front() << " ";
        q.pop();
    }
    os << "}";
    // Print a newline at the end
    return os;
}
template<typename T> std::ostream& operator<<(std::ostream& os, std::stack<T> q) {
    // Print each element in the queue
    os << "{ ";
    while (!q.empty()) {
        os << q.top() << " ";
        q.pop();
    }
    os << "}";
    // Print a newline at the end
    return os;
}
template<typename T> std::ostream& operator<<(std::ostream& os, std::priority_queue<T> q) {
    // Print each element in the queue
    os << "{ ";
    while (!q.empty()) {
        os << q.top() << " ";
        q.pop();
    }
    os << "}";
    // Print a newline at the end
    return os;
}

template<typename T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
    os << "[ ";
    for(const auto& elem : vec) {
        os << elem << " ";
    }
    os << "]";
    return os;
}
template<typename K, typename V> std::ostream& operator<<(std::ostream& os, const std::map<K, V>& m) {
    os << "{ ";
    for(const auto& pair : m) {
        os << pair.first << " : " << pair.second << ", ";
    }
    os << "}";
    return os;
}
template<typename T>
using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
using namespace std;
using ll = long long;
#define add push_back 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define f first
#define s second
#define trav(a,x) for (auto& a: x)
#define int long long
#define vt vector
// #define endl "\n"
#define double long double
const ll mod = 1000000007;
const ll inf = 1e18;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
struct Trie {
    vt<int> lChild, rChild, count;
    int nxt = 1;
    Trie() {
        lChild.add(-1);
        rChild.add(-1);
        count.add(0);
    }
    void insert(int x) {
        // cout << "LINE 147 " << x << " " << nxt << endl;
        int cur = 0;
        R0F(i, 31) {
            if(x&(1<<i)) {
                if(rChild[cur]==-1) {
                    rChild[cur]=nxt++;
                    rChild.add(-1);
                    lChild.add(-1);
                    count.add(0);
                }
                cur=rChild[cur];
            } else {
                if(lChild[cur]==-1) {
                    lChild[cur]=nxt++;
                    lChild.add(-1);
                    rChild.add(-1);
                    count.add(0);
                }
                cur=lChild[cur];
            }
            count[cur]++;
        }
    }
    void remove(int x) {
        // cout << "LINE 171 " << x << endl;
        // cout <<lChild[32] << rChild[32] << endl;
        int cur = 0;
        R0F(i, 31) {
            // cout << cur << endl;
            if(x&(1<<i)) {
                cur=rChild[cur];
            } else {
                cur=lChild[cur];
            }
            count[cur]--;
        }
    }
    int minimize_xor(int alr) {
        // cout << "LINE 183 " << alr << endl;
        int cur = 0, ans = 0;
        // cout << "LINE 187" << endl;
        R0F(i, 31) {
            // cout << cur << " " << count[lChild[cur]] << " " << count[rChild[cur]] << endl;
            if(alr&(1<<i)) {
                if(rChild[cur]!=-1&&count[rChild[cur]]) {
                    cur=rChild[cur];
                    ans+=1<<i;
                } else {
                    cur=lChild[cur];
                }
            } else {
                if(lChild[cur]!=-1&&count[lChild[cur]]) {
                    cur=lChild[cur];
                } else {
                    cur=rChild[cur];
                    ans+=1<<i;
                }
            }
        }
        return ans;
    }
};
signed main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    // freopen("input.txt" , "r" , stdin);
    // freopen("output.txt" , "w", stdout);
    // Trie tt;
    // tt.insert(1);
    // tt.insert(2);
    // tt.insert(3);
    // tt.remove(3);
    // cout << tt.minimize_xor(3);
    // return 0;
    int t = 1;
    cin >> t;
    // t=0;
    while(t--) {
        int n;
        cin >> n;
        vt<int> a(n);
        F0R(i, n) cin >> a[i];
        int tot = 0, ans = 0;
        F0R(i, n) tot^=a[i];
        Trie tr;
        F0R(i, n) tr.insert(a[i]);
        int mx = 0;
        F0R(i, n) mx=max(mx, a[i]^tot);
        int option2a = mx^tot;
        trav(b, a) {
            int here = inf, here2 = inf;
            here=min(here, mx);
            tr.remove(option2a);
            here=min(here, tot^b^tr.minimize_xor(tot^b));
            tr.insert(option2a);
            int option1a = tr.minimize_xor(tot^b);
            here2=min(here2, tot^option1a);
            tr.remove(option1a);
            here2=min(here2, tot^b^tr.minimize_xor(tot^b));
            tr.insert(option1a);
            // cout << b << " " << here << " " << here2 << endl;
            ans=max(ans, here);
            ans=max(ans, here2);
        }
        cout << ans << endl;
    }
    return 0;
}
/*
1 2 3 4
*/
/*
Let X denote XOR of all numbers initially
Let's suppose Alice's move is to set a to a^b
Case 1: Bob chooses the new number (a^b) -> XOR sum = X^b^(a^b)=X^a
Case 2: Bob chooses another number -> XOR sum = X^b^c (where c!=a)

Loop through b. Whats optimal a to pick?
- option 1: choose a to be the c that minimizes X^b^c (so Bob cant pick it)
- option 2: choose a to be the one that maximizes X^a
*/

[aiaiai]

Hi, can you please critique the following approach:
consider xor_val as the xor value of the original array.
Now, iterate over the array to produce a new value xor_value2 for each unique value X in the array.
This is the score of the array when it’s Bob’s turn. Now, Bob uses the elements in the array to find optimal a[i] such that xor_value2 ^ a[i] is minimal. If Alice has modified any other element then Bob can choose this a[i] and get the min value.
However, if Alice has modified a[i], then it is not accessible and therefore we must remove a[i] from the bit trie and insert a[i] ^ X. Note that xor_value2 has remained unchanged. So, we can now find the value in a that minimizes score.

[for_array_74]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
using vpi = vector<pair<ll, ll>>;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using vli = vector<long long>;
using vvi = vector<vector<ll>>;
#define pb push_back
#define ppb pop_back
#define mp(a,b) make_pair(a,b)
#define f(i, n) for (ll i = 0; i < n; i++)
#define endn '\n'
#define MOD (ll)(998244353)
#define all(x) x.begin(),x.end()
#define rll(x) x.rbegin(),x.rend()
void solve(){
    ll n;cin>>n;
    vi vec(n);
    for(auto &x:vec) cin>>x;
    ll ans=0;
    f(i,n) ans=(ans^vec[i]);
    ll ans1=INT_MIN,ans2=INT_MAX,idx=0;
    f(i,n) {
        if(ans1<(ans^vec[i])) {ans1=(ans^vec[i]);idx=i;}
    }
    f(i,n){
        if(i==idx) continue;
        ans2=min(ans2,(ans1^vec[i]));
    }
    cout<<ans2<<endn;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

where am i going wrong

[himanshu_097]

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

struct Trie {
struct Node {
int count;
int child[2];
Node() {
count = 0;
child[0] = child[1] = -1;
}
};

vector<Node> nodes;
Trie() {
    nodes.push_back(Node()); // root node
}

void insert(int x) {
    int cur = 0;
    for (int bit = 30; bit >= 0; --bit) {
        int b = (x >> bit) & 1;
        if (nodes[cur].child[b] == -1) {
            nodes[cur].child[b] = nodes.size();
            nodes.push_back(Node());
        }
        cur = nodes[cur].child[b];
        nodes[cur].count++;
    }
}

void erase(int x) { // assumes x exists
    int cur = 0;
    for (int bit = 30; bit >= 0; --bit) {
        int b = (x >> bit) & 1;
        int nxt = nodes[cur].child[b];
        cur = nxt;
        nodes[cur].count--;
    }
}

// Returns {minXor, valueThatGivesIt}
pair<int, int> queryMin(int x) {
    int cur = 0, res = 0, val = 0;
    for (int bit = 30; bit >= 0; --bit) {
        int b = (x >> bit) & 1;
        // Prefer same bit to minimize XOR
        if (nodes[cur].child[b] != -1 &&
            nodes[nodes[cur].child[b]].count > 0) {
            cur = nodes[cur].child[b];
            val |= (b << bit);
        } else {
            cur = nodes[cur].child[1 ^ b];
            val |= ((1 ^ b) << bit);
            res |= (1 << bit); // This bit differs
        }
    }
    return {res, val};
}

};

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int T;
cin >> T;
while (T--) {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int &x : A) cin >> x;

    // Build trie and compute total XOR
    Trie trie;
    int X = 0;
    for (int v : A) {
        trie.insert(v);
        X ^= v;
    }

    // Precompute top two (X ^ A[i]) values
    int max1Val = -1, max2Val = -1;
    int max1Idx = -1;
    for (int i = 0; i < N; i++) {
        int val = X ^ A[i];
        if (val > max1Val) {
            max2Val = max1Val;
            max1Val = val;
            max1Idx = i;
        } else if (val > max2Val) {
            max2Val = val;
        }
    }

    int ans = 0;

    for (int j1 = 0; j1 < N; j1++) {
        // Find j2 = index that minimizes (X ^ A[j1] ^ A[j2])
        auto [minXor, val] = trie.queryMin(X ^ A[j1]);
        int best = minXor;

        // Case i1 != j2: Alice picks best max (not j2's max)
        if (val == A[max1Idx]) {
            best = min(best, max2Val);
        } else {
            best = min(best, max1Val);
        }

        // Case i1 == j2: simulate
        trie.erase(val);
        trie.insert(val ^ A[j1]);
        best = max(best, trie.queryMin(X ^ A[j1]).first);
        trie.erase(val ^ A[j1]);
        trie.insert(val);

        ans = max(ans, best);
    }

    cout << ans << "\n";
}
return 0;

}

[ak_fo7]

Editorial pretty difficult to understand after part which says ans = min( x^a[i1] , x ^ a[j1] ^ a[j2] ) .
1 . please think from the perpesctive that change is not done wrt i but j in any operation .
2 . now the cases are :-
a) i1 == j2*
Alice chose what was best for Bob in above formula . now j2* or i1 got changed to a[i1] = a[i1] ^ a[j1] .
Now i1 is not what it was intially which was best for Bob , hence now trie min query .
b) i1 != j2*
let both of them be happy

[ak_fo7]

Also , i think the problem is solvable with binary search too but n * log_{2}^{2} ( n) complexity .