pksingh290's blog

WA on codeforces round 166 prob d(Hashing)
By pksingh290, history, 4 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://mirror.codeforces.com/contest/271/submission/85804655

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

Comments Comments (3)
| Write comment?
»
4 years ago, # |
← 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
  • »
    »
    4 years ago, # ^ |
    ← 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
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Read about it here: https://en.cppreference.com/w/cpp/container/array

      Main benefit is that array has compare operators already defined for it, and you can use STL functionality on it. In my experience, the speed is almost exactly the same as using pair or tuple or int[].

      → Reply