Got AC. There were "Time Limit Exceeded" at tests 32, 56, 59, 60 before i made some complicated enhancements to my program. The monitor have shown smth around 0,9 second for some tests, so it was pretty close.

My algo uses O(N*N) memory and O(N*Ln(N)) or O(N*N) operations (depends on input string; there are too slightly different ways of algorithm). I suppose there should be better solution. Any hints about that?

Edited by author 12.10.2008 05:22

how did you do in O(N*Ln(N)) or O(N*N) operations ?
I got AC, but my solution use 0.5+s, it's too slowly.
I use O(N*N) find all Palindromes, and use greedy, memorize search

oh, O(N*N) dynamic programing will get 0.1s

Cool. At first, I wrote O(N^3). It was too slow. I wrote hash cutoff it so it was close to O(N^2), though, worst-case still O(N^3), got AC. Today I realize there is O(N^2) solution and read mention of O(N*log(N)).

Is O(N*log(N)) bestcase? Is worstcase still O(N^2)?

Edited by author 12.10.2008 20:22