PROBLEM LINK:
Practice
Contest
Author: Full name
Tester: Istvan Nagy
Editorialist: Oleksandr Kulkov
DIFFICULTY:
SIMPLE
PREREQUISITES:
None
PROBLEM:
Construct a palindromic string $s$ of letters $a$ and $b$ that has period $P$ (that is, $s$ can be obtained by concatenating several copies of some string $p$ of length $P$), each letter must be used at least once, or determine that it is impossible.
QUICK EXPLANATION:
For palindromicity of $s$, it is necessary and sufficient for $p$ (period) to be palindromic. A palindromic string of characters $a$ and $b$, each present at least once, exists for $P\ge 3$.
EXPLANATION:
Let's prove that for palindromicity of $s$, it is necessary and sufficient for $p$ (period) to be palindromic. For simplicity, let's consider three cases (mind that $N=|S|, P=|p|$).
- $\dfrac N P$ is even. In this case, the length of $s$ is even. The middle of the string $s$ is thus not a character, but rather lies between the end of some occurrence of $p$ in $s$ and the beginning of the next occurrence of $p$ in $s$. Considering these two occurrences, from palindromicity of $s$ we conclude that $s=s^R$. As the $\dfrac N P$ occurrences of $p$ in $s$ can be grouped into middle-symmetric pairs when $p$ is palindromic $s$ is also palindromic.
- $\dfrac N P$ is odd, $P$ is odd. The middle of the string $s$ is the middle of "central" occurrence of $p$ in $s$, so from palindromicity of $s$ it follows that $p$ is palindromic. Again, the remaining $\dfrac{N}{P} - 1$ occurrences can be split into middle-symmetric pairs, and from palindromicity of $p$ palindromicity of $s$ will follow.
- $\dfrac N P$ is odd, $P$ is even. The middle of the string $s$ thus splits the "central" occurrence of $p$ in $s$ into two equal-length parts, so from palindromicity of $s$ it follows that $p$ is palindromic. Again, the remaining $\dfrac{N}{P} - 1$ occurrences can be split into middle-symmetric pairs, and from palindromicity of $p$ palindromicity of $s$ will follow.
With that observation the rest of the solution is straightforward. For $P=1$ and $P=2$, clearly, $p$ can't contain both $a$ and $b$ and be palindromic, thus the answer is impossible
. For $P>2$ we can take $p=a\underbrace{bb\ldots bb}_{P-2\text{ times}}a$. To obtain $s$, concatenate $\dfrac{N}{P}$ copies of $p$.
Time and memory complexity of the solution is $O(N)$ as we need to construct the answer.
AUTHOR'S AND TESTER'S SOLUTIONS:
Author's solution can be found here.
Tester's solution can be found here.
Editorialist's solution can be found here.
RELATED PROBLEMS:
asked
13 Nov '17, 04:46
2★melfice
71●7●22
accept rate:
0%