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?
EDIT: itachi0012 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$$$.
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}$$$.