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

Discussion of Problem 1590. Bacon’s Cipher

Actually hashes work
Posted by ARK (***AESC_USU***) 27 May 2017 07:20
There were rumors that it is hard to get AC with hashes.
Got AC in 0.031 using standard N log^2 N suffix array. Hashes modulo 2^64 (so there is no explicit divisions in code).
There are couple of tricks, but they all are very easy to code.

1) gethash(i + l, i + mid) == gethash(j + l, j + mid)
&& memcmp(s + i + l, s + j + l, mid - l) == 0
instead of just
gethash(i, i + mid) == gethash(j, j + mid)
in binary search (lcp computing)

2) std::::stable_sort is preferable over std::sort when comparisons are heavy. std::stable_sort makes more assignments in average, but much less comparisons.

0.031 sec, 62 lines of code (including 10 empty, "return 0", 4 includes and so on).
Re: Actually hashes work
Posted by Sandro (USU) 28 May 2017 08:23
The rumors said that it was hard to get AC with hashes in O(n^2): to calculate hashes of all substrings and output the number of different ones :)
Re: Actually hashes work
Posted by mouse_wireless2 27 Jan 2018 02:09
I got AC by output number of different hashes in O(n^2).
Took some tries though. Ended up using double hash, one which uses long long overflow and one modulo some big prime. I think test 27 is anti-hash test.

Edited by author 27.01.2018 02:09