You are not logged in. Please login at www.codechef.com to post your questions!

×

PALHAM - Editorial

Problem Link

Practice

Contest

Setter: Hasan Jaddouh

Tester: Amr Mahmoud

Editorialist: Bhuvnesh Jain

Difficulty

MEDIUM

Prerequisites

Combinatorics

Problem

Given 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/Tricks

Try 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)$.

Explanation

The 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, 0-based 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:

  1. Fixed: The set of those indices, $i (< {\\frac{n}{2}})$, such that $S[i] == S[n-1-i]$.
  2. nonFixed: The set of those indices, $i (< {\\frac{n}{2}})$, such that $S[i] \\neq S[n-1-i]$.

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:

  1. $f1(Fixed, k)$ = returns the number of ways to change "Fixed" indices so that palindrome condition is satisfied at those indices, with the condition that maximum of $k$ changes can be made.
  2. $f2(nonFixed, k)$ = returns the number of ways to change "nonFixed" indices so that palindrome condition is satisfied at those indices, with the condition that exactly $k$ changes can be made.

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, k-1)$.

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}^{nonFixed-x}}$, provided that $(x >= 0 \text{ and } x <= nonFixed)$

The reasoning is as follows:

  1. In "fixed" case, the condition of the palindrome is already satisfied. So, if we change a character at fixed index, (say $i$), we need to change it at another location, (namely $(n-i-1)$). Thus, we every time need to make at least 2 changes in $S$. Thus, we select the number of indices we want to make changes in and then make changes in them. The number of ways to chose the indices is ${{Fixed}\\choose{x}}$ and the number of ways is ${25}^{x}$ as there are $25$ different possible characters to be replaced at each location.
  2. In "non_fixed" case, the condition of the palindrome is not satisfied. So, we can either change both the indices, $i$ and $(n-i-1)$, or change only one of them. But change has to be applied to ensure final string has the palindrome condition satisfied. If we change both of them, then both of them must be same and there are remaining $24$ characters to chose from. If we change only one of them, then we have only 2 choices, either change $S[i]$ and make it equal to $S[n-i-1]$ and vice-versa.

Implementing the above full idea naively will take $O(N^2)$ time as there will be double summations. The trick is to pre-compute 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, k-1)$, 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 Links

Setter's solution

Tester's solution

Editorialist's solution

asked 19 Nov '17, 22:04

likecs's gravatar image

6★likecs
3.7k2380
accept rate: 9%

edited 21 Nov '17, 09:04

admin's gravatar image

0★admin ♦♦
19.7k350498541

1

@admin Solution links redirect to the same page.

(20 Nov '17, 01:00) shawnfrost5★
2

@admin there's hyperlink recursion :P

(20 Nov '17, 01:29) swetankmodi ♦♦6★

Wait!! did you uploaded the editorials during the contest? The contest just ended and this editorial was uploaded 2 hours ago

link

answered 20 Nov '17, 00:07

kunnu120's gravatar image

2★kunnu120
5189
accept rate: 5%

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, 4-i) * 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.

link

answered 20 Nov '17, 02:19

samuelfgs96's gravatar image

6★samuelfgs96
11
accept rate: 0%

edited 20 Nov '17, 03:38

@samuelfgs96, thanks for pointing the mistake. The editorial is updated and link to my solution is also provided.

(20 Nov '17, 03:11) likecs6★

to calculate f(fixed, k), why are we summing from 0 to floor(k/2) but to calculate f(non-fixed, 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.

link

answered 20 Nov '17, 13:48

adhyyan1252's gravatar image

6★adhyyan1252
1425
accept rate: 11%

edited 20 Nov '17, 18:54

@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 double-counting 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) likecs6★

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) likecs6★

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$.

link

answered 04 Jan, 14:19

roll_no_1's gravatar image

6★roll_no_1
413
accept rate: 18%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,499
×2,559
×869
×593
×101
×98
×11

question asked: 19 Nov '17, 22:04

question was seen: 2,183 times

last updated: 04 Jan, 14:19