Infinite.Loop's blog

Solution with unordered_map giving TLE gets accepted with ordered_map
By Infinite.Loop, history, 4 years ago, In English

This is my solution when I used unordered_map.

This is my solution when I used ordered_map.

It is seen that unordered_map performs better than ordered_map so how can TLE get resolved with ordered_map but not with unordered_map???

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The hashing is not perfect and with specific test cases, every find, insert etc. works in O(n) instead of O(1). Refer to this for more detail.

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

    But here all keys are ints and not int64_t/long longs, so their hashes do not (should not?) collide, so what's the real reason?

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

      https://codeforces.me/blog/entry/62393 this might help??

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

      If you look at the TLE testcase, it's pretty obvious what's going on: The input consists of exactly the multiples of 53201. They have different hashes, but these hashes all get mapped into the same bucket when the unordered map reaches the right size. Only the latter is needed for the bad worst-case performance of unordered_map to occur.

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

        yes, thank you, we figured this out in another thread too, I forgot about the % bucket_count part

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

        so should we avoid using unordered_map in contests and stick to map or use some custom hash with unordered_map like this.

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

          Using unordered_map with default hash on Codeforces is just begging to get hacked or fail system tests. What you do instead is up to you. Options include:

          1. Using (ordered) map: This takes no effort to set up and is fast enough most of the time (with obvious exceptions).
          2. Using unordered_map with a randomized custom hash function. This is OK and not very inconvenient to set up even without any pre-written code.
          3. Using a hand-rolled or library policy-based hash table, with a randomized custom hash function. This will give by far the best runtime performance.
          → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
| map             | unordered_map

Ordering | increasing order | no ordering | (by default) |

Implementation | Self balancing BST | Hash Table | like Red-Black Tree |

search time | log(n) | O(1) -> Average | | O(n) -> Worst Case

Insertion time | log(n) + Rebalance | Same as search

Deletion time | log(n) + Rebalance | Same as search

so the answer of your problem is in worse case unordered_map uses O(n) for each insertion .So your insertion in the testcase no 12 will take upto O(n^2) in your unordered map ,but it will take only O(nlog(n)) in map.

→ Reply