PROBLEM LINKS :
Contest : Division 1
Contest : Division 2
Setter : Pranjal Rai
Tester : Alipasha Montaseri / Kasra Mazaheri
Editorialist : Anand Jaisingh
DIFFICULTY :
Easy
PREREQUISITES :
Properties of Xor.
PROBLEM :
You are initially given an empty set. We get queries to add elements to the set one by one, and when we add element X to the set, we also add element X \oplus Y to the set, for each Y that already belongs to the set.
After each query, print the number of elements having even/odd number of set bits present in the set.
QUICK EXPLANATION :
If in the input queries we get a number X, such that X \not\in S already , then, we add X to the set and go over all elements Y \in S ( already ) and add element X \oplus Y to the set. If we get an input query for an integer X already in S, then we don’t touch the set.
This process works in O(range), where range \approx 2^{17}. When adding an element to the set, we can check it’s parity.
EXPLANATION :
Here, we’ll try and maintain the set mentioned in the problem statement. We can do it in a naive manner by simulating the exact words mentioned in the statement, each time we add a new element, we go over the entire set of existing elements again.
The complexity of such a solution is not good enough to get a full score, and is bounded below by O(N^2) .
What is desirable is that we construct a solution in which each element is checked for new addition to the set no more than once. Such solutions would guarantee us a run-time of as good as O(N). In fact, we can using the 2 claims given below, indeed construct such a solution
Claim 1 :
If element x is in the set and element y is in the set, then element x \oplus y is also in the set. This is a necessary condition, that is ensured after we prove claim 2.
Claim 2 :
If element x is not in the set and element y is in the set then element x \oplus y cannot be in the set. This could be proved by contradiction. Assume x \oplus y is in the set, then, by the first claim, (x \oplus y) \oplus y must be in the set. This is equivalent to x which we said that it isn’t in the set. Therefore, x \oplus y isn’t in the set.
Using these 2 crucial observations, we construct a solution in which, when adding a new element x not already present in the set, we go over all elements y already existing in the set and add x \oplus y to the set since its guaranteed it’s not already present in the set.
When adding a new element x \oplus y to the set, there is no need to go over all elements of the set again and add elements that may be of the form (x \oplus y) \oplus z, since we have already added the same elements in the form x \oplus ( y \oplus z ) to the set.
This process ensures claim 1
In such a manner, we go over each element added to the set no more than once.
Now, while adding each new element to the set, we can check the parity of its bit count, and maintain and print the answer accordingly
The complexity is of this solution is O(Q+Max.Val), where Max.Val \approx 2^{17}.
Your comments are welcome !
COMPLEXITY ANALYSIS :
Time Complexity: O( T \cdot ( Q+val) ) , where val \approx 2^{17}
Space Complexity : O(val)
SOLUTION LINKS :
Setter
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
//ifstream fin ("input5.txt", ifstream::binary);
//ofstream fout ("output5.txt", ofstream::binary);
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll t;
cin>>t;
set<ll>::iterator it;
while(t--)
{
ll n;
cin>>n;
set<ll> s;
ll e=0,o=0;
while(n--)
{
ll x;
cin>>x;
if(s.find(x)!=s.end())
{
cout<<e<<" "<<o<<"\n";
continue;
}
set<ll> temp;
for(it=s.begin();it!=s.end();it++)
{
ll y=*it;
ll val=(x^y);
ll cnt=__builtin_popcount(val);
if(cnt%2)
o++;
else
e++;
temp.insert(val);
}
for(it=temp.begin();it!=temp.end();it++)
{
s.insert((*it));
}
s.insert(x);
ll cnt=__builtin_popcount(x);
if(cnt%2)
o++;
else
e++;
cout<<e<<" "<<o<<"\n";
}
}
return 0;
}
Tester
# include<bits/stdc++.h>
using namespace std;
const int N = 200000 + 77;
int T;
int q , M[N] , odd , even;
inline void Test() {
memset(M , 0 , sizeof(M));
M[0] = 1;
odd = even = 0;
scanf("%d" , & q);
while(q --) {
int x;
scanf("%d" , & x);
if(M[x] == 0)
for(int i = 0;i < 131072;++ i)
if(M[i] == 1 && M[i ^ x] == 0) {
M[i ^ x] = 1;
int cnt = __builtin_popcount(i ^ x);
odd += cnt & 1;
even += (1 - (cnt & 1));
}
printf("%d %d\n" , even , odd);
}
}
int main() {
scanf("%d" , & T);
while(T --)
Test();
return 0;
}
Editorialist
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
// Anand Jaisingh
#include<bits/stdc++.h>
using namespace std;
typedef complex<double> base;
typedef long double ld;
typedef long long ll;
#define pb push_back
#define pii pair<int,int>
#define pll pair< ll , ll >
#define vi vector<int>
#define vvi vector< vi >
const int maxn=(int)(2e5+5);
const ll mod=(ll)(1e9+7);
int a[maxn];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
int t;cin>>t;
while(t>0)
{
int q;cin>>q;
set<int> s1;int cnt=0;s1.insert(0);
for(int i=0;i<q;i++)
{
int x;cin>>x;
auto z=s1.find(x);
if(z!=s1.end())
{
cout<<(s1.size()-cnt-1)<<" "<<cnt<<endl;
continue;
}
vector<int> v;
for(int z:s1)
{
// cout<<"hello "<<z.first<<endl;
v.pb(z^x);
}
for(int z:v)
{
if(__builtin_popcount(z)%2==1)
{
cnt++;
}
assert(s1.find(z)==s1.end());
s1.insert(z);
}
cout<<(s1.size()-cnt-1)<<" "<<cnt<<endl;
}
t--;
}
return 0;
}