Chiefash's blog

Why unordered_set and unordered_map are giving me TLE but lower bound isn't.
By Chiefash, history, 6 months ago, In English

I was trying to solve problem C in Educational Codeforces Round 159 (Rated for Div. 2).

Here I just wanted to check if the value i is not present in the array. I tried using three things 1. I created an unordered_set of all elements in the array and used !s.count(i) to check if the value is present or not? 2. I created an unordered_map of all elements in the array and used mp[i] == 0 to check if the value is present or not 3. Finally I used lower_bound function on the array to check if the value is present or not.

I got TLE on first two but accepted in third. Can someone please explain why is this happening. I don't want to make the same mistake again in the contest.

I am adding images for all examples.

image1 image2 image3

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

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I believe this blog should be helpful here.
Here is your original code and here is code with little modification (added custom_hash in unordered_map)

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

Here, the lower_bound method has a complexity of $$$O(\log N)$$$; unordered map and set have an amortized complexity of $$$O(1)$$$, but they can be blown up to $$$O(N)$$$ with hack tests.

Lower_bound is consistently fast (enough so it gives you AC), but the other 2 aren't unless you apply safe hash as mentioned above.

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

    This happens when there is a lot of collisions of the hashes? There is no way to be sure about it being O(1)?

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

      Apparently, no. But by applying safe hash you can significantly reduce the number of collisions and speed up the runtime

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

Since all elements distinct just use set or multiset(the best stl ds in the world)

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

    When can I be sure to use unordered_set in general to achieve O(1).

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      In real life – when you know that the data that you put in the map/set can't be such that map/set blow up

      In competitive programming – generally when there's no hacks available, because problemsetters usually don't try to blow up hashes

      At Codeforces – basically never (because of hacks) unless you use custom hash function

      → Reply