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...

suffix array + HESH    = WA 67 , why

please give me some test

Edited by author 08.11.2013 17:06

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

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 ?

I use only polinomial hash and sort.
Dont use base 97, it would have wa52.

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

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;

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?

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...

Edited by author 05.04.2006 22:25