| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
as the title said,I had a problem solving some questions about hashing:
If you write a hash with high accuracy, you will exceed the time limit, but if you write a hash with low accuracy, you do not know whether it will be hacked by the data.
What should I do then?
As same as you.I want to know why.
I've never seen a problem of which the intended solution is hash but you can't write a 'safe' hash function just because it's just a little bit slower than a straightforward version. Perhaps you should think again if the intended solution is not hash at all?
our test's solution is hash，but if I use unsigned overflow hash，I will get hacked，I only got 1/10 points.But if I use double hash，I will get TLE.But common hash will get hacked,too.
So what do I do in this situation?
I think this question is becoming an XY problem. You should probably specify what you're actually trying to solve. We need to know:
You're right.I'm working on a string hash problem. This problem requires checking arbitrary substrings, and I can only think of ordinary hashes. But the constant problem is with this string hash, and if I use a double hash, I run out of time. Thank you again for your answer.
While solving from the problemset, I end up binary searching on the accuracy until i get AC ;-; , generally 10**9 + 7 works quite well tho , and to make it more randomized , i store the values XORed with some random integer. So as to make it harder to hack.
Stupid question, but which kind of hash are you asking about?
If time limit is not a problem (if you're hashing and it's not fitting in the time limit, probably the intended solution is not hashing), you can try double or even triple hashing. This just means you combine several modulos and bases (for example, mod $$$1e12+39$$$, base $$$69$$$ and unsigned overflow hashing) and instead of a single integer, your hashed value would be a tuple of integers.
Note that apart from changing modulos, changing bases is also effective. And if you're still getting hacked, try randomizing mods and bases. Hope this helps!
This is very helpful to me, thank you!
But what if it's a matter of time? What if there are some evil quiz makers who know the hash constant (like our quiz maker)?
Using XOR-hashing will be a lot quicker than hashing strings into numbers since it doesn't use the expensive modulo operator. If you're worried about the accuracy then just use two or three of them in conjunction. I never needed to use more than two in my experience.
use double or triple hash and random base