I was solving this problem with the use of single hash and got wrong answer which means conflicts are arising. I've seen other users submission, they've solved it using double hashes, so I was wondering that can't this problem be solved using single hashing. Link to my submission:
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 4 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 14.11.2024 19:52:35 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
Single Hash : http://codeforces.me/contest/271/submission/37988095
Thanks mate....could you tell me one thing that in the power array you are storing powers of p = 123, why it is not overflowing since n can be upto 1500. And another thing I think I did exactly same thing as your's could you review my code for a minute pal!! Please.... Your kind help would be appreciated.
Overflow is same as modulo 2e64
Oh....thanks found a new thing :)
Sorry for disturbing you again... but won't it cause a signed integer overflow...!!
You are counting only the no. of hashes,it only matters for the hashes to be equal
I get it what you're saying, but do we have to take the prime number to be fairly big, i mean can't we take p to be 31 instead of 123, i'm getting wa at 31 but ac on 123...
there must be anti-hash TC,so you are having WA.Double hashing provides less probability for collisions.I just tried 123 and it worked!!
Thanks for your time pal...:)
Possibility of collision
, you can not use int32 modulo, it is not safe for u. If it will be helpful, my solution uses single prime modulo 261 - 1.
Thank you so much!! please could you elaborate further how did you reached the conclusion for collision probability!! Thanks :)
I writed tutorial about rolling hash for beginners, see Minimizing the probability of collision. In this problem we need to compare each pairs of strings in set of n(n + 1) / 2 strings, so it is n4. Maybe in this problem we need to count only compares strings with equal length, maybe someone will help to accurately assess this.
Thanks for your precious time, onii-chan :p