Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

CP_Sucks's blog

By CP_Sucks, history, 17 months ago,

Is there any limit to the length of the string after which hashing should be avoided. Also can the hashing solutions be easily hacked in contests ?

• -14

 » 17 months ago, # |   0 For p = 31 and m = 1e9 + 9, if string is zzzzzzz the hash value is more than 1e9 + 9 and the collisions start, so how can i use it for strings as large as 1e6 without getting hacked ?
 » 17 months ago, # |   +2 According to the birthday paradox, if m = 1e9 + 9, we can random about 200000 strings and the possibility of collisions is more than 99.9999%!Simple code can calculate the possibility: int m = 1e9 + 9; double x = 1; for (int i = 0; i < 200000; ++i) { x = x * (m - i) / m; } x = 1.0 - x; cout << fixed << setprecision(11) << x << endl; Also, if you want to make your hashing become hard to hack, there are two possible choice: use a long long prime as m use two or more hash functions Sorry for my poor English, I hope this can help you:)
•  » » 17 months ago, # ^ |   +24 Well, that might make it a bit harder to hack, but still hackable. You should also make your base randomized.