CHEFSHIP - Editorial

editorial
, , , , , , ,
175

We need hash[l]-(hash[r+1]*pow[r-l+1]) under a modulo. However, subtraction under a modulo can lead to a negative result. But modulo only allows answers from 0 to (MOD-1). Thus, when we perform subtraction under a modulo, we add MOD to the result if it’s negative. Instead of checking whether or not the result is negative, I’ve simply added MOD to it, and then performed MOD again. This will guarantee that the result is between 0 and (MOD-1).

Thus, I wrote:

(MOD-(hash[r+1]*pow[r-l+1])%MOD+hash[l])%MOD;

This can also be written as:

long left=hash[l];
long right=(hash[r+1]*pow[r-l+1])%MOD;

long res=(left-right)%MOD;
if(res<0) return res+MOD;
else return res;
176

@raja1999 @akashbhalotia @rishup_nitdgp
sir, I used Z-function approach, my solution is giving WA and I tried all possible cases,
please, can you provide a test case where my solution is wrong

solution: https://www.codechef.com/viewsolution/33842329

177

Possible bug, wherever you use MOD, check weather its value (say x) is <0, if x<0 then x = (x+MOD)%MOD

178

Can somebody suggest me a test case where my approach will fail
Solution:
https://www.codechef.com/viewsolution/34734893

I used 2 lps arrays-One is for the input string and another is for the reverse of the input string
See the if condition in the last for loop, I update my count variable there

179

try this case
1
abababababababab

1 Like
180

why are we ignoring case of collision with this hash function?

181

what is the difference between these two function ?

  • 1 ) hash[i]=(str[i]− ′a ′+1)+(P∗hash[i+1]).
  • 2 ) hash[i] = (hash[i - 1] + (str[i] - ‘a’ + 1)*P[i]).

    please help anyone i use the 2nd hash function which sometimes giving me negative value when i subtract (hash[r] - hash[l - 1]), obviously result need to be divided by P[l] when [l…r],(hash value ranges from [l…r]). what am doing wrong?

EDIT :

Problem Solved :smile:

  • Modular Multiplicative Inverse
  1. Modular Inverse - Algorithms for Competitive Programming
  • Modular Subtraction :slightly_smiling_face:
    there may be the situation where hash[r] < hash[l - 1] and the result must be in between 0 to MOD.
    wrote this :slightly_smiling_face:
    • ((hash[r] - hash[l - 1] + MOD)) % MOD
182

Compile with the-std=c++17 flag

183

You should not use substr() at all. The hash_value function should take a begin and end index and then return the hash of the corresponding substring. By doing it this way we can do some pre-processing so that the call to hash_value will complete in \mathcal{O}(1).

This is done using a rolling hash. for the rolling hash we need two values: an base B and a large prime P. I will take B=27, P=10^9+7, though you may need to play around with these values. Then the hash value of a string s_0s_1s_2s_3...s_k will be B^n(B^0s_0+B^1s_1+B^2s_2+\ldots+B^ks_k)\mod P.

Now as precomputation we will calculate prefix hashes ph_k=B^0s_0+B^1s_1+\ldots+B^ks_k. Now we can calculate the substring hashes as hash(l,r)=B^{n-r}(ph_r-ph_{l-1})

Note: For those knowing rolling hashes the B^n term might be strange. I have added it to avoid modular division as it is not entirely trivial to do. Then having the B^n term in front is an easy workaround

1 Like