ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1517. Freedom of Choice

Hashing ...
Posted by vlyubin 21 Mar 2013 04:55
It seems that lots of people can solve this problem with hashing. Well, I'm using 64 bit hashing and am using sufficiently large prime p (I'm using the usual polynomial hashing i.e. s[0]+s[1]*p+s[2]*p*p ...). I have tried 5 different p's and I'm always catching collisions at test 52 !!! I added code to check for collision and keep working with a different random chosen p ... and now I get TL !!!

My question is: what is the smart solution to the problem that I have? What hashing have you used?

To admins: How can you guys make solutions with random p get collisions? That's probably a really good test. I know how to build anti-hash for certain p, but I cannot imagine a test that hacks 10 random p's in a row. Good job! Or more like "my solution sucks" :)
Re: Hashing ...
Posted by Alexey Dergunov [Samara SAU] 22 Mar 2013 11:38
Re: Hashing ...
Posted by QProgS 23 Nov 2013 18:00
QProgS    1517. Свобода выбора    Visual C++ 2010    Accepted 0.656    9 720 КБ
Accepted with double hashing )

Edited by author 23.11.2013 18:01