TLE using sets

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? :stuck_out_tongue: 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.