I understand that I'll get downvoted here, but maybe I'll get some help as well. I'm trying to solve 514C using hashing, as it's done in editorial, but why my submission gets WA on test 27?
# | User | Rating |
---|---|---|
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 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | adamant | 157 |
6 | awoo | 157 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | djm03178 | 153 |
I understand that I'll get downvoted here, but maybe I'll get some help as well. I'm trying to solve 514C using hashing, as it's done in editorial, but why my submission gets WA on test 27?
Name |
---|
Most probably a false positive due to a hash collision. The hash function is probably telling your program that the string only has a single character changed, but multiple characters may have changed and the same hash value has been computed.
To avoid this, maintain a Map<Long, String> for each hash value -> string, then when you think you found a solution, double check that the difference is indeed one letter. See my submission for an example.
I get AC with a small change to your code: http://codeforces.me/contest/514/submission/9973616
Thank you.