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 tjat different because of hash collision ss. Some people have added to hack some other peopleck some other people by using clever inputs that blow up hashmaps ... 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 tjat different because of hash collision
↵
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!
