Блог пользователя pksingh290

WA on codeforces round 166 prob d(Hashing)
Автор pksingh290, история, 4 года назад, По-английски

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.net/contest/271/submission/85804655

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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).

→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить