L_H's blog

Problem C Div 2
By L_H, 10 years ago, In English

I am trying to solve http://mirror.codeforces.com/contest/514/problem/C but repeatedly getting wa at test 6.Tried a lot but can't figure out the problem...Link to my solution http://mirror.codeforces.com/contest/514/submission/9883601

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

Comments Comments (11)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

=(((str[j]-'a'+1)*(ll)pow(5,j))%mod); pow function is declared like double pow(double x, double n)
some powers of 5 will not fit into double and number will be truncated(size of double is 8 bytes).
Use your own Pow function to power number modulo mod.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Your bug is in hash calculation: pow function is calculating result in double type. It won't work as you expect: pow can return something like 3e100, it won't be taken by modulo and will moreover loose a lot of significant digits.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the solution with trie is better than the hashing one. I haven't perfectly analized your code but maybe the bug is that your hashing is not perfect so I suggest you to implement the trie solution, which is much easier

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why you don't try with different bases?For example try with 37 or 71...

→ Reply