Why is this solution at least 4 times slower when using recursion?
Difference between en2 and en3, changed 82 character(s)
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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English JasonMendoza2008 2024-08-15 16:53:56 182
en5 English JasonMendoza2008 2024-08-14 23:20:27 4 Tiny change: 'oever.\n\nDoes the over' -> 'oever.\n\nIs the over'
en4 English JasonMendoza2008 2024-08-14 23:08:31 2 Tiny change: 'could be tjat differe' -> 'could be that differe'
en3 English JasonMendoza2008 2024-08-14 23:08:18 82
en2 English JasonMendoza2008 2024-08-14 23:07:35 89
en1 English JasonMendoza2008 2024-08-14 23:06:08 810 Initial revision (published)