|
|
Oh. My. God. JEBUS! I ACed it! Just use suffix array + Kasai and it will work out just fine. Trust me :) But also here is what I collected about test 30 : * Size of the string = 250000. * All letters of English alphabet are being used. * If we divide the string into heterogeneous and homogeneous regions, then the latter forms a majority. Moreover, longest homogeneous region = 396 and heterogeneous = 6. * The amount of divergent adjacent characters is between 5000 and 10000. Hope it helps :3 5 AAAAA ans:5.000 6 CBDCBD ans:3.600 6 DDADDD ans:2.000 They helped me to solve this problem~ Hope they can help you o(∩_∩)o... Test "DDADDD" is really nice. My program shows different results for different shifts of that string. For first two shifts it shows 2.0 and for the next four it shows 1.4,1.8,2.2 and 1.2 respectively suffix array + HESH = WA 67 , why please give me some test Edited by author 08.11.2013 17:06 Try to avoid hashes does size of T equal to n or not? could you give me your email ? I will send you my code and you will give me your advice a have got WA67 when i use polynomial hash module to multiple of two (up to 96bit hash). try to modify your hash, or use another algo. ( my ac solution uses suffix array with hash ;) ) New timelimit is 1.5 seconds. All solutions were rejudged. I found a test that might be you don't have: input: 2 AA output: 2.000 my program accepted even it's not passed this test. plase add this test as a variant Your test was added. Thanks. i also use suffix array.but i can ac it. It's O(nlogn + n). I use suffix array to solve this problem...but i've WA 30 many times and don't know why. Can someone give me some hint or tests ? for var 'ans' use __int64 type. and printf( "%.3lf\n", (ans+0.0)/(n-1) ); I use only polinomial hash and sort. Dont use base 97, it would have wa52. Base 29 with 32bit hash works fine. I find mistake and got AC Edited by author 08.08.2011 20:44 The statement says "The only line of the output should contain the Average LCP of T with 3 digits after decimal point. " Is this with rounding or without? I'm using printf("%0.3lf") and keep on getting WA 35 Can somebody tell what's the reason of WA 35? I think it's not rounding. Do you use long long to count total length of common prefixes? Try a test like AAA...AAA (250000 times) I've tried both long long and double. There's no problem with such test. Could you give me test #10? I made an algorithm which runs in O(n*logn*logn)which gives the same results as the trivial one (sort for suffix array and then comparing every two adjacent O(n^3)), but it doesn't pass this test, while the previously mentioned trivial one does (it gets stuck at #29). I supose I have some kind of trivial error, so it would be rather helpfull. I got WA#29 so many times. I can't find the mistakes from my program. By the way,is that something wrong with my "reading" part? Here is my reaing part: procedure init; begin readln(m); for i:=1 to m do begin read(ch); a[i]:=ord(ch); end; readln; end; 250000 AA...A Edited by author 16.03.2009 19:41 And test 30? I reach both memory limit and time limit. I wrote an O(n*log(n)) algorithm, but have got a TL. I think this is a problem of Java language (there are arrays and garbage collector due to small memory limit). And I saw that there is no AC on this problem using Java. Can You change time-limit for Java on this task? Edited by author 20.09.2007 15:54 If it's N*log(N) due to sorting, you can implement it at O(N) via bucket sorting. Bucketing array can be filled at O(N) along with list of non-empty buckets. Later this list can be used for O(N) sorted array traversal and for fast cleanup before further sorts. My solution using suffix tree got MLE... Here is the definition of suffix tree node: typedef struct node *point; struct node { point ParentLink,SuffixLink; point Child,Brother; int FirstCharIndex,LastCharIndex,Depth; int ID; } sizeof(node)=32 A suffix tree of a n-length string has at most 2*n nodes, so the tree may use 32*2*250000=16MB memory and lead to MLE. Please RELAX THE MEMORY LIMIT or tell me how to reduce the space requirement of suffix tree. Thanks... I used suffix tree also and there is enough memory. But, as you notice, it is quite difficult... You can use bit fields: struct node { point ParentLink,SuffixLink; point Child,Brother; int FirstCharIndex:24,LastCharIndex:24,Depth:24; int ID:24; } sizeof(node)=28 to Grebnov Ilya[Ivanovo SPU] : i have tried to find information about constructing suffix array using google, but all information is in english. please give me some links, or if you can, please send me your implementation. Edited by author 18.03.2007 21:39 Edited by author 25.11.2007 16:05 Edited by author 25.11.2007 16:05 by the way, this problem can be solved in O(n) time :) but a don't know these algorithms Just for interest, why you use dirty account? I don't blame you, but I don't see reasons for such fraud. Why? i use it just for fun... if all of you think that it's a fraud,i will not use it any longer and sorry Edited by author 05.04.2006 22:25 i don't know why i got wrong answer. If i use suffix array, i get wrong answer in test 3. But when i use a same string concentrate after input string (s[1]...s[n]s[1]...s[n]), i got time limit exceeded in test 30. Can any one help me???????? i don't know, if i don't, i got wrong answer in test 3. I made many test for this problem, and two ways both get the same result. To Admin: Would you give me test #3! 6 ABABAB Thank you, i got accepted :). i need to priority start point of suffix when two suffix have the same order. |
|
|