PRTAGN - Editorial

PROBLEM LINKS :

Contest : Division 1

Contest : Division 2

Practice

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;
}
9 Likes

This is very disappointing as the same logic seems to be giving TLE in the Java8. You are making language a barrier in a coding contest. My (and many more like me) similar logic code failed to even accept anything else than ‘q’ queries. I am saying so because every accepted code is either in C/C++ or Python and none in Java i guess.

I hope you look in this matter

7 Likes

It isn’t. I didn’t got TLE in kotlin. There multiply TL by factor that depends on language.

Try in java it doesn’t accept a simple print statement after q queries.

How it passed in python, python is kinda slower than java

1 Like

I used the similar approach as you have written in both of the claims above.I have used a flag array to mark the elements present in the set.So i check whether the given element is present in the set by O(1) and if not then i go on adding x^y to the set(flag array).Its passing some test cases from sub task 2 but the last three…I am getting SIGSEGV. I am a newbie seeking for help.

Yes, It is giving TLE in jav…

I have used exactly what you’ve done. My code has AC. Providing the link below.
Link :: CodeChef: Practical coding for everyone

1 Like

Its funny how just for one question i looked up all the properties made for xor, and in the end all i was missing was some optimization :laughing:
Anyways it was a cool and fun question, kinda sad for the Java Guys :frowning_face:

8 Likes

I’ve avoided using find() due to its high time complexity it gives TLE in Subtask 2 when I tried. Here’s an alternate solution. Take an array initialized to 0 and flag the arr[query] and array[XOR] as 1 progressively while entering each query and taking the XORs. This keeps a check of duplicates in O(1):
CodeChef: Practical coding for everyone

1 Like

In case of Set STL, find() takes O(log n ) i believe :thinking: So i think it would have worked?

No man even my solution in python with same approach is giving TLE. I used BST

I have use diff approach for this question. i use the property that is if two numbers with same parity is xor the resultant will be always even parity and if two numbers with diff parity is xor then resultant will be odd parity.
i m not good at finding time complexion but if the duplicates can be handled better, my code just take O(q) time, i m not sure tho.
here is my code…its not properly written tho XD.
https://www.codechef.com/viewsolution/25127014

1 Like

https://www.codechef.com/viewsolution/25313227
i did it this way . it got accepted also ,but i am not able to understand time complexity, i think i did it as same as in the editorial,but if you calculate worst case time complexity of my code it comes like following for a given test case
First i enter element 1 in the set it directly inserts it,
then i enter element 2, it calculates xor with 1, and insert 2,
then i enter element 3, it calculates xor with 1,1^2,2 and then insert 3,
so if any point of time if for inserting n th element i am performing 2*(n-1)+1 operations = 2*n -1 operations for if i perform that for every element where n is belonging to 0 to n,the worst case time complexity will be of order O(N^2),so it should not get accepted .Pls tell me if I am doing something wrong in my time complexity calculation.

4 Likes

Here is my solution based on the given editorial, the trick is if you optimise your solution and implement the algorithm correctly you will get AC. Here is my solution. I found a pattern how the number of odd and even terms are increasing when n is odd and when is even. This optimised my solution and got AC.

2 Likes

Even i was frustrated as i was getting TLE for some of the cases of the 2nd subtask for 2 days and my solution was optimal to the best possible way but then i suddenly realised something and changed the set i was using to an unordered_set and it got accepted and this is because insertion and other operations in set takes O(logn) becuase it uses BST for its implementation while unordered_set uses hashtables which give O(1) time complexity.

1 Like

Well this was my solution
https://www.codechef.com/viewsolution/25057831
I was surprised it passed the test cases…

1 Like

MySolutions
using Set - CodeChef: Practical coding for everyone
using bool vector and maps of pair- CodeChef: Practical coding for everyone

1 Like

It got accepted in java also.
Here is my solution CodeChef: Practical coding for everyone
In my opinion language is not a restriction in CP.

The test cases were very weak in the question as the actual complexity of this solution would O(q.s.size()). The test cases were weak so it the sol got accepted but where all the size of set is 10^4 and the X insert greater than 10^4 the the sol wouldn’t work.