Why is this solution at least 4 times slower when using recursion?
Difference between en1 and en2, changed 89 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 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!

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)