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

Problem C Div 2
Автор L_H, 10 лет назад, По-английски

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

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

=(((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.

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить