saint_coder's blog

By saint_coder, 4 weeks ago, , 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 #dp, Comments (18)
 » 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.
 » 4 weeks ago, # | ← Rev. 4 →   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?
•  » » 4 weeks ago, # ^ | ← Rev. 5 →   "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 partThe 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] ;
•  » » » 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 ] elsedp[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.
 » 3 weeks ago, # | ← Rev. 5 →   please,if anyone of you could solveStuck 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: if $2k \le N$, there are exactly $K^{N-2k}$ ways to append $N-k$ characters if $2k \gt N$, there's at most one way to do that 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 :)