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.
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)
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.
This happens when there is a lot of collisions of the hashes? There is no way to be sure about it being O(1)?
Apparently, no. But by applying safe hash you can significantly reduce the number of collisions and speed up the runtime
Since all elements distinct just use set or multiset(the best stl ds in the world)
When can I be sure to use unordered_set in general to achieve O(1).
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
Thanks