PROBLEM LINK:
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.