J_san's blog

Problem D in Codeforces 847 div3 contest
By J_san, history, 15 months ago, In English

problem:D Most of the time i use UNORDERED MAP because it takes O(1) time, but while solving this problems, it is actually giving TLE, while on the other hand if you use ORDERED MAP which takes O(logn) time, is getting accepted.I don't know why? Can anyone please explain the reason and also how to decide in advance which to use?

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

Comments Comments (3)
| Write comment?
»
15 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Blowing up unordered_map, and how to stop getting hacked on it

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This Query has been asked and answered many times on CF itself . Unordered Map is implemented using Hashtable which involves collisions if size of inputs is large and also high number of testcases which becomes very slow i.e. O(n) for find method whereas Map is implemented using Binary search trees in which find method works with O(logn) time complexity . So for small value of inputs and less testcases Use Unordered Map whereas for large number of testcases use map . On leetcode use unordered map while on codeforces use Map . Hope it answered your query .

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

    Not true. Even with massive input sizes, unordered_map still does all queries in $$$O(1)$$$ unless the input has been specifically created to cause as many hash collisions as possible. You should read this.

    → Reply