×

PERPALIN - Editorial

Author: Full name
Tester: Istvan Nagy
Editorialist: Oleksandr Kulkov

SIMPLE

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

1. $\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.
2. $\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.
3. $\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:

This question is marked "community wiki".

4★melfice
811534
accept rate: 0%

19.5k348496535

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,029
×1,084
×301
×2

question asked: 13 Nov '17, 04:46

question was seen: 711 times

last updated: 14 Nov '17, 19:31