ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1393. Average Common Prefix

To Admin: more memory please
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...
Re: To Admin: more memory please
Posted by Kit 10 Mar 2006 22:19
I used suffix tree also and there is enough memory. But, as you notice, it is quite difficult...
Re: To Admin: more memory please
Posted by GaLL[Tyumen SU] 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
Hint (+)
Posted by Grebnov Ilya[Ivanovo SPU] 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
Re: To Admin: more memory please
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
Re: To Admin: more memory please
Posted by Kit 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?
All the dirty account found will be deleted soon. Enjoy the last days of freedom :) (-)
Posted by Dmitry 'Diman_YES' Kovalioff 11 Mar 2006 17:01
No subject
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
Re: Hint (+)
Posted by Alias (Alexander Prudaev) 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
Re: Hint (+)
Posted by Ilya Grebnov[Ivanovo SPU] 19 Mar 2007 10:56

Edited by author 25.11.2007 16:05

Edited by author 25.11.2007 16:05
Re: Hint (+)
Posted by Alias (Alexander Prudaev) 19 Mar 2007 15:27
by the way, this problem can be solved in O(n) time :)
but a don't know these algorithms