PROBLEM LINK

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...

problem link

SOLUTION — Geeks for Geeks

I have also seen william lin solve it using hash_map in his cses speedrun video on youtube.

But C++ STL unordered_map is a 1 to 1 mapping of key and value. So say x = 12, Now we could make x by doing (a1+a4) + (a2+a3) = 5 + 7. But let's say (a3+a4) = 7 as well , and as unordered_map records only the latest occurrence of 7, so we only have 7 at (a3+a4). As a4 is repeating in both (a1+a4) and (a3+a4), these are not distinct positions and we don't have an answer.

This is not a perfect example, because we can discover other good ways to make 12 if we check other possible combinations. And also a perfect example might not exist given that this is a well-known solution, I just wanted to convey my idea why unordered_map might fail and it is not all clear to me why it actually works for every possibility.