Tenz1n's blog

TLE while using unordered_map<> but AC when using mp.find() function
By Tenz1n, history, 10 months ago, In English

I was solving the problem : 1732D1 - Balance (Easy version). And my solution was same as i keep the track of the kth-MEX of the xth element when ever the request has been made. So for checking whether the kth element is present in the set or not, i used unordered_map<> by while adding the elements in the unordered_map<> when the add operation is processed. But i got TLE at test 36. Later when i checked other's solution they used ordered_map<> and used the .find() function to check whether the element is added to the set or not. And then i also used that .find() function and it got accepted.

Can anyone help tell me why by using mapping with unordered_map<> gives TLE and get Accepted while using .find() function?

Submission 1 : 223430749 Submission 2 : 223513656

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Read this blog: https://codeforces.net/blog/entry/62393

→ Reply
»
10 months ago, # |
  Vote: I like it +2 Vote: I do not like it

There is performance difference between std::unordered_map and std::map in terms of finding elements and to understand this you need to know the internal implementation of these data Structures.

  1. std::unordered_map:
  • std::unordered_map is implemented as a hash table, where elements are stored in buckets based on their hash values. When you perform a find operation in an unordered_map, it has an average time complexity of O(1), assuming a good hash function and a low collision rate.
  • However, in some worst-case scenarios, particularly when there are many hash collisions, the time complexity can degrade to O(n), where n is the number of elements in the map. This happens because all elements in the same bucket need to be examined linearly to resolve the collision.
  1. std::map (ordered_map):
  • std::map (or std::ordered_map) is implemented as a balanced binary search tree (usually a Red-Black Tree). This data structure maintains the elements in sorted order based on their keys.
  • The find operation in a std::map has a time complexity of O(log n), where n is the number of elements in the map. This is because it performs a binary search on the tree structure to locate the element.

So, why might you observe a TLE (Time Limit Exceeded) when using std::unordered_map::find but not when using std::map::find?

The most likely explanation is that your std::unordered_map is experiencing worst-case behavior due to hash collisions. In cases where there are many hash collisions (e.g., if your hash function is not well-distributed or if you have a lot of elements with the same hash), the std::unordered_map can degrade in performance and, in the worst case, become slower than a std::map for finding elements. This can lead to TLE errors.

→ Reply