Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 USACO: PROB Calf Flac
Index -> Contests
Goto page Previous  1, 2
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
A.J




PostPosted: Mon Aug 31, 2009 8:38 am   Post subject: RE:USACO: PROB Calf Flac

I guess that does make more sense.
Sponsor
Sponsor
Sponsor
sponsor
saltpro15




PostPosted: Mon Aug 31, 2009 4:11 pm   Post subject: RE:USACO: PROB Calf Flac

I suppose using a trie wouldn't work? Just spitballing ideas at this point, I've tried pretty much every obvious approach I can think of.
bbi5291




PostPosted: Mon Aug 31, 2009 6:03 pm   Post subject: Re: USACO: PROB Calf Flac

A prefix trie won't help you. A suffix trie takes O(N^2) time and O(N^2) space. With some path compression and leet hax you can reduce both of those requirements to linear. Congratulations, you have just constructed a suffix tree!
A.J




PostPosted: Mon Aug 31, 2009 8:44 pm   Post subject: Re: USACO: PROB Calf Flac

bbi5291 wrote:

With some path compression and leet hax you can reduce both of those requirements to linear.


I don't quite see how you can ever possibly get intimidated by me when you are talking about reducing the time and space required for a suffix trie to linear. I would be really impressed if you can present a program that performs in linear time.
bbi5291




PostPosted: Tue Sep 01, 2009 10:40 am   Post subject: Re: USACO: PROB Calf Flac

Hold on a minute. You used Ukkonen's algorithm, and your solution isn't linear time? Ukkonen's algorithm was hailed as the first online linear-time suffix tree construction algorithm. Is it possible that what you built is actually a suffix trie?
btw, there is an "easy" linear-time construction - you use the linear-time divide-and-conquer suffix array construction described in Simple Linear Work Suffix Array Construction by J. Karkkainen, then the linear-time suffix-array-to-lcp-array algorithm described in Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications (T. Kasai, 2001), and finally you put these together to obtain the suffix tree (exercise for the reader).
A.J




PostPosted: Tue Sep 01, 2009 11:27 am   Post subject: RE:USACO: PROB Calf Flac

Alas, I am trying to reconstruct my memory of Ukkonen's algorithm...

How do you know this much, Brian?
bbi5291




PostPosted: Tue Sep 01, 2009 12:06 pm   Post subject: Re: USACO: PROB Calf Flac

I don't know all that from memory, of course. I have various bookmarks to stuff like this.
There are some problems on SPOJ that are trivial if you can construct a suffix tree in linear time, so Ivan Katanic and I teamed up to find some info on suffix tree construction. That's how I found out all of this.
btw, here's a partial list (note: many of these have more elegant solutions):
BEADS
BWHEELER
DISUBSTR
LCS
LCS2
MINMOVE
PALIM
SUBST1
TWICE
WPUZZLES
BWHEELER and DISUBSTR are passable with quadratic time/space too, though.
riveryu




PostPosted: Tue Sep 01, 2009 6:04 pm   Post subject: RE:USACO: PROB Calf Flac

Can someone explain how LCS would connect to the Calf Flac problem? I'll read what LCS is right now... Pretend I don't know anything.
Sponsor
Sponsor
Sponsor
sponsor
CodeMonkey2000




PostPosted: Wed Sep 02, 2009 12:15 am   Post subject: Re: USACO: PROB Calf Flac

If you have 2 strings, the LCS algorithm can be used to figure out the largest common sub sequence. For example suppose you have the strings: ABCFG and ABTFG, then the longest common sub-sequence is of length 4 (the largest sequence in both is ABFG).

In this problem it is useful because you are looking for the largest common sub sequence between a string and the reversed version of the string. Although for palindromes, you need to change the the implementation of the algorithm a bit.
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 2 of 2  [ 24 Posts ]
Goto page Previous  1, 2
Jump to:   


Style:  
Search: