Discussion @ 1646. Godzilla Strikes Back! @ Timus Online Judge

Help me !!!

Posted by Asyamov Igor 25 Oct 2008 18:29

I use map<int,string> why it got MLE 5????

Edited by author 25.10.2008 18:30

Re: Help me !!!

Posted by Vedernikoff Sergey (HSE: EconomicsForever!) 25 Oct 2008 19:59

In maxitest length of the string may be as large as 10*2^100 =)

Re: Help me !!!

Posted by Asyamov Igor 25 Oct 2008 20:34

so and what kind of problems it is????

Re: Help me !!!

Posted by Vedernikoff Sergey (HSE: EconomicsForever!) 25 Oct 2008 20:43

Dynamic programming

Re: Help me !!!

Posted by Asyamov Igor 25 Oct 2008 20:52

really??
I can't imagine how it could be solve with the help of dynamic....
could you tell me your idea????

Re: Help me !!!

Posted by Tbilisi SU: Giorgi , Akaki , [Andrew] 27 Oct 2008 16:39

for each DNA you must store number of occurences Godzilla's DNA in it, and prefix and suffix of this DNA, which length is less by one, than Godzilla's DNA s length. with this information you can easily compute next DNA

Edited by author 27.10.2008 16:41

Re: Help me !!!

Posted by Asyamov Igor 27 Oct 2008 21:10

Thank you!!! Now AC :) !!!

Why MLE?

Posted by MOiAIS 28 Oct 2009 23:29

MOiAIS 1646 Java Memory limit exceeded 5 0.125 40 330 КБ

My program used 40 MB, but restrictions - 64 MB. Why MLE?

Discussion of Problem 1646. Godzilla Strikes Back!