PROBLEM LINK:
Setter: Mohammad Solaiman
Tester: Teja Vardhan Reddy
Editorialist: Teja Vardhan Reddy
DIFFICULTY:
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
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int bad[123],gg[123];
int k,taken;
int addelem(int val){
int i;
rep(i,k){
if(val&(1<<i)){
if(bad[i]){
val^=gg[i];
}
else{
gg[i]=val;
bad[i]=1;
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){
bad[i]=0;
}
int val;
rep(i,m){
cin>>val;
addelem(val);
}
comps=k-taken;
cout<<(1<<comps)<<endl;
}
return 0;
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 