Всем привет!
В ходе решения 4C - Registration System возникла интересная ситуация. Моё решение: 24184665. Суть в том, что мой компилятор и компилятор Codeforces выдает разные ответы. Компилятор — MS VS C++ 2010. Пример:
Входные данные: test data
Всем привет!
В ходе решения 4C - Registration System возникла интересная ситуация. Моё решение: 24184665. Суть в том, что мой компилятор и компилятор Codeforces выдает разные ответы. Компилятор — MS VS C++ 2010. Пример:
Входные данные: test data
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 152 |
| 3 | Proof_by_QED | 146 |
| 3 | Um_nik | 146 |
| 5 | Dominater069 | 144 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
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.