| ENG RUS | Timus Online Judge |
Discussion of Problem 1517. Freedom of ChoiceIvan Ivanov Just curious [46] // Problem 1517. Freedom of Choice 16 Dec 2006 18:14 Just curious did anyone managed to pass the time limit using binary search + rolling hash or the test data are specially designed to be solved in time only by an efficient suffix tree/array implementation? Bruce Merry Re: Just curious // Problem 1517. Freedom of Choice 16 Dec 2006 18:16 I tried an O(N.log N) suffix array (although finding the length of a match was O(N.log N.log N)) and it was too slow, although it ran in about 1.3s on my machine. Nick J Re: Just curious // Problem 1517. Freedom of Choice 16 Dec 2006 18:23 Test 10 was very hard for binary+hash solutions,but double or triple hash would pass it. Dmitry 'Diman_YES' Kovalioff Several hash-based solutions got AC (+) [43] // Problem 1517. Freedom of Choice 16 Dec 2006 18:36 These solutions are correct, because the test set was really hard. The solutions of the authors are based on suffix trees (Nikita Rybak, Pascal) and suffix arrays (Ilya Grebnov, Java) and pass the TL easily. Ivan Ivanov Re: Several hash-based solutions got AC (+) // Problem 1517. Freedom of Choice 16 Dec 2006 22:52 Thank you Dmitry! It seems that pretty soon Ukkonen and/or efficient suffix array implementations will become a must in real time contests. I would like to congratulate the autors for the excellent problem set! Deftone Re: Several hash-based solutions got AC (+) [38] // Problem 1517. Freedom of Choice 17 Dec 2006 07:40 Single hash-based solution got AC too Nick J Re: Several hash-based solutions got AC (+) [37] // Problem 1517. Freedom of Choice 18 Dec 2006 13:39 I got AC with optimized single hash-based solution too. But if I wrote double hash based solution I wouldn't have +9. CHN_XT Re: Several hash-based solutions got AC (+) [36] // Problem 1517. Freedom of Choice 22 Dec 2006 11:45 I got TLE on #28, with single hash solution. Burunduk1 Re: I got TLE on #28, with single hash solution. [34] // Problem 1517. Freedom of Choice 22 Dec 2006 13:28 The simplest solution with single hash gets AC in 0.468 Ilya Grebnov[Ivanovo SPU] Re: I got TLE on #28, with single hash solution. [33] // Problem 1517. Freedom of Choice 22 Dec 2006 15:33 Some statistics: 0. Suffix Automaton get AC in C++ 0.125 time and 22 320 KB Memory, author is [SPbSU ITMO] WiNGeR 1. Suffix Automaton get AC in C++ 0.14c with 22220КБ Memory, author is Burunduk1 3. Suffix Tree gets AC in 0.14 time and 23 888 KB Memory, author is [SPbSU ITMO] WiNGeR 4. Suffix Array with O(N) implementation get AC in C++ 0.343c with 5756 КБ Memory, author is me 5. Single Hash get AC in C++ 0.39c with 4024 КБ Memory, author is me 6. Single Hash get AC in Pascal 0.5c with 6191 КБ Memory, author is me 7. Suffix Tree get AC in Pascal 0.656c with 16416 КБ Memory, author is Kit(Vologda SPU) 8. Suffix Array with O(NLogN) implementation get AC in C++ 0.765c with 2756КБ Memory, author is me 9. Suffix Array with O(NLogN) implementation get AC in Java 1.406c with 5503КБ Memory, author is me Edited by author 22.12.2006 15:35 Edited by author 25.12.2006 11:24 Edited by author 11.02.2007 13:44 Edited by author 11.02.2007 13:45 Edited by author 11.02.2007 13:45 EfremovAleksei Re: I got TLE on #28, with single hash solution. // Problem 1517. Freedom of Choice 22 Dec 2006 16:05 I write Suffix Tree(Ukkonen Algorithm). AC - 1 sec. But I used 30mb memory. Felix Halim I got MLE, TLE on test #9, WA on test #8 :( [12] // Problem 1517. Freedom of Choice 23 Dec 2006 09:37 I tried to solve this problem using Suffix Tree (ukkonen95) and got MLE on test #9, what trick did you use to reduce the memory? Then I saw this discussion about Suffix Array, I tried Larsson-Sadakane algorithm and got WA on test #8. Then I tried Karkkainen-Sanders algorithm and got TLE on test #9. I haven't try to use Suffix Automaton yet. This problem is really hard. Anyone can give hints about reducing memory for the Suffix Tree? Kit Re: I got MLE, TLE on test #9, WA on test #8 :( [2] // Problem 1517. Freedom of Choice 23 Dec 2006 12:09 Felix Halim wrote 23 December 2006 09:37 I tried to solve this problem using Suffix Tree (ukkonen95) and got MLE on test #9, what trick did you use to reduce the memory? No tricks, I have almost double reserve in memory. But I use hash working with edges, may be that's the matter.Test #8 is extremally small, so you can find similiar manually. #9 is just the first large test. Good luck! Felix Halim Re: I got MLE, TLE on test #9, WA on test #8 :( [1] // Problem 1517. Freedom of Choice 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? Felix Halim Suffix Array seemed a lot faster in implementation // Problem 1517. Freedom of Choice 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 :) EfremovAleksei Re: I got MLE, TLE on test #9, WA on test #8 :( [8] // Problem 1517. Freedom of Choice 23 Dec 2006 17:18 >This problem is really hard. Anyone can give hints about >reducing memory for the Suffix Tree? I also had MLE#9, after that I saved at node of suffix tree only used links to child And got AC. It reduced memory, but I my prog eat 30mb. Felix Halim Re: I got MLE, TLE on test #9, WA on test #8 :( [7] // Problem 1517. Freedom of Choice 23 Dec 2006 22:18 Those who solved it using Suffix Trees: Did you built 2 Suffix Trees or just 1? 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 "#". Or is it better to create 2 Suffix Trees and compare the two trees? Or there is a way to build a Suffix Tree only for the first string and try to find the LCS with the second string using that Tree. Did you get AC using the first algorithm? second? or the last? Thanks Kit First way (-) [2] // Problem 1517. Freedom of Choice 24 Dec 2006 10:52 Ngô Minh Đức Re: First way (-) [1] // Problem 1517. Freedom of Choice 25 Dec 2006 17:48 I use hashing but my algorithm is O(n(logn)^2), is it a better way? Here is my algorithm: m = the result l = length(m) - Do a binary search on l Check whether there is a common substring length l: + Calculate and sort hash values of string 1 (into array f) + For each value in string 2, search it in f, check whether there is a match! Vedernikoff Sergey Re: First way (-) // Problem 1517. Freedom of Choice 25 Dec 2006 22:12 What is double hash??? My single hash O(N*logN) prog. got AC within 0.671 sec. and 6,... MB memory. cpphamza Re: I got MLE, TLE on test #9, WA on test #8 :( [3] // Problem 1517. Freedom of Choice 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? Felix Halim Re: I got MLE, TLE on test #9, WA on test #8 :( [2] // Problem 1517. Freedom of Choice 5 Jan 2007 22:35 Don't traverse the tree using recursion ;) Try using explicit array[100000] cpphamza Re: I got MLE, TLE on test #9, WA on test #8 :( [1] // Problem 1517. Freedom of Choice 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? Felix Halim Re: I got MLE, TLE on test #9, WA on test #8 :( // Problem 1517. Freedom of Choice 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 [SPbSU ITMO] WiNGeR Update // Problem 1517. Freedom of Choice 9 Feb 2007 20:51 [SPbSU ITMO] WiNGeR Update [11] // Problem 1517. Freedom of Choice 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)? Ilya Grebnov[Ivanovo SPU] Re: Update // Problem 1517. Freedom of Choice 11 Feb 2007 13:41 Suffix array can be constructed in O(n) time by Karkkainen-Sanders algorithm. Felix Halim Re: Update [7] // Problem 1517. Freedom of Choice 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 Chalyshev Vladimir [cmd] Re: hashing [2] // Problem 1517. Freedom of Choice 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? KIRILL(ArcSTUpid coder:) Re: hashing [1] // Problem 1517. Freedom of Choice 30 Nov 2007 19:25 try 64bit hashing Cheryl Xie Re: hashing // Problem 1517. Freedom of Choice 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? Rafail Ahmadisheff Suffix Automata are simple [3] // Problem 1517. Freedom of Choice 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). SPIRiT Hints for impementingsuffix trees [2] // Problem 1517. Freedom of Choice 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). georgi_georgiev nlogn // Problem 1517. Freedom of Choice 31 Aug 2009 13:14 I just did it with hash and my own hash table for 0.265 sec and 7mb memory. daftcoder [Yaroslavl SU] Re: Hints for impementingsuffix trees // Problem 1517. Freedom of Choice 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 -XraY- Re: Update [1] // Problem 1517. Freedom of Choice 27 Oct 2011 02:42 Edited by author 27.10.2011 02:46 -XraY- Re: Update // Problem 1517. Freedom of Choice 27 Oct 2011 02:45 Edited by author 27.10.2011 02:46 Rostislav Re: I got TLE on #28, with single hash solution. [2] // Problem 1517. Freedom of Choice 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? Ilya Grebnov[Ivanovo SPU] Re: I got TLE on #28, with single hash solution. [1] // Problem 1517. Freedom of Choice 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. Rostislav Re: I got TLE on #28, with single hash solution. // Problem 1517. Freedom of Choice 18 Feb 2007 12:45 Thank's. ONU_1785 Re: I got TLE on #28, with single hash solution. [1] // Problem 1517. Freedom of Choice 30 Apr 2012 05:47 Just got 0.96s and 28M memory with suffix automaton. How do i make it fast? Alexey Dergunov [Samara SAU] Re: I got TLE on #28, with single hash solution. // Problem 1517. Freedom of Choice 30 May 2012 01:53 String hashes + binary search: 0.468 s String hashes + hashset: 0.234 s Mahilewets Re: I got TLE on #28, with single hash solution. // Problem 1517. Freedom of Choice 26 May 2017 21:27 Suffix automation AC C++ MSV2013 0.093 sec 22 MB, yeah Kit Re: Several hash-based solutions got AC (+) // Problem 1517. Freedom of Choice 22 Dec 2006 16:15 Actually, not any hash is suitable here. Burunduk1 Re: The solutions of the authors are based on suffix trees and suffix arrays // Problem 1517. Freedom of Choice 17 Dec 2006 16:22 Why not suffix automaton? It is much easier to implement and, of course, gets AC =) Aman Re: Several hash-based solutions got AC (+) // Problem 1517. Freedom of Choice 6 Apr 2017 20:53 This problem can be solved using using suffix tree. Here are some of the String processing programs http://www.techcrashcourse.com/2014/10/c-program-copy-string.html http://www.techcrashcourse.com/2014/11/c-program-convert-string-to-integer-atoi.html http://www.techcrashcourse.com/2014/11/c-program-remove-extra-spaces-string.html http://www.techcrashcourse.com/2014/11/c-program-check-anagram-strings.html dorrungin Re: Several hash-based solutions got AC (+) // Problem 1517. Freedom of Choice 22 Aug 2022 08:21 |