Set in C++ STL == Binary Search Tree, and in binary search tree all operation takes O(logn)
Hey @anand20 why my code is not working please tell me?
I am getting only partial points
anybody can cast the vote but please tell me where I am going wrong.
hey I seem to use the same logic can someone help me as to why my code gets a TLE
for the 2nd subtask
link-CodeChef: Practical coding for everyone
I too got TLE in 2nd sub task as long as I used find() function. Then, I modified my approach and used a 2D array to keep track of elements which are already present in the set. Also, it takes O(1) to check for duplicacy everytime!
Here is my solution and I hope it helps 
1 Like
What is the size of flag array you have made?
I think you have made the flag array of lesser size as compared to the range of the elements in the set. The size of flag array should be 131,072 (maximum value any element can take in the set) or more.
Hope this clarifies your doubt.
Complexity should be beyond 10^10 in my view . How is it not giving tle? In tester’s solution, time complexity is O(tq131072) which should give tle, isn’t it?
I found that optimisation too but i couldnt figure out how to maintain the set
I have a doubt, In C++ does list is faster than Vector? My code is showing tle for three subtasks and i have used vector instead of list.
Store the result in a StringBuffer and print it at the end.
As there is 10^5 query and printing via SOUT takes a lot time so storing and printing will solve it.
I have submitted your code via this and it got AC. Here is the link
https://www.codechef.com/submit/complete/25328382
assert(s1.find(z)==s1.end())
what is use of assert in c++
??
Can you explain me one thing in your solution. When you are taking array of 140000 length it is giving TLE but AC when you are taking array of length 100001. Why??
Can anyone help me. Why am I getting WA, everything seems to be fine.
#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";
}
}
}
Do you know why it passed all the testcases???
Because you used set. This is your solution implementation without set and see it gives TLE.
You got very lucky man and please thanks me for finding this out.
1 Like
First of all, vector must be declared as vector <data_type> v, you didn’t mention the data type above( I believe it is a typing error )
Next, after taking x as input and performing a binary search, if u find that x already exists in v, you used continue - but for AC you still have to show an output for that query( which is same as previous output )
Even after fixing these issues, if you are still getting TLE in some test cases, I recommend using a 2D array to check for duplicacy.
1 Like
https://www.codechef.com/viewsolution/25052113
I got TLE like this before 
So i optimized the algo a bit and got AC
Ok so first of all, in the question it says that X is <=100000, and as indexing in list starts from 0 so one more is needed, or else if X = 100000, the solution will get list index Out of Range Error.
And Secondly, if i use 140000, It is not giving TLE, Link to the accepted Solution. Please reply attaching the solution that is giving TLE, I may help you debug where the implementation is going wrong! 
Well can you look at my approach?
I mean i posted my two solutions.
The one which got AC…
why are you adding and appending to a set at the same time ? 
I mean adding would save you a lot of time and optimised the problem itself,
And by the way you are using brute force to be precise and you have optimised to an extend.
Try finding what happens when :
- When a number with even number of set bits is xored with a number with even number of set bits
- When a number with even number of set bits is xored with a number with odd number of set bits
- When a number with odd number of set bits is xored with a number with odd number of set bits
This would optimise the solution to a great extend!!
1 Like
@manas_0
Coud you please clarify the below statement.
“The size of flag array should be 131,072 (maximum value any element can take in the set) or more.”
cos In question, the maximum value any element can take in the set can be 10^5. Is there any need to traverse extra elements and store extra elements in the binary map?