Chiefash's blog

By Chiefash, history, 3 months ago,

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.

• 0

 » 3 months ago, # |   +4 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)
 » 3 months ago, # |   0 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.
•  » » 3 months ago, # ^ |   0 This happens when there is a lot of collisions of the hashes? There is no way to be sure about it being O(1)?
•  » » » 3 months ago, # ^ |   0 Apparently, no. But by applying safe hash you can significantly reduce the number of collisions and speed up the runtime
 » 3 months ago, # |   0 Since all elements distinct just use set or multiset(the best stl ds in the world)
•  » » 3 months ago, # ^ |   0 When can I be sure to use unordered_set in general to achieve O(1).
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +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 upIn competitive programming – generally when there's no hacks available, because problemsetters usually don't try to blow up hashesAt Codeforces – basically never (because of hacks) unless you use custom hash function
•  » » » » 3 months ago, # ^ |   0 Thanks