pksingh290's blog

WA on codeforces round 166 prob d(Hashing)
By pksingh290, history, 6 years ago, In English

i am using string hashing in the sollution but each time i m getting WA on submission .i am unable to find where it went wrong . all the suggestions to make the sollution correct are welcome .here is the link to the sollution https://codeforces.me/contest/271/submission/85804655

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
6 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Your hash was too weak. I fixed your code by using p2 = 29 and making the hashes pairs of long longs: 85813439

P.S. The code became much faster after using vector and unique instead of set: 85813494. set's constant factor is huge compared to vector.

Also if the string size is bigger or stores a wider range of characters, the hashes of substrings will overflow long long, so you should hash under two moduli (1e9 + 7 and 1e9 + 9 worked for me).

→ Reply
  • »
    »
    6 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    hey thank for your reply but can u plz tell me the diff between array<unsigned ll, 2> hashs and unsigned ll array[2]. i think the one u used belongs to STL but can u plz ellaborate about it little.thanks for your time AQZZ

    → Reply