 # XORCMPNT - EDITORIAL

Practice

Contest: Division 1

Contest: Division 2

Tester: Teja Vardhan Reddy

Editorialist: Teja Vardhan Reddy

Medium

# PREREQUISITES:

Gaussian Elimination in modulo field, xor base.

# PROBLEM:

Given an array A of n numbers x_1,x_2,...x_n.Consider all the vertices numbered 0 to 2^k-1. Add edge from each vertex i to (i \oplus x_j)\forall_{j=1}^n. Now count the number of connected components in the graph obtained.

# EXPLANATION

• From a vertex u, a vertex v is reachable if and only if there exist a subset S of the given array A such that xor of all the elements in S is equal to u \oplus v. Note that u is always reachable from u according to this because u \oplus u = 0 which can be obtained by taking empty set.

• Now, for two values p and q such that p \neq q, u \oplus p \neq u \oplus q.
Proof: Assume they are equal, then xor both sides with u, we will get p = q which is a contradiction.

• Let set M be set of all the subset xor values of the given array A.M does not have duplicates. Let i th element of M be m_i. So all the vertices which are reachable from u will be u \oplus m_i for all i from 1 to size(M). Now, size of component of u is size(M) (because all above vertices u \oplus m_i are distinct as proved previously). The above result is true for any u from 0 to 2^k-1. Hence each vertex belongs to a component of size size(M). Hence, number of components is 2^k/size(M).

• Now we are left with computing size(M). We want size of space spanned by A in modulo 2 field which will be nothing but 2^{size(basis of A)}. We need to compute the basis of A which is quite standard with Guassian Elimination.

• Some insight into finding basis:
We want to maintain a number for each bit which activates or deactivates that bit without altering below bits. So we iterate over all the numbers, and start from bottom bit and go to top bit, while iterating following cases might arise

Case 1: Current bit has number set. So now we have to make this bit in current number zero (if its already zero do not do anything otherwise make it zero by xor with number responsible for that bit).

Case 2: Current bit has no number set. Now if current number has that bit active, make it responsible for this bit and move to next number otherwise move to next bit.

And finally all the responsible numbers for the basis.

Code snippet for finding basis
``````int addelem(int val){
int i;
for(i=0;i<maxbits;i++){
if(val&(1<<i)){
if(alloted[i]){
val^=responsible[i];
}
else{
responsible[i]=val;
alloted[i]=1;
break;
}
}
}
return 0;
}
``````

Alternate tutorial for finding basis in modulo 2 field

# TIME COMPLEXITY

While finding basis , each number in the array is checked for each bit. Hence, each number takes O(k) time.
Finding basis takes O(n*k) complexity. rest is O(1).
Hence total complexity is O(n*k)

# SOLUTIONS:

Setter's Solution
``````/// author's solution

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

int gaussElimination(vector<int>v, int k)
{
int i = 0;
for (int j = 0; j < k; j++) {
int l;
for (l = i; l < v.size() && ((v[l]>>j)&1)==0; l++);
if (l==v.size()) continue;
if (l > i) swap(v[i], v[l]);
for (l = i+1; l < v.size(); l++) if (v[l]&(1<<j)) v[l] ^= v[i];
i++;
}
return i;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
//    freopen("input13.txt", "r", stdin);
//    freopen("output13.txt", "w", stdout);

int t;
cin >> t;

for (int ti = 1; ti <= t; ti++) {
int k, m;
cin >> k >> m;

vector<int>v(m);
for (int i = 0; i < m; i++) cin >> v[i];

int r = gaussElimination(v, k);
cout << (1<<(k-r)) << "\n";
}

return 0;
}
``````
Tester's Solution
``````//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;

#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983

// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

int k,taken;
int i;
rep(i,k){
if(val&(1<<i)){
val^=gg[i];
}
else{
gg[i]=val;
taken++;
break;
}
}
}
return 0;
}
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int m,comps;
cin>>k>>m;
int i;
taken=0;
rep(i,k){
}
int val;
rep(i,m){
cin>>val;
}
comps=k-taken;
cout<<(1<<comps)<<endl;
}
return 0;
}
``````

Feel free to Share your approach, If it differs. Suggestions are always welcomed. 2 Likes

Can someone please explain the last part a bit more?

• How the problem of computing size(M) get reduced to space spanned in modulo 2 ?
• “We want to maintain a number for each bit which activates or deactivates that bit without altering below bits.” What if we use the same number before (i.e. in setting or unsetting some lower bits) and we use the number again?

If someone has then please share some blog post or some similar problems.

2 Likes

1 Like

@pk301 size(M) basically represents every unique xor value which can be achieved by taking any subset of array A and xoring all values in it.
Thus size of M will be 2^(size(basis of A)) because every basis vector of A can either be taken or not taken.That’s why size(M) == 2**(size(basis of A)).
I hope it makes sense!!!

This is for someone who had trouble understanding the 3rd point in the explaination above.

In this, in order to find the connected component of any vertex (note that connected component means that if a->b->c then {a,b,c} form one connected component). In the question they have given that for all the elements of array A (x1, x2, …, xn), if a⊕b = xi, then a and b are connected meaning a->b edge is there. So, in order to find the connected components for a, we would also need all the edges originating from b (excluding the one with node a ofcourse).

In order to find this, we have used the newly created set M (same notation as the editorial). Basically if a⊕b = xi and b⊕c = xj, and we need to find such c, then
Taking xor of both of the above equations we have
=> a⊕b⊕b⊕c = xi⊕xj
=> a⊕c = xi⊕xj
Similarly let’s say c is connected to d meaning, c⊕d = xk (this means that connected component will have {a,b,c,d}). So in order to find d using the above method, we can reach the equation
=> a⊕d = xi⊕xj⊕xk
and so on.
This means that we need to consider the set of all possible xors of the given array A (which is taken to be M in this case).
Thus taking xor of a with each element in M, will give all the nodes which are directly reachable from a (hence the connected component of a).
NOTE: We are only concerned with the number of connected components and not the actual components.

Now p number of nodes are counted in 1 component.
So, 2^k number of nodes will be counted in => (1/p)*(2^k)
p is nothing but the size of the set M.
Therefore the number of connected components => 2^k/size(M).

4 Likes