DimmyT's blog

Why I have TL?
By DimmyT, history, 7 years ago, translation, In English

On task 977F - Последовательная подпоследовательность I have a TL on solution with unordered_map 37945413 but exactly the same solution with map instead of unordered_map 37989920 I have passed. This is not an error because unordered_map faster map, right?

UPD: I just translated to Eng

UPD1:

Everything about unordered_map:

https://mirror.codeforces.com/blog/entry/62393

https://mirror.codeforces.com/blog/entry/21853

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

»
5 years ago, # |
← Rev. 2   Vote: I like it -35 Vote: I do not like it

Why so much dislikes?

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

Good amount of discussion on this same topic can be found here. Read all comments.

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

The worst case time complexity of operation in unordered_map is O(n) rather than the expected O(1),moreover the complexity of unordered_map is amortised O(1) ,whereas for map is O(log n). Similar thing had happened to me earlier.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it -15 Vote: I do not like it

    In which cases, unordered_map works O(N)? Could tell me about this?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Sorry,I don't know any specific case as such. But I am sure there are set of test cases which can make them happen everytime as the hash function which unordered_map uses is known ans thus the cases which produces more and more collisions are bound to produce TLE verdict.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      https://mirror.codeforces.com/blog/entry/62393

      → Reply