Why is hashing so slow?

Правка en1, от balbit, 2019-08-14 18:11:48

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!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский balbit 2019-08-14 18:11:48 619 Initial revision (published)