I thought unordered_set was faster because it doesn't need to deal with sorting.
I got accepted for problem C on a recent Div.3 contest, but it returned as TLE on test 17 after contest finished and I lost 52 points. You know what's funny? When you replace unordered_set with normal set, it gives accepted (sorting ability of normal set doesn't help you for this problem)
Code with unordered_set (TLE on test 17): https://mirror.codeforces.com/contest/2106/submission/317003071
Same code with normal set (Accepted): https://mirror.codeforces.com/contest/2106/submission/317364054
It’s due to hash attacks. You can mitigate this by using a custom hasher.
This problem happens so often that I just asked ChatGPT to sum it up, take a look at this chat:
https://chatgpt.com/share/680d1664-4814-8011-9b58-aaa807bea445
I guess I should just use set to prevent those hashing problems, even though unordered_set is meant to be faster
I recommend using gp hash table with the splitmix64 hash, it functions the same as unordered_set but it is faster in edge cases because of it's O(logn) time complexity compared to the unordered_set O(n)
Can you drop an example code please?
https://mirror.codeforces.com/contest/2097/submission/317465961
But some unordered_set functions aren't avialble so just normal unordered_set<int, SplitMix64> st; would also be fine with ~ same speed
Yes'nt. In theory, unordered set's operations are much faster than set(1 vs logn). Butt, due to collision, sometimes unordered_set operation can take up to O(n). Check this blog