Consider this problem (https://mirror.codeforces.com/contest/984/problem/D).↵
↵
Solution one (https://mirror.codeforces.com/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://mirror.codeforces.com/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 because of hash collision some people have added to hack some other people but adding a random custom_hash did not help whatsoever.↵
↵
Does 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!
↵
Solution one (https://mirror.codeforces.com/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://mirror.codeforces.com/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 because of hash collision some people have added to hack some other people but adding a random custom_hash did not help whatsoever.↵
↵
Does 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!
