ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1517. Freedom of Choice

Pages: Previous 1 2 3 Next
Re: I got MLE, TLE on test #9, WA on test #8 :(
Posted by Felix Halim 30 Dec 2006 23:05
Kit wrote 23 December 2006 12:09
No tricks, I have almost double reserve in memory. But I use hash working with edges, may be that's the matter.

Yes, I got it Accepted at last :) The trick is to use your own hash implementation rather than hash_map from STL!

Did anybody solve this problem using STL?
Suffix Array seemed a lot faster in implementation
Posted by Felix Halim 1 Jan 2007 20:00
I just got AC with Suffix Array + LCP in 0.3xx secs.

The implementation is cleaner than Suffix Tree and requires less space yet still run in O( N ) time.

I'm curious with Burunduk1's Suffix Automaton, is there any online resources available to learn about Suffix Automaton? I really want to solve this problem using Suffix Automaton :)
Re: I got MLE, TLE on test #9, WA on test #8 :(
Posted by cpphamza 1 Jan 2007 20:01
Felix Halim wrote 23 December 2006 22:18
What I did is to create 1 Suffix Tree with string: s1 + "\$" + s2 + "#"  where s1 and s2 is the first and second string in the input. After I built the Suffix Tree, I traversed it and find the deepest node which has child "\$" and "#".

this is exactly what iam trying to do but i got stack overflow in test case 9, obviously the stach overflows when i traverse the tree wishing to find the deepest node which has the two terminator characters as children (or in the subtree below).

I guess the tree is too deep, so how could u solve this part?
Re: I got MLE, TLE on test #9, WA on test #8 :(
Posted by Felix Halim 5 Jan 2007 22:35
Don't traverse the tree using recursion ;)
Try using explicit array[100000]
Re: I got MLE, TLE on test #9, WA on test #8 :(
Posted by cpphamza 8 Jan 2007 00:26
Felix Halim wrote 5 January 2007 22:35
Don't traverse the tree using recursion ;)
Try using explicit array[100000]

Do u mean to use that array to bottom up traverse the tree? or u mean something else?
Re: I got MLE, TLE on test #9, WA on test #8 :(
Posted by Felix Halim 8 Jan 2007 11:50
cpphamza wrote 8 January 2007 00:26
Felix Halim wrote 5 January 2007 22:35
Don't traverse the tree using recursion ;)
Try using explicit array[100000]

Do u mean to use that array to bottom up traverse the tree? or u mean something else?

A recursion is using stack implicitly (stack memory) and it has limitation on the depth of the recursion for some compiler (or maybe by the stack memory configuration of the compiler).

So, instead of using stack memory we can use an explicit stack array to simulate the same behavior. However, the code   gets uglier and harder to read :p
Update
Posted by [SPbSU ITMO] WiNGeR 9 Feb 2007 20:51
Update
Posted by [SPbSU ITMO] WiNGeR 9 Feb 2007 20:57
Suffix Tree gets AC in 0.14 time and 23 888 KB
Suffix Automation gets AC in 0.125 time and 22 320 KB
autor is me

P.S. Who can tell me, how to implement Suffix Array in O(n)?
Re: Update
Posted by Ilya Grebnov[Ivanovo SPU] 11 Feb 2007 13:41
Suffix array can be constructed in O(n) time by Karkkainen-Sanders algorithm.
Re: I got TLE on #28, with single hash solution.
Posted by Rostislav 16 Feb 2007 14:33
Hi!
I have tried so many interpretations of the main idea for finding suffix array in O(NlogN), but all of them (except 1, because I optimize it) ran for more than 2 second  .
Would you share the secret, I mean is there something special you do?
Re: I got TLE on #28, with single hash solution.
Posted by Ilya Grebnov[Ivanovo SPU] 17 Feb 2007 23:57
There is no any secret. Try to find original article "Faster Suffix sorting" by N.Jasper Larson and Kunihico Sadakane. Also very useful article for this problem is "Two Space Saving Tricks for Linear Time LCP array Computation" by Giovanni Manzini.
Re: I got TLE on #28, with single hash solution.
Posted by Rostislav 18 Feb 2007 12:45
Thank's.
Re: Update
Posted by Felix Halim 19 Feb 2007 13:08
Hi WiNGeR,

You might be interested to see this demo about creating Suffix Array in linear time by Juha Karkkainen and Peter Sanders:

http://felix-halim.net/pg/suffix-array/index.php

Do you have any reference on how to build Suffix Automaton?
Which one is simpler? Suffix Tree or Automaton?

Thanks
Re: hashing
Posted by Chalyshev Vladimir [cmd] 30 Nov 2007 03:07
i relalize double hashing, but i get tle on test 9.
Can anybody get me hash-functions used in solution on this problem?
Re: hashing
Posted by KIRILL(ArcSTUpid coder:) 30 Nov 2007 19:25
try 64bit hashing
Re: hashing
Posted by Cheryl Xie 11 Jan 2008 19:15
I can't use single hash to solve the problem...
Would you please tell me how to design the hash?

And what is the 64bit hashing meaning?
Suffix Automata are simple
Posted by Rafail Ahmadisheff 27 Jan 2008 03:19
As far as I am concerned, Suffix Automata are the best tool for solving this problem. At least, it holds for me. I got AC three hours after I started reading "Automata for Matching Patterns" ( http://www-igm.univ-mlv.fr/~mac/REC/B4.html ). Earlier I spent much more time on Suffix Trees and Arrays - and I failed to solve this problem by their means. Would be grateful for any hints concerning Trees and Arrays (just curious).
Hints for impementingsuffix trees
Posted by SPIRiT 7 Aug 2009 22:51
I used the standard ukkonen implementation. However, I use sibling lists for edges representation (watch Wikipedia "Suffix tree"), and I make leaves of tree explicit, that means that in the worst case you have 2*N nodes totally, N of them are leaves, where N is the total size of the text. This works fine.

Also, for the traversal of the tree, I used simple recursion. I tried to use stack modelling, as someone proposed in the posts earlier, but failed with TLE on test 9. In order not to get stack overflow set up the size of the stack about 10 megabytes (watch FAQ in order to learn, how to do it).
nlogn
Posted by georgi_georgiev 31 Aug 2009 13:14
I just did it with hash and my own hash table for 0.265 sec and 7mb memory.
Re: Hints for impementingsuffix trees
Posted by daftcoder [Yaroslavl SU] 3 Sep 2011 16:22
SPIRiT wrote 7 August 2009 22:51
I used the standard ukkonen implementation. However, I use sibling lists for edges representation (watch Wikipedia "Suffix tree"), and I make leaves of tree explicit, that means that in the worst case you have 2*N nodes totally, N of them are leaves, where N is the total size of the text. This works fine.

Also, for the traversal of the tree, I used simple recursion. I tried to use stack modelling, as someone proposed in the posts earlier, but failed with TLE on test 9. In order not to get stack overflow set up the size of the stack about 10 megabytes (watch FAQ in order to learn, how to do it).

Totaly agree.
Sibling lists save memory well, and work pretty fast.
I also needed to increase stack size.

http://acm.timus.ru/status.aspx?author=48362&from=3761647&count=1
Pages: Previous 1 2 3 Next