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?

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: http://www.codechef.com/viewsolution/6004281?

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!

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.

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 http://www.codechef.com/viewsolution/6004574

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 :http://www.codechef.com/viewsolution/6004207

use scanf it will pass
http://www.codechef.com/viewsolution/6004729
i used maps

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.