Discussion @ 1635. Mnemonics and Palindromes @ Timus Online Judge

Evgeny finally accepted [3] // Problem 1635. Mnemonics and Palindromes 2 Feb 2013 15:29

maybe it will be useful (or at least interesting) for somebody.

at first i tried to make simple DP with O(n^3).
i tried in java (and i received TLE in 32th test).

after that i tried to realize greed algorithm and understood that this idea is wrong (simple antigreed test is: "abzzbbbzza")

aand finally i've made O(n^2) DP.
little hint: try to precalc d[l][r]:
d[l][r] = true, s[l..r] - palindrom
d[l][r] = false, s[l..r] - not palindrom

Rahul Agarwal Re: finally accepted [1] // Problem 1635. Mnemonics and Palindromes 14 Jun 2013 23:32

whats the ans for 'abzzbbbzza'?

sylap Re: finally accepted // Problem 1635. Mnemonics and Palindromes 19 Jun 2013 12:32

4
a b zzbbbzz a

chomu1850 Re: finally accepted // Problem 1635. Mnemonics and Palindromes 22 Nov 2015 20:37

i didn't get it how it will become n^2 because for l=1 to l=n is one loop and for r=l to r=n is inside loop and for checking it is palindrome is another loop so i don't get how it will be n^2 can you please explain me

i am very confused here please help me

Discussion of Problem 1635. Mnemonics and Palindromes