Show all threads Hide all threads Show all messages Hide all messages  WA#52  Anwar  1517. Freedom of Choice  17 Sep 2018 23:58  1  WA#52 Anwar 17 Sep 2018 23:58 Plz help me, I used hashing with binary search and got WA on 52.  WA #9  10100  1517. Freedom of Choice  14 Apr 2018 07:03  1  WA #9 10100 14 Apr 2018 07:03 use N = 100001 instead N = 100000  Clang C++14 Compiler Failed  Mahilewets  1517. Freedom of Choice  10 Jul 2017 19:55  1  I have got a verdict Compiler Failed on Clang compiler. Never have got such a verdict. Every other compiler submit gets AC. Can't post code here because it is a working solution.  _getchar_nolock can really boost your code  Mahilewets  1517. Freedom of Choice  27 May 2017 09:56  2  So at first I got AC in 68 ms using scanf("%c", *char) and then I replaced scanf with_getchar_nolock() and got AC in 46 ms... And 31 ms with _putchar_nolock!  Just curious  Ivan Ivanov  1517. Freedom of Choice  26 May 2017 21:27  46  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? 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. Test 10 was very hard for binary+hash solutions,but double or triple hash would pass it. 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. 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! Single hashbased solution got AC too I got AC with optimized single hashbased solution too. But if I wrote double hash based solution I wouldn't have +9. I got TLE on #28, with single hash solution. The simplest solution with single hash gets AC in 0.468 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 I write Suffix Tree(Ukkonen Algorithm). AC  1 sec. But I used 30mb memory. 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 LarssonSadakane algorithm and got WA on test #8. Then I tried KarkkainenSanders 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? 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! 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? 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 :) >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. 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 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! What is double hash??? My single hash O(N*logN) prog. got AC within 0.671 sec. and 6,... MB memory. 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? Don't traverse the tree using recursion ;) Try using explicit array[100000] 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? 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 [SPbSU ITMO] WiNGeR 9 Feb 2007 20:51 Update [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 Ilya Grebnov[Ivanovo SPU] 11 Feb 2007 13:41 Suffix array can be constructed in O(n) time by KarkkainenSanders algorithm. Hi WiNGeR, You might be interested to see this demo about creating Suffix Array in linear time by Juha Karkkainen and Peter Sanders: http://felixhalim.net/pg/suffixarray/index.php Do you have any reference on how to build Suffix Automaton? Which one is simpler? Suffix Tree or Automaton? Thanks i relalize double hashing, but i get tle on test 9. Can anybody get me hashfunctions used in solution on this problem? 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? 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://wwwigm.univmlv.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). 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 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. 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 Edited by author 27.10.2011 02:46 Edited by author 27.10.2011 02:46 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? 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. Just got 0.96s and 28M memory with suffix automaton. How do i make it fast? String hashes + binary search: 0.468 s String hashes + hashset: 0.234 s Suffix automation AC C++ MSV2013 0.093 sec 22 MB, yeah Actually, not any hash is suitable here. Why not suffix automaton? It is much easier to implement and, of course, gets AC =)  Suffix Automata  Takanashi Rikka  1517. Freedom of Choice  4 Mar 2016 15:36  1   What is Test #12?  Binary_Mind [RAU]  1517. Freedom of Choice  16 Sep 2015 13:19  1  Edited by author 16.09.2015 13:22  WHAT'S TEST 7?  invokerj  1517. Freedom of Choice  3 Dec 2013 12:00  1  my solution WA7, anyone post more test? thanks!  WHAT'S TEST 7?  invokerj  1517. Freedom of Choice  3 Dec 2013 12:00  1  my solution WA7, anyone post more test? thanks!  Hashing ...  vlyubin  1517. Freedom of Choice  23 Nov 2013 18:00  3  It seems that lots of people can solve this problem with hashing. Well, I'm using 64 bit hashing and am using sufficiently large prime p (I'm using the usual polynomial hashing i.e. s[0]+s[1]*p+s[2]*p*p ...). I have tried 5 different p's and I'm always catching collisions at test 52 !!! I added code to check for collision and keep working with a different random chosen p ... and now I get TL !!! My question is: what is the smart solution to the problem that I have? What hashing have you used? To admins: How can you guys make solutions with random p get collisions? That's probably a really good test. I know how to build antihash for certain p, but I cannot imagine a test that hacks 10 random p's in a row. Good job! Or more like "my solution sucks" :) QProgS 1517. Свобода выбора Visual C++ 2010 Accepted 0.656 9 720 КБ Accepted with double hashing ) Edited by author 23.11.2013 18:01  Help pleased . My Suffix Array wa on test # 3 ???  Eazy jobb  1517. Freedom of Choice  1 Aug 2013 13:09  3  [code deleted]  I've got AC. If you wa on test#3 , you should wirte your OWN suffix array base on your UNDERSTANDING cause it's too easy . If you want my help , just send me an email . adress : ngziming@gmail.com .  pleased try this data input: 5 CCCCC CCCCC output: CCCCC  hint: remeber to add a nouse char at the last of the string .  Edited by author 16.08.2012 09:29  can this problem solved with dp.  runtime_error  1517. Freedom of Choice  29 Jul 2013 15:07  1  i tried to solve this problem with dp. O(N*2) time and O(N) memory: here is my code #include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; int n; string s,t; string Longest_common_substr(void) { int place; int longest=0; vector<int> m(n); for(int i=0;i<n;i++) { for(int j=n1;j>=0;j) { if(s[j]==t[i]) { if(j!=0)m[j]=m[j1]+1; else m[j]=1; } else m[j]=0; if(m[j]>longest) { longest=m[j]; place=jlongest+1; } if(longest==n)return s.substr(place,longest); } } if(longest==0)return ""; else return s.substr(place,longest); } int main() { ios::sync_with_stdio(0); cin.tie(); cin>>n; cin>>s; cin>>t; cout<<Longest_common_substr()<<endl; return 0; } can you please suggest any modifications?  Problem 1517 "Freedom of Choice" was rejudged.  ...†.†.†... Stigius ...†.†.†...  1517. Freedom of Choice  21 Jul 2012 18:51  6  Some new tests were added. 127 authors lost their AC. Теперь изза антихеш тестов все задачи перерешивать? Спасибо :) Всегда пожалуйста. Очередной реджадж уже в процессе. Suffix Array Without Longest Common Prefix O(N*logN) 0.312 Edited by author 31.01.2014 21:34 Antihash tests are дрочерство.  WA9  severin  1517. Freedom of Choice  1 Jun 2012 20:53  1  WA9 severin 1 Jun 2012 20:53 Does anyone see what goes wrong with my program for the input of test #9? or test inputs maybe? EDIT: Test Case found! Edited by author 01.06.2012 22:08  why N*(logN)^2 have TLE 19? N = min(N,M)  Giorgi Pataraia [Tbilisi SU]  1517. Freedom of Choice  23 May 2012 15:30  1  my algo Accepted in 0.4s. Edited by author 23.05.2012 16:24  What i have to write in this case PLEASE HELP  Valentin Ro  1517. Freedom of Choice  12 Sep 2011 22:18  3  17 WEARECHAMPIONSYES WEHAVECHAMPIONSNO What should I write in this case ??? Sory my english Edited by author 10.04.2011 23:15 Edited by author 10.04.2011 23:16  WHAT WILL HAPPEN IF SPEECHES ARE TOTALLY DIFFERENT.PLEASE HELP  Anupam Ghosh,Bengal Engg and Sc Uni,MtechIT,200609,India  1517. Freedom of Choice  10 Jul 2008 13:01  2  You should output empty string.  why WA1? please suggest some tricky test cases  Anupam Ghosh,Bengal Engg and Sc Uni,MtechIT,200609,India  1517. Freedom of Choice  8 Jul 2008 15:40  1   Solving this problem with method of "PAZNAVANIA" (AC)  Giorgi Beridze[IBSU_Tbilisi]  1517. Freedom of Choice  17 Feb 2008 00:19  3  You can't solve this problem without paznavania, this is an unic method of solving. This method was created in the 12 century, by Greece phylosofers, but unfortunately, is destroied now, because Greece enemies destroies it. But there are legends that some nations stole the method of paznavania and I surely know that who solved this problem is a representative of that nation who stole, because, as you know, without paznavania this problem couldn't be solved... :(((( Edited by author 17.02.2008 00:48 Yes,I think that you are right,but I think that you were not right in the afternoon
Edited by author 17.02.2008 00:22 I agree with you, but I see that you don't know the history of this method very well. Method "Paznavania" is the result of developing of method "Dazozorivanie", which was created in ancient times and later, stepbystep it reached it's highest perfection and was given a new name "paznavanie"(by its developer Numanchik Paznavaius). I tried to test method "dozozorivanie" but unfortunately there is time limit problem:( so "paznavanie" is the one method to solve this problem. Edited by author 17.02.2008 00:55  Suffix tree construction  Giorgi Saghinadze (Tbilisi SU)  1517. Freedom of Choice  16 Feb 2008 23:35  4  How to construct suffix tree in N*log(N) time? I am searching it in internet for 2 days and can't find site where all will be explained clearly. If you now link where suffix tree constuction algorithm is explained clearly give me please. thanks. Actually, you'll find it possible to construct a Suffix Tree in O(N) (: First such algo was offered by Weiner in 1973. Some new ideas have sprung to life since then. I believe, nowadays Ukkonen's algorithm for online suffix tree construction is your best choice for most applications. http://en.wikipedia.org/wiki/Ukkonen's_algorithmI personally tried a pair of its implementations: 1) Using explanation by Lloyd Allison ( http://www.allisons.org/ll/AlgDS/Tree/Suffix/ ) and implementation by Stephan T. Lavavej ( http://nuwen.net/libnuwen.html ) as base, I coined some C++ code... It got TLE 12. 2) Then I considered Dan Gusfield's book "Algorithms on Strings, Trees and Sequences" (Strictly speaking, I was reading Russian translation by Romanovsky  if it matters). And, you know, they made some sample programs in C available online ( http://www.cs.ucdavis.edu/~gusfield/strmat.html ) TLE 10 was the best judgement result I ever saw on this attempt. I finally solved the problem with DAWGs (also known as Suffix Automata). This time I referred to "Automata for Matching Patterns" by Maxime Crochemore and Christophe Hancart for ideas, proofs and samples all along ( http://wwwigm.univmlv.fr/~mac/REC/B4.html ). AC in 0.125 s. Thus I got disappointed with Suffix Trees: despite them being good for theoretical considerations, in practice I'd rather be using Suffix Automata from now on. In this problem there is a big another problem: Create rather many triks to implement suffix tree maximally compact, because test were very optimized by authors. For example such structure as vector is unsatisfactory for description of adjast list in each node. I were forced to organize dynamic memory allocation by small parts for each new edge in int *smeg with rewriting stored information. 

