asimaries's blog

Why TLE?
By asimaries, history, 2 years ago, In English

https://mirror.codeforces.com/contest/1691/submission/159098417

Why does this solution fail on test 30 (TLE)? this is an O(n) solution and also this shouldn't have run more then O(1) time complexity.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

This TLE is repeated more and more nowadays in codeforces and the reason is same.
I just replace unordered_map with map and it get accepted
unordered_map cause TLE because of its bad hashing function, but to override this you can check this blog for most efficient custom hashing.

upd: accepted code using unordered_map with custom hash.

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

    Thank you very much I thought using using unordered_map will give me a lesser time complexity

    → Reply