PTMSSNG - Different answers on using MAP and UNORDERED MAP

help
1

Using Unordered map- CodeChef: Practical coding for everyone
Using just map - CodeChef: Practical coding for everyone

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
2

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
3

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
4

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
5

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

1 Like