Consider this problem (https://codeforces.net/contest/984/problem/D).

Solution one (https://codeforces.net/contest/984/submission/276446617) uses two recursive self-explanatory functions (compute_f, and compute_max_xor) that use unordered_map for memoization. It does not pass (2000 ms TLE).

Solution two (https://codeforces.net/contest/984/submission/276446798) is the same from a logic point of view (dp corresponds to compute_f and dp_max corresponds to compute_max_xor), except it uses Dynamic Programming. It passes in 546 ms.

I thought it could be that different because of hash collisions. Some people hack some other people by using clever inputs that blow up hashmaps ... but adding a random custom_hash did not help whatsoever.

Is the overhead of using an unordered_map that HIGH? Big enough to bring a x4 in time? Or am I missing something else?

Thank you!

EDIT Keeping memoization but using a 2D array instead of an unordered map did the trick. https://codeforces.net/contest/984/submission/276544726. Crazy. Thank you for your help!