Tags: algorithms xor graphs
Rating: 5.0
[If the LaTeX isn't rendering, try refreshing the page.]
## Problem Statement
By convention, we use $\oplus$ to denote the XOR operation.
Consider a 1-indexed array $A$ of $n=10^5$ integers, where each integer $x$ satisfies $0\leq x\leq 2^{31}$.
You are given $t=10^5$ constraints with values $l$, $r$ and $v$. Each constraint indicates that the XOR-sum from $A_l$ to $A_r$ (in other words, $A_l\oplus A_{l+1}\,...\,\oplus A_{r}$) must be equal to $v$.
Find an array $A$ that satisfies these constraints.
## Solution
Let $P_i$ be the _prefix XOR-sum_ to index $i$ -- in other words, $P_i=A_1\oplus ... \oplus A_i$ (and $P_0=0$).
Now, as $x\oplus x=0$, notice that the XOR-sum from $A_l$ to $A_r$ is given by $P_{l-1}\oplus P_r$.
So we can now convert each of our constraints into the form $P_{l-1} \oplus P_r = v$, and we are now left with the following problem: given a set of XOR constraints of the form $P_i \oplus P_j = v$, find values for $P$ to satisfy these constraints. (Notice that there may be values $P_i$ that are not involved in any constraints -- we can simply set these to some arbitrary value -- e.g. 0.)
Consider the graph whose nodes are elements of $P$, and two nodes $P_i,P_j$ are connected by an edge with weight equal to $v$ iff there exists a constraint $P_i \oplus P_j = v$.
Now consider some arbitrary node $P_i$ in the graph. Assuming the set of constraints is satisfiable, any path from $P_i$ to any other node $P_j$ in its connected component will yield the value of $P_j$ if we take the XOR-sum of the weights of the edges we traverse. So we can determine the values of all the nodes in $P_i$'s connected component such that all the conditions in that connected component are satisfied, in terms of $P_i$ -- arbitrarily setting $P_i$ to zero yields one possible set of values that satisfy the constraints.
So we have an algorithm to solve the problem: for each connected component in the graph, set the value of one node arbitrarily to zero, and perform a depth-first search, updating the values of nodes by XORing with edge weights as we go.
Once this is done, taking the XOR-difference $P_{i-1} \oplus P_i$ for each pair of adjacent elements in $P$ will yield an array $A$ that satisfies all conditions (in other words, $A_i = P_{i-1} \oplus P_i$).
The following code was used to solve the problem:
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> prefxor;
vector<vector<pair<ll,ll>>> adjlist; //node, weight
void dfs(ll x){
for (auto p : adjlist[x]){
if (prefxor[p.first]==-1){
prefxor[p.first]=prefxor[x]^p.second;
dfs(p.first);
}
}
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cerr<<"starting\n";
ll n = 100000;
prefxor.resize(n+1,-1);
adjlist.resize(n+1);
for (ll i = 0; i<n; i++){
ll l,r,v;
cin>>l>>r>>v;
l--;
adjlist[l].push_back({r,v});
adjlist[r].push_back({l,v});
}
cerr<<"received input\n";
for (ll i = 0; i<n+1; i++){
if (prefxor[i]!=-1){continue;}
prefxor[i]=0;
dfs(i);
}
for (ll i = 0; i<n; i++){
cout<<(prefxor[i]^prefxor[i+1])<<'\n';
}
cerr<<"sent output\n";
string s;
cin>>s;
cerr<<s<<'\n';
}
```
and run with the following shell commands:
```
g++ -o expohash expohash.cpp
mkfifo fifo
nc 2020.redpwnc.tf 31458 < fifo | ./expohash > fifo
```
Writeup by [eohomegrownapps](https://ctftime.org/user/81813)