PTMSSNG - Different answers on using MAP and UNORDERED MAP

Using Unordered map- https://www.codechef.com/viewsolution/35479887
Using just map - https://www.codechef.com/viewsolution/35479985

Using unordered map i am getting some testcases wrong. But using ordered map i am getting all testcases passed. I know that unordered map uses concept of hashing and ordered map uses trees. But why different answers? Please help me I am not able to figure it out.
Thanks!

1 Like

Ordered Map has a complexity of O(logn) in worst case where as Unordered Map has average complexity of O(1) but O(n) in worst case. Hence here you get a TLE.

3 Likes

Take this as a note, whenever you use unordered_map, always use custom_hash along with it. Here is your AC code with custom_hash. You can read more about it here

4 Likes

I had the same problem. I just reserved some space for my unordered_map and TLE turned into AC.
Without reserving: https://www.codechef.com/viewsolution/34975044
With reserving: https://www.codechef.com/viewsolution/34975500

3 Likes

The blog link you provided was nice. It cleared my doubts regarding unordered maps. Thank You!

1 Like