I solved each query in constant time, Its a very brilliant solution.
https://www.codechef.com/viewsolution/25112004
Each query solves in O(16) i.e O(1)
I declared the data type but it’s not showing over here.
#include<bits/stdc++.h>
using namespace std;
vector v;
int main()
{
long int t,q,x,i,temp,odd,even,ans;
cin >> t;
while(t–)
{
v.clear();
cin >> q;
while(q–)
{
cin >> x;
if (binary_search(v.begin(), v.end(), x))
{
continue;
}
else
v.push_back(x);
temp = v.size();
for(i=0; i<temp; i++)
{
ans = x^v[i];
if(ans == 0)
continue;
else
v.push_back(ans);
}
sort(v.begin(), v.end());
odd = 0; even = 0;
for(i=0; i<v.size(); i++)
{
temp = __builtin_popcount(v[i]);
if(temp & 1)
odd++;
else
even++;
}
cout << even << " " << odd << "\n";
}
}
}
I didn’t get your second point. If x exists in the vector it should not be inserted in the array and I should move further.
def onesInBinary(x):
return bin(x).count(‘1’) % 2
for _ in range(int(input())):
q = int(input())
s = []
e = o = 0
for _ in range(q):
a = int(input())
k = []
if a not in s:
k.append(a)
if onesInBinary(a) == 0:
e += 1
else:
o += 1
for i in s:
z = i ^ a
if i != a and (z not in s):
k.append(z)
if onesInBinary(z) == 0:
e += 1
else:
o += 1
s.extend(k)
print(e, o)
Can anyone explain why I got TLE for 2nd subtask?? (Sorry but I’m not being able to indent it)
because x and elements formed by xor operation already exists in the vector and therefore there is no need for insert operation
You need 17 bits to represent 10^5. It is quite possible that taking the XOR of 2 elements may give an element with all these 17 bits equal to 1. Therefore the maximum value would be 2^17 -1 = 131071. So you can make an array of that size.
e.g. : Let first query be 65536 (10000000000000000 in binary) i.e. 2^16.
Therefore S={65536}.
Let second query be 65535 ( 01111111111111111 in binary) i.e. 2^16-1.
The XOR of 65535 and 65536 is 131071 ( 11111111111111111 in binary) i.e. 2^17 -1 .
Hence you have to take 131072 elements in the array (1 extra for zero).
1 Like
thanks for the detailed explanation.
yeah, even my code. Tried everything in and after the contest but still, nothing seems to be working.
ok so if you look closely at my program which you send the link, the line s=s.union(a) is outside the indentation block of “if n not in s:” . So the statement s=s.union(a) gets executed in all the queries which is not required and so it takes greater time and leads to TLE.
Now if you see the link which i sent that has got AC, you will see that “s=s.union(a)” is placed in the indentation block of " if n not in s:". Hope you can understand what i meant to say!
Yes, you are correct. If x already exists in the vector, you should not do anything. But you still need to show output for that query(which you aren’t doing).
Have a look at this:
Example : For input 4 - 4 2 6 7
The correct output is :
0 1
1 2
1 2
3 4
your output is :
0 1
1 2
3 4
Can anyone help me figuring out why my code is giving TLE.
Here is my code:
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long int
ll EVEN=0;
ll ODD=0;
set sett;
void Count(ll n){
ll s=__builtin_popcount(n);
if(s%2==0) EVEN++;
else ODD++;
}
int main(){
int t;
cin>>t;
while(t){
ll q,x;
cin>>q;
while(q){
cin>>x;
vector v;
v.clear();
set::iterator ptr;
if(sett.find(x)==sett.end()){
if(!sett.empty()){
for(auto it=sett.begin();it!=sett.end();it++){
v.push_back(*it^x);
}
}
}
sett.insert(x);
for(auto it=v.begin();it!=v.end();it++){
sett.insert(*it);
}
EVEN=0;
ODD=0;
for(ptr = sett.begin(); ptr != sett.end(); ptr++){
Count(*ptr);
}
cout<<EVEN<<" "<<ODD<<’\n’;
q–;
}
sett.clear();
t–;
}
}
Thanks for the reply.
https://www.codechef.com/viewsolution/25432974
Can someone tell me where I am going wrong since i am also checking only once before inserting into set?
Thank you!
Here are my two cents:
1.> Use fast input output for problems such as these where the difference between TLE and AC is so small. I implemented that in your code and the execution time improved roughly by 15%.
2.> Instead of taking sets and inserting after checking you can use a boolean array to make the number visited[number]=false; so that next time you dont need to insert same number in the vector therefore doing same thing as sets but more efficiently… why more efficient? It is mainly because set is implemented using red-black trees and the T.C of insert operation in a set is O(logn) while in the array it’ll be O(1). So in the worst case your code will run in O(N x N) instead of O(N x N x logn)… You can check my implementation here, I’ve added comments for better readability.
here’s the code:
https://www.codechef.com/viewsolution/25121488
Moreso, By approach is not very memory efficient so once you have applied the logic , try to do it using arrays instead of vectors or sets… But again , memory constraint is hardly the issue here.
1 Like
#include <bits/stdc++.h>
using namespace std;
bool myset[100001] = {false};
int main(){
int t;
scanf("%d",&t);
while(t--){
memset(myset,false,sizeof(myset[0])*100001);
vector<int> vec;
int n;
bool prev = false;
scanf("%d",&n);
int e=0, o=0;
for(int i=0;i<n;++i){
int q;
scanf("%d",&q);
for(int i=0;i<vec.size();++i){
if(vec[i]!=q) {
prev = myset[vec[i]^q];
myset[vec[i]^q] = true;
if(!prev){
vec.push_back(vec[i]^q);
(__builtin_popcount(vec[i]^q)%2==0)?++e:++o;
}
}
}
prev = myset[q];
myset[q] = true;
if(!prev){
vec.push_back(q);
(__builtin_popcount(q)%2==0)?++e:++o;
}
printf("%d %d\n",e,o);
}
}
return 0;
}
i made the changes its still giving tle.
https://www.codechef.com/viewsolution/25441913
I think you have uploaded a different link 
Thank you for replying 
why the simple code below giving me TLE error? and what is the solution?
#include<iostream>
#include<iterator>
#include<vector>
using namespace std;
int e=0,o=0;
void getParity(unsigned int n)
{
bool parity = 0;
while (n)
{
parity = !parity;
n = n & (n - 1);
}
parity? o++:e++;
}
void func(int q, int x[]){
long long int n=0,l=0;
vector<unsigned int> v;
vector<unsigned int>::iterator it;
v.push_back(x[0]);n++;
getParity(x[0]);
cout<<e<<" "<<o<<endl;
for(int i=0 ; i<(q-1) ; i++)
{
v.push_back(x[i+1]);n++;getParity(x[i+1]);
l=n;
for(int j=0 ; j<(l-1) ; j++)
{
v.push_back(x[i+1]^(v[j]));n++;getParity(x[i+1]^(v[j]));
}cout<<e<<" "<<o<<endl;
}
}
int main()
{ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
e=0;o=0;
int q;
cin>>q;
int x[q];
for(int i=0;i<q;i++)
{
cin>>x[i];
}
func(q,x);
}
return 0;
}[CodeChef: Practical coding for everyone] Yeah I think uploaded a different one… This one is my submission in the contest , you can check!
(CodeChef: Practical coding for everyone)