Discussion @ 1635. Mnemonics and Palindromes @ Timus Online Judge

JAVATO Time Limit Excedent test 32 wow [3] // Problem 1635. Mnemonics and Palindromes 15 Oct 2008 08:36

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

Anisimov Dmitry (Novosibirsk STU) Re: Time Limit Excedent test 32 wow [1] // Problem 1635. Mnemonics and Palindromes 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

JAVATO Re: Time Limit Excedent test 32 wow // Problem 1635. Mnemonics and Palindromes 20 Oct 2008 06:41

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

svr Re: Time Limit Excedent test 32 wow // Problem 1635. Mnemonics and Palindromes 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

Discussion of Problem 1635. Mnemonics and Palindromes