I tried this problem on Hackerearth :

The editorial is not provided, just the code is there. I cannot understand how the author did it.

Please try this problem and please explain the approach. Can this also be done using combinatorics?

Edit 1: I spent my whole day waiting for the solution from CF community. I don't know why anyone doesn't want to help a struggling coder. :(

Edit 2: I would request people that if they cannot help then atleast don't downvote someone's blog.

Edit 3: I was wrong about the CF community. You all are kind and helpful people. :D

waiting! I also stuck in this problem before

How do you know that it is an interview problem?

It got asked in a hiring challenge. Please solve it, I know you can.

EDIT: itachi001 pointed out below that e.g. a good string $$$caaac$$$ doesn't come from a good string shorter by $$$2$$$, so my idea is incorrect.

I would try extending a special string by adding a new character to the beginning and to the end at the same time. If we make some long palindrome-prefix, there was already some. So we should watch out only for palindrome-prefixes of length 2 or 3. I think the solution should be something like $$$dp[n] = dp[n-2] \cdot (k-2)$$$ unless $$$n$$$ is small. Does it make sense?

"If we make some long palindrome-prefix, there was already some. So we should watch out only for palindrome-prefixes of length 2 or 3" — Couldn't get this part

The recurrence in author's solution is this:

if ( i%2 )

else

I read both two comments and thought about it for ~15 minutes and still have no idea what is going on. Please, help!

Let's say $$$S$$$ was a good string and now we append a character $$$c$$$ to both sides. We get $$$cSc$$$. If it is for example $$$cabacxrzy...$$$ then we get a bad prefix. But hey, $$$aba$$$ was already a bad prefix in string $$$S = abacxrzy...$$$

So, lemma: if string $$$cSc$$$ has a bad prefix of length $$$L \geq 4$$$ then $$$S$$$ wasn't a good string because it had a bad prefix of length $$$L - 2$$$.

Now I get it.

Thanks Errichto for taking out time for this.

You are awesome :D :D

what about cases like "caaac". Are we accounting this case with this recurrence.

It isn't a good string and neither is "aaa".

but i guess for n=5 this is a valid case how we are going to account for this!!

Oh, you are right. There are good strings such that its interior isn't a good string. I don't know how to count that though :D

ok.. your logic was good and easy to understand.. i didn't get the recurrence mentioned by author The recurrence in author's solution is this:

if ( i%2 )

dp[i] = ( K * dp[i-1] ) — dp[ ( i + 1 ) / 2 ] else

dp[i] = dp[i-1] ; can u explain this

Somebody already pasted it. If I could explain it, I would already do that ;p

oops!! my mistake.. thanks though.

300iq Um_nik Radewoosh rng_58 majk Swistakk Xellos antontrygubO_o Lewin neal

please,if anyone of you could solve

Stuck on it since days.

I figured it out!

Take all palindromes with length $$$N$$$ and subtract the number of palindromes that have a palindromic prefix. When the smallest palindromic prefix of our palindrome has length $$$k$$$, we just need to take that and append $$$N-k$$$ characters. The last $$$k$$$ characters are uniquely defined and the rest can be chosen in any (palindromic) way, so we have 2 cases:

Notice that in the latter case, if the last $$$2k-N$$$ characters of our prefix don't form a palindrome, we can't make a palindrome with length $$$N$$$, so it seems like we need to count something different — palindromes that don't have a non-trivial palindromic prefix but have a palindromic suffix. Fortuniately, if a palindrome has a palindromic suffix with length $$$l$$$, it obviously also has a palindromic prefix with length $$$l$$$, so the only option for $$$2k > N$$$ is $$$2k = N+1$$$.

Now it's obvious how to solve this with $$$O(N^2)$$$ DP. To speed up to $$$O(N + \log mod)$$$, use multiplicative inverse and remember sums of $$$c_k K^{-2k}$$$.

Thank You Xellos. You are a life saver :)