RESPAL - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: hjroh0315
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Construct a string of length N that has at most five distinct palindromic substrings.

EXPLANATION:

Note that any string of length 1 is a palindrome.
So, if S contains more than five distinct characters, it will certainly contain more than five distinct palindromes.
Thus, we only need to think about strings that have no more than five distinct characters.
For simplicity, let’s use \{\texttt{a, b, c, d, e}\}.

Suppose we use all five characters. That’s already five palindromes - meaning our string cannot contain any other palindromes - that is, we need to create a string that has no palindromes of any length \gt 1.

This is equivalent to not having any palindromes of lengths 2 and 3 in the string; because if we have a palindrome of length k, we also have a palindrome of length (k-2) by removing the first and last characters.
Now, you can see that:

  • To not have a length 2 palindrome, we must have S_i \ne S_{i+1} for all 1 \le i \lt N.
  • To not have a length 3 palindrome, we must have S_i \neq S_{i+2} for all 1 \le i \lt N-1.

This leads to the following construction.

  • Let’s start with S_1 = \texttt{a}.
  • S_2 \neq S_1, so let’s say S_2 = \texttt{b}.
  • Now for each i \geq 3, we only need to ensure that S_i \neq S_{i-1} and S_i \neq S_{i-2}.
    We have five characters available to us, and only two are forbidden, so there’s always a valid choice.
    You can find it by just brute-forcing over all possible choices.

In fact, if you analyze a bit more, you might notice that we don’t even need five characters: this logic would work even if we had only three, with the resulting string being

\texttt{abcabcabc}\ldots

It’s easy to see that this works.
Of course, since any valid answer is accepted, you can do anything you like with \leq 5 distinct characters, while ensuring that S_i \neq S_{i-1} and S_i \neq S_{i-2} for all valid i. The above pattern just has the simplest implementation.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
s = 'abc'*100
for _ in range(int(input())):
    n = int(input())
    print(s[:n])
1 Like