PERPALIN - Editorial

editorial
, , ,
1

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: