Discussion @ 1590. Bacon’s Cipher @ Timus Online Judge

SPIRiT About the solving approach(+) [8] // Problem 1590. Bacon’s Cipher 29 Oct 2007 21:43

I know that suffix trees can be used for such problem. How about using a large hash table for storing codes of substrings that we already have? Anyone got AC in that way?

svr Re: About the solving approach(+) [5] // Problem 1590. Bacon’s Cipher 29 Oct 2007 22:16

I trying during a long time O(n) suffix tree of Ekkonen
but could'n catch all details. I think that you
question has the same nature. If you think about
yourself as good coder you should catch O(n) suffix tree.

Vedernikoff Sergey Re: About the solving approach(+) [3] // Problem 1590. Bacon’s Cipher 30 Oct 2007 17:40

I tried double-hash of about 30000 elements each but WA. Nevertheless, some people claim the problem may be solved with hash.

Lomir Re: About the solving approach(+) [2] // Problem 1590. Bacon’s Cipher 13 Nov 2007 04:25

How do you calculate hash for n^2 substrings?
I calculate hash seperately for each lenth os substring by:
hashcode = prime^n*c1 + prime^(n-1)*c2 + prime^(n-2)*c1...

string movement is by 1 char:
newhashcode = (oldhashcode - prime^n*removedchar)*prime + prime*addedchar

This gets TLE 3.

Brainfuck Re: About the solving approach(+) // Problem 1590. Bacon’s Cipher 16 Jul 2009 16:31

I use 'poganyi hash'. And it works very good. Yeah, baby!

Oracle[Lviv NU] Re: About the solving approach(+) // Problem 1590. Bacon’s Cipher 6 Aug 2010 03:47

to Lomir: you should not use sorting. Without sorting this approach gives AC in 0.454 sec.

SPIRiT Re: About the solving approach(+) // Problem 1590. Bacon’s Cipher 6 Aug 2009 00:46

Finally managed to implement the Ukkonen algo correctly - worked from the first try and is much faster now, than with O(N^2) implementation. Here is my status board to examine:

http://acm.timus.ru/status.aspx?space=1&num=1590&author=33910

Edited by author 06.08.2009 00:47

Edited by author 06.08.2009 00:48

AterLux Re: About the solving approach(+) [1] // Problem 1590. Bacon’s Cipher 7 Sep 2010 20:51

Calculation of hash for each substring will take O(N^2). Then you need to check non-equal of string with same hash. For example for test 'aaaaaaaaaaaaa' (and longer) every substring of same length will have same hash code

Sushil Nath Re: About the solving approach(+) // Problem 1590. Bacon’s Cipher 24 Jun 2011 01:17

Can it be done using ternary search tree

Discussion of Problem 1590. Bacon’s Cipher