Hi All
I have been implementing the solution to the following problem. I first tried using Unordered Maps but the solution gave a TLE, however, when I submitted the same code using Ordered Maps, it got Accepted.
Problem Link: https://codeforces.me/contest/1234/problem/B2
Solution using Unordered Maps: https://codeforces.me/contest/1234/submission/104445196
Solution using Ordered Maps: https://codeforces.me/contest/1234/submission/104445219
The same problem was observed in the following question as well:
Problem Link: https://codeforces.me/contest/808/problem/D
Solution using Unordered Maps: https://codeforces.me/contest/808/submission/101908196
Solution using Ordered Maps: https://codeforces.me/contest/808/submission/101848962
In most of the theory, I went through, regarding Maps in CPP, it states that ordered maps are mostly slower than unordered maps as the lookup in unordered maps is O(1).
Does anyone have any clue as to what might be the coding error leading to such a deviation. Any help will be appreciated!
Thanks in advance!
Auto comment: topic has been updated by bucky21 (previous revision, new revision, compare).
Lookup is not necessarily O(1) in unordered map. Read This
Why make such blog? If you want to use a DS, first read up on it. Search for articles on CF, other places as well. In this case, read neal's blog on unordered_map. https://codeforces.me/blog/entry/62393. Copy the implementation at the bottom slap it in there. Understand how to use it. Understand why unordered_map can be so slow. Understand how to use the custom hash.