Hello
So I was solving this problem (here), and a hashing-based solution seemed obvious to me. It is enough to look at the hash of the changed substring and get the final hash of the modified string using the prefix and suffix. I do not know much about hashing, just a little about polynomial (or rolling) hash. But it seems that my hash isn't safe enough. I tried a few things, but with no luck:
Spoiler
I used the standard primes M = 1e9+9 and p = 31 initially, as I learned from cp-algo. I have no clue what I'm doing wrong.
I hope someone could assist me in this and help me understand hashing a little better. Cheers!
off by one
You can only improve probability of correct answer using hashing.
You can check SlavicG submission. He used $$$3$$$ different combination of $$$3$$$ $$$M$$$ (mod) values and $$$4$$$ different $$$p$$$ values to improve his probability of getting correct output.
You can also checkout his other submission during contest which failed to pass since they used only $$$1$$$ value of $$$M$$$ and $$$p$$$. submission-1 submission-2
UPD: You can checkout this blog for more information on multi-hashing and how to write hard to hack hashing code (and also how to hack poorly written hashes).
I do not think that the SlavicG submission you linked is safe from hacks. I've hacked many similar rolling hash solutions like that in that past. The reason it is hackable is that
In my opinion, the easiest solution to be safe from hacks when using rolling hashes is to use a single large prime like $$$P=2^{61} - 1$$$, and then use a random base (pick it uniformly at random in [0, P)). But whichever option you choose to go with, do not make the base constant (non-random).
Just a final note. SlavicG technically does randomize the bases using
shuffle(all(plsnohack2), rng);
, but there are only 24 different possible outcomes. So his choice of bases is effectively deterministic.Since all of your hashes are integers in range $$$[0, M)$$$, there are $$$M$$$ different possible hashes. Your code will work incorrectly if you encounter a hash collision, i.e. a case where two different strings hash to the same hash value.
In the problem you linked, you're comparing up to $$$2\cdot10^5$$$ hashes with each other. According to the birthday paradox you only need around $$$\sqrt{M}$$$ different hashes before it's expected that some two are the same. Since $$$2\cdot10^5$$$ is much larger than $$$\sqrt{M} \approx 31622$$$, it's very likely that you'll encounter a hash collision.
The easiest way to deal with this is to choose two different pairs of (multiplier, modulus) and calculate the hash with both; now the hash is the pair of these hashes. Now the number of hashes is on the order of $$$M^2$$$ and we'd expect a collision only once we have around $$$M$$$ strings, so two hashes should be good enough. Of course you can use more to be safe but it's probably not required.
Adding to this, in most* problems it usually suffices to have $$$2^{64}$$$ as the second modulus for ease of implementation (something like 231564057).
$$$2^{64}$$$ is a very weak modulus; It is widely known that the Thue-Morse sequence will hack any modulus in the form of $$$2^k$$$. How does it help when used alongside a prime modulus?
UPD: It really doesn't help so much
purple face lol
Thanks! It took me some time to implement, but I'm pretty sure the hash is much safer. Thanks for your advice.
accepted submission
using unsigned long long to hash, i will call it overflow hashing.
You can check my code for better understanding: https://codeforces.me/contest/1840/submission/208865643