Hello, Codeforces.
I tried to use hashing to solve 1129C - Morse Code. However, I kept getting the TLE verdict. My time complexity should be O(k * m^2) (where k is the longest string to be tested, or 4) while the editorial's solution has time complexity O(k * m^2 + m^2 * log m).
I've tried many optimizations, such as using 2^64 as a base, switching between unordered_map and map, tweaking the multiplied prime, and even adding huge strings of pragmas. Pre-doing all the hashes gave me an MLE.
Here is a link to one of my many failed submissions : 58709459. Please help!
I was able to squeeze it using self-written unordered map. Standard one is very slow and not able to perform 9*10^6 operations in two seconds. 58835699
Is it because it hashes the input value, or because the unordered_map expands itself when it gets too large?
That's just because of the slow nature of the unordered map. At least, there is different data structure implemented, mine is linear, while standard uses buckets as far as I know.
AC with unordered_set: 50590417
seen.max_load_factor(0.7);=> AC