ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1635. Mnemonics and Palindromes

finally accepted
Posted by Evgeny 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
Re: finally accepted
Posted by Rahul Agarwal 14 Jun 2013 23:32
whats the ans for 'abzzbbbzza'?
Re: finally accepted
Posted by sylap 19 Jun 2013 12:32
4
a b zzbbbzz a
Re: finally accepted
Posted by chomu1850 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