Всем привет!
В ходе решения 4C - Система регистрации возникла интересная ситуация. Моё решение: 24184665. Суть в том, что мой компилятор и компилятор Codeforces выдает разные ответы. Компилятор — MS VS C++ 2010. Пример:
Входные данные: test data
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| 5 | adamant | 159 |
| 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 10:08:25 (l3).
Десктопная версия, переключиться на мобильную.
При поддержке
Since the standard doesn't specify the implementation of hash functions, the output is environment-dependent. Actually
std::hashcan even produce different hash values for the same input in different executions.(Since C++14)But during one execution it should return the same hash codes for the same values. It's the main principle of hash alghorithms. The question is in generation different hash-codes for the same objects during one execution.
The issue isn't "different hash-codes for the same objects during one execution" which is a library bug. It's the same hash value for different objects, in other words, hash collision. The string "idcvexvhgtyyvplfr" and "idcvexvhgtyyvplfrl" generates the same hash value for the compiler you selected.
MS VS C++ 2010 hash function only looks at a part of the string according to this StackOverflow post. A bit odd, but not a bug.
Yes. Maybe my previous comment isn't clear. I meant generating different hash for an object in an execution is a bug. Hash collision, although only looks part of a string is weird, isn't a bug.
Oh, I understood. Thank you, guys. The solution is very simple — write your own hash function.
Writing your own hash function is not going to prevent you from getting collisions. Is there a reason why you're not using a hash table?
There isn't. Simply, hash function was the first solution, which I found as optimal. But practice has shown that it isn't the best one. Thank you for a helpfull tips.