This is a very simple question, I tried this because I thought searching in the set takes logarithmic time, thinking it’ll pass easily. Why it is giving TLE?
std::set has a huge constant factor because it implements a binary search tree. The constant factor is not to be underestimated. Never use set when it is not strictly necessary. Consider reading this article: http://lafstern.org/matt/col1.pdf
Edit: same applies to map.
use scanf it will pass
http://www.codechef.com/viewsolution/6004729
i used maps
You didn’t need an ordered set as the input is already lexicographically sorted. Each insertion in set takes O(logn) time, making it O(nlogn*|s|), which is quite big!
Then, what in this: CodeChef: Practical coding for everyone?
Also, every insertion in set takes logn time, thus n*logn- complexity f insertion which can maximum be 1000log(100) which is 2000, now searching takes logn, which can maximum be log(100)=2. These much operations can be executed in 1 sec easily I suppose.
@damn_me: There are 1000 test cases as well.
1 Like
^^ also tles as expected, insertion in map is O(logn) aswell!
As I can see in your code, you are nowhere calling binarysearch function or m i missing something?
sorry i gave the wrong link. pls check here CodeChef: Practical coding for everyone
this guy’s solution got accepted using a map. He has used scanf instead of cin
http://www.codechef.com/viewsolution/6004729
It’s also the case in one of my solution, but the only difference I see in ACed ones, is the use of scanf() etc and strcmp(). Nothing else… Try changing to that once…
wHAT IS wrong with this :CodeChef: Practical coding for everyone
just the difference of scanf and cin
In this case the problem seems to be slow IO.
But everything I said still applies and I wouldn’t recommend using a set when sorting an array and doing binary search works.
In your code also I suppose? 
This is just kind of damn thing, oh damn_me, we spend so much of time thinking where we went wrong and then the mistake which comes out to be is this “use scanf() and u’ll get AC”!!!
I didn’t participate in this contest.
Just always use scanf and you won’t come across such errors.
Yeah, I know, and i always try my TLE submission replacing it with scanf(), this was just a by chance that I didn’t try it again and that was the only thing I was supposed to do.