abhinavawasthi's blog

unordered_map gives TLE? UMAP vs MAP
By abhinavawasthi, history, 3 years ago, In English

Yesterday, I have participated in codeforces round 773.

Was able to solve the first three questions during the contest, but my B and C submission got TLE on System Cases, do you know why? Just because I have used unordered_map instead of map.

I think, this is practical example to examine the diff btw unordered_map and map.

The same code with the same logic gives TLE, when using UMAP but got accepted, when using MAP.

1642B - Power Walking Submission with UMAP: submission:147440230

1642C - Great Sequence Submission with UMAP: submission:147426920

1642B - Power Walking Submission with MAP: submission:147497381

1642C - Great Sequence Submission with MAP: submission:147497320

One of my codeforces friends also told me about this, with a very good resource attached, you can check it.

Any suggestions are welcomed!

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's always better to use simple Map instead of Umap i guess

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No Unordered map is faster than normal map.(for safety use custom hash function)

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I used unordered map with custom hash and got Ac.check my submission

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So using custom hash reduces the the collision chances and the worst case happening probability even further ? From your implementation can it be used for only unsigned 32 or 64 bit int or can we make it even for strings ?

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Before making a blog on codeforces try googling "$your_subject codeforces". In your case google "unordered_map codeforces" and you will find many blogs on the subject. In particular there is this one that explains what is going and how to hack unordered_map.

→ Reply