Блог пользователя J_san

Problem D in Codeforces 847 div3 contest
Автор J_san, история, 15 месяцев назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
15 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

→ Ответить
»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 .

→ Ответить
  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить