Discussion @ 1393. Average Common Prefix @ Timus Online Judge

Einstein Chen(einstein[underline]csm[at]hotmail[dot]com) To Admin: more memory please [10] // Problem 1393. Average Common Prefix 9 Mar 2006 07:37

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

Kit Re: To Admin: more memory please // Problem 1393. Average Common Prefix 10 Mar 2006 22:19

I used suffix tree also and there is enough memory. But, as you notice, it is quite difficult...

GaLL[Tyumen SU] Re: To Admin: more memory please [4] // Problem 1393. Average Common Prefix 10 Mar 2006 23:51

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

Grebnov Ilya[Ivanovo SPU] Hint (+) [3] // Problem 1393. Average Common Prefix 11 Mar 2006 14:27

Problem can be easy solved without Suffix Tree. Try Suffix Array. Suffix array can be easy constructed in O(N*ln(N)*ln(N)) time with 8*N bytes addition memory.

See this
http://acm.timus.ru/status.aspx?space=1&num=1393&status=accepted&pos=1021243

Edited by moderator 11.03.2006 16:59

Alias (Alexander Prudaev) Re: Hint (+) [2] // Problem 1393. Average Common Prefix 18 Mar 2007 21:39

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

Ilya Grebnov[Ivanovo SPU] Re: Hint (+) [1] // Problem 1393. Average Common Prefix 19 Mar 2007 10:56

Edited by author 25.11.2007 16:05

Edited by author 25.11.2007 16:05

Alias (Alexander Prudaev) Re: Hint (+) // Problem 1393. Average Common Prefix 19 Mar 2007 15:27

by the way, this problem can be solved in O(n) time :)
but a don't know these algorithms

Einstein Chen(einstein[underline]csm[at]hotmail[dot]com) Re: To Admin: more memory please [2] // Problem 1393. Average Common Prefix 11 Mar 2006 15:03

Great thanks to Kit,GaLL[Tyumen SU],Grebnov Ilya[Ivanovo SPU].
After several of MLEs,finally ACed using suffix tree :)

http://acm.timus.ru/status.aspx?space=1&num=1393&status=accepted&pos=1113397

Kit Re: To Admin: more memory please [1] // Problem 1393. Average Common Prefix 11 Mar 2006 16:16

Just for interest, why you use dirty account? I don't blame you, but I don't see reasons for such fraud. Why?

Dmitry 'Diman_YES' Kovalioff All the dirty account found will be deleted soon. Enjoy the last days of freedom :) (-) // Problem 1393. Average Common Prefix 11 Mar 2006 17:01

Einstein Chen(einstein[underline]csm[at]hotmail[dot]com) No subject // Problem 1393. Average Common Prefix 11 Mar 2006 18:12

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

Discussion of Problem 1393. Average Common Prefix