I implemented the same idea as the editorial in 3 different ways.
Using stl:map : submission
Using stl:unordered_map: submission
Using stl:lower_bound: submission
I have no idea why map would give TLE and lower_bound will not, both costs O(logn). Given that lower_bound solution passes in just 312 ms, I expect map solution to pass even if runtime is a bit higher. And why on earth would unordered_map give a runtime of 1341 ms? It was supposed to be of O(1) cost. I am certain my hash_function has absolutely no chance of colliding.
Can anybody explain this behaviour...
I stumbled upon the exact same problem few weeks ago in a different OJ. Here is the translated version of the answer that I received.
Because N is rarely infinitely large in the real world, the difference between O(lgN) and O(1) is varies by constants attached to the time complexity depending on the size of N.
For example, let's say there's a hypothetical problem where you have to find the number you want with the least comparison.
If there is an O(1) algorithm that always looks for numbers by 50 comparisons, regardless of N, and an O(lgN) algorithm that compares ceil(lgN) times against N,
In terms of complexity alone, O(lgN) is faster than O(1) unless N is bigger than 1e15 or so.
This happens often, even when there is a significant difference in time complexity, such as O(N) and O(N^2).
If you want to know where the time complexity of hashmap, especially the unordered_map of C++, has a big constant, check the following videos and links.
unordered_map
hashtable_policy.h
bits/hashtable.h