I am getting a WA on testCase 6.
Question — Div 2C
Can someone please tell me what's wrong with the code?
→ Обратите внимание
До соревнования
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 05.11.2024 10:50:23 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
Ok.
??
Auto comment: topic has been updated by skpro19 (previous revision, new revision, compare).
Auto comment: topic has been updated by skpro19 (previous revision, new revision, compare).
I changed s[j] to c(to fix the logic at your code) and get WA at test 16 instead. 25885244
I think there is hash collision which cause this to still fail. So either use a better hash function or don't hash! :)
UPD: The problem do lies in the hashing. I simply change the hash function and now the answer is wrong on another line
But I just used a polynomial hash function as given in the tutorial for the question
I have no idea then. But looking at most people's code, they have better hash function than a polynomial hash.
Your function returns this same hash for strings "af" and "ba"... Seems like it isn't very good... Try changing 5 for something bigger, it should help (bigger than 26). I haven't look for other bugs, so I am not sure that it will help.
Each line consists only of letters 'a', 'b', 'c'.
So? What are you trying to imply?
Such a cryptic comment, we can only try to guess what he means.
I have already assigned 'a', 'b' and 'c' with the values 1, 2 and 3 respectively. So, that's I am asking
Good question.
I wish I could say your comments are helping, but sadly, they are not. So, how about getting a life, huh?
You can get rid of hashing by replacing
set<ll>withset<string>and still get WA 6: 25894661. It means that your solution has some other problems. I'd recommend finding them first, getting TL, and add hashing only afterawards.Also, as far as I can see, your hashing function is just fine.
I fix the logic as pointed out above, and got TLE on test 28. 25929172.
Great! Have you tried adding hashing back?
I did that above, and it got WA on test 16. 25885244
Ok, I believe that there is a chance of collision when using small modulo (like 109 + 7). Birthday paradox tells us that if there are approx.
random hashes, then chances of collision are greater than 50%. I'd suggest using bigger module as long as you use
long long— like 1018 + 9 (it's prime, which is important).Afterwards you'll find out that your code is in fact quadratic, because calculation of a single hash takes linear time in your code (can be done more efficient by recalculating hash when changing the character). Try optimizing that. And afterwards you may encounter that
endlmakes your program extremely slow — replace it with"\n"if it's the case.yup, i agree with you. I am not the poster of this problem btw. Just trying to help out here.
1 1
ab
ab
should be no, but your code says yes.
fixed that issue. Still fails on test case 16 :-(