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!
Auto comment: topic has been updated by JasonMendoza2008 (previous revision, new revision, compare).
Auto comment: topic has been updated by JasonMendoza2008 (previous revision, new revision, compare).
In the first request, you do not respond quickly to the request It’s hard for me to say for how long. And in the second, they made a preconception and responded to a request from O(1)
well because there is a cache it won't ever be longer, complexity wise, than filling up the whole dp array
Unordered map is pretty slow compared to array look up. At the end of the day, unordered map is a hash table which is just an array but with the added step of converting the key to the index in the table with hashing. Hashing is not the quickest operation.
Hopefully it's clear why this is much slower than an array.
I think so too but damn I did not expect such a big gap between the two.
I don't know what c++ uses, but this link has an example of a hash. https://stackoverflow.com/questions/664014/what-integer-hash-function-are-good-that-accepts-an-integer-hash-key. The first one performs around 12 operations to make a hash.
Keeping memoization but using a 2D array instead of an unordered map did the trick. https://codeforces.net/contest/984/submission/276544726. Crazy
Yes, the combined overhead of unordered_map and recursion can easily cause a 4x slowdown. But the iterative DP approach with vectors is more efficient, avoiding the significant costs associated with hashing and recursion. i think This is the key difference between the two solutions.