Problem LinkSetter: Hasan Jaddouh Tester: Amr Mahmoud Editorialist: Bhuvnesh Jain DifficultyMEDIUM PrerequisitesCombinatorics ProblemGiven a string S and an integer K. Find the number of strings, T, having the same length as S such that T is palindrome and the hamming distance between S and T is at most K. Some Hints/TricksTry to think about how changing an index in left part or sting S, forces us to operate on the corresponding right index to maintain the palindromic property satisfied in final string. Try to find a combinatorial formula for it. Precompute some sums (or formulas) to get an overall complexity of $O(n)$. ExplanationThe question can be reframed as "Find the number of strings which can be formed by changing at most K characters in S, so that resulting string becomes a palindrome." Assume, 0based indexing in the editorial. The strings $T$ that we need to form should be palindrome. This restricts how we modify some characters from string $S$. Thus, we define 2 terms here:
Based on these terms, we can clearly see that the all possible strings, with given counts of "Fixed" and "nonFixed" indices, will give the same answer. This is because the answer depends on whether we chose to perform an operation on given index or not and this may force us to perform some operation on another index so that final string remains palindrome. These operations don't depend on the characters present at that location in the string. Thus, to calculate the complete answer, we need to evaluate 2 functions, namely:
From the definition of above 2 functions, it is easy to see that the final answer is as follows: $F(S, k) = \sum\limits_{i = 0}^{i = k} f1(Fixed, k  i) * f2(nonFixed, i)$ Some simplification, before we proceed (assuming we can implement the above functions efficiently). What happens when the length of the given string is odd. The middle character will be not be treated as "Fixed" or "nonFixed". But, it is clear that we can change this character without affecting the palindromic property in final string. To fix this, we can either change that character or not. Thus, final answer, in this case, would be as follows: $ans = F(S, k) + 25 * F(S, k1)$. Now, let us come back to the evaluation of functions $f1(Fixed, k)$ and $f2(nonFixed, k)$ defined before. These are given by following formulas : $f1(Fixed, k) = \sum\limits_{x = 0}^{x = floor(k/2)} {{{Fixed}\choose{x}} {25}^{x}}$ $f2(nonFixed, x + 2*(nonFixed  x) <= k) = {{{nonFixed}\choose{x}} * {2}^{x} * {24}^{nonFixedx}}$, provided that $(x >= 0 \text{ and } x <= nonFixed)$ The reasoning is as follows:
Implementing the above full idea naively will take $O(N^2)$ time as there will be double summations. The trick is to precompute the function $f1(Fixed, k)$ and compute the final answer, $F(S, k)$ in such a way that function $f2(nonFixed, k)$ is computed on the fly. To compute $f1(Fixed, k)$ for all values of $x$, such that $0 <= x <= k$, we can make one observation. The value of $f1(Fixed, k)$ will be same as $f1(fixed, k1)$, if $k$ is odd. Otherwise, the only additional contribution is of last term i.e. ${{Fixed}\choose{k/2}} {25}^{k/2}$. To get more idea about the implementation, refer to editorialist solution. In case of any doubt's, feel free to comment below. Time Complexity$O(N)$, per test case. Assuming all precomputations are also done in $O(\text{MAX VALUE})$. Space Complexity$O(N)$ Solution Linksasked 19 Nov '17, 22:04

Wait!! did you uploaded the editorials during the contest? The contest just ended and this editorial was uploaded 2 hours ago answered 20 Nov '17, 00:07

Sorry, but I'm not understanding why this formula doesn't count repetitions. Look this example: F(S, 4) = Sum (from i = 0 to 4) (f1(Fixed, 4i) * f2(NonFixed, i)); If i = 2 We have f1(Fixed, 2) * f2(NonFixed, 2) Fixed:(Ways using 0 Change + 1 Change + 2 Changes) * NonFixed:(Ways using 0 Change + 1 Change + 2 Changes). And if i = 1 We have f1(Fixed, 1) * f2(NonFixed, 3) Fixed:(Ways using 0 Change + 1 Changes) * NonFixed:(Ways using 0 Change + 1 Change + 2 Changes + 3 Changes). So, Fixed(1 Change) * NonFixed(1 Change) is counted twice. What am I missing? Thank you. answered 20 Nov '17, 02:19
@samuelfgs96, thanks for pointing the mistake. The editorial is updated and link to my solution is also provided.
(20 Nov '17, 03:11)

to calculate f(fixed, k), why are we summing from 0 to floor(k/2) but to calculate f(nonfixed, k) we are not summing up. Can you elaborate the method used to bring the complexity to O(n). I understood the O(n^2) approach but couldnt understand the O(n) solution. Also can you share any resource which explains find out the inverses quickly. answered 20 Nov '17, 13:48
@adhyyan1252, see the exact definition for f1 and f2 again. For one we need "atmost" and for other we need "exactly". This is to prevent doublecounting as accounted by @samuelfgs96 above in his comment. To understand the $O(n)$, I ask you to refer to the implementation and ask again if it is not clear.
(20 Nov '17, 22:31)
To calculate the inverses of factorial better than naive $O(n \log{n})$ approach, we make one observation that $invf[i] = invf[i+1] * (i+1)$, in MOD field where $invp[i]$ denotes inverse of factorial(i). Thus, we just calculate the inverse factorial of largest factorial and then calculate the inverse of other factorials in reverse order (kind of dp). Again refer to my implementation for details. Complexity of this approach will be exactly $O(\log{MOD} + \text{ MAX VALUE })$, which is basically $O(\text{MAX VALUE})$.
(20 Nov '17, 22:34)

The second argument of $f2$ function in the editorial seems like a boolean expression and is really confusing. To clarify that, suppose we are computing $f2(nonFixed, k)$ where $k$ is the no. of characters that need to be changed and let $x = 2*nonFixed  k$ ( = no. of characters that must be kept constant). So, now the $RHS$ of the expression computes $f2(nonFixed, k)$ and the condition that must be satisfied is $0\le x \le nonFixed$. answered 04 Jan, 14:19

@admin Solution links redirect to the same page.
@admin there's hyperlink recursion :P