Discussion @ 1635. Mnemonics and Palindromes @ Timus Online Judge

Time Limit Excedent test 32 wow

Posted by JAVATO 15 Oct 2008 08:36

my program
O(N*N) java solution
:(

Re: Time Limit Excedent test 32 wow

Posted by Anisimov Dmitry (Novosibirsk STU) 15 Oct 2008 20:53

I think you solution is really O(N^3), because comparing strings takes O(N) time, not O(1), and true O(N^2) is extremely unlikely to get TL.

Edited by author 15.10.2008 20:54

Re: Time Limit Excedent test 32 wow

Posted by svr 15 Oct 2008 21:03

The problems has good DP structure:
array of sentres of possible first pallindrom, each such
center is renewed for O(1) when i:=i+1

Re: Time Limit Excedent test 32 wow

Posted by JAVATO 20 Oct 2008 06:41

is true, my solution is O(N^3)
:( slow

Discussion of Problem 1635. Mnemonics and Palindromes