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

×

PERPALIN - Editorial

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

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

asked 13 Nov, 04:46

melfice's gravatar image

2★melfice
412
accept rate: 0%

edited 14 Nov, 19:31

admin's gravatar image

0★admin ♦♦
16.9k347485513

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:

×11,984
×795
×247
×2

question asked: 13 Nov, 04:46

question was seen: 178 times

last updated: 14 Nov, 19:31