Set Vs Multiset


#1

I saw a question on codechef,where I used multiset of pairs to solve the problem which gave me TLE(time limit exceeded) but when i submitted the exactly same code with the set of pairs instead of multiset of pairs I got a correct answer verdict AC. I am thinking that the problem with multiset is occuring at the time of input.Is there any difference between the sorting algorithm of set and multiset?or is there anything else which is giving me TLE…Just want to remind again that all the things in my both codes were same except the use of set and multiset…Please help.


#2

u shld hav posted link to ur solution


#3

I think std::multiset has a bigger constant factor than std::set.


#4

Will that diffrence become so large that it will cross 2 sec time limit when the set is performing the same in 0.34 sec?


#5

Oh that’s a big difference. I don’t know what could the reason be then.


#6

Upload the problem link and your solution link


#7

Question link
https://www.codechef.com/APRIL19B/problems/FENCE

Solution using multiset of pairs giving tle using binary search

https://www.codechef.com/viewsolution/23899493

Solution using multiset of pairs using find function giving AC

https://www.codechef.com/viewsolution/23987510


#8

Binary search function on a set has a higher complexity because you can’t access a index in constant /logN time in a set or multiset.