CHEFHPAL - Editorial

#1

Author: Hanlin Ren
Tester: Istvan Nagy
Editorialist: Oleksandr Kulkov

MEDIUM

Brute force

PROBLEM:

Using only A first latin letters, construct a string of length N whose longest palindromic substring is as short as possible; also output this length;

QUICK EXPLANATION:

Handle easy cases A=1 (unique answer) and A>2 (the prefix of the infinite string \underbrace{abc}_{ ext{period}}abcabcabc\ldots contains only single-letter palindromes). When A=2, for N\le 8 find the answer via brute force; for N>8, the minimum palindrome substring length is 4, and one of the possible answers is the prefix of the infinite string \underbrace{aabbab}_{ ext{period}}~aabbab~aabbab~aabbab~\ldots.

EXPLANATION:

For A=1, the only possible string is \underbrace{aaa\ldots a}_{N ext{ times}}, and the length of its longest palindromic substring is N.

For A>2, take the prefix of the string \underbrace{abc}_{ ext{period}}abcabcabc\ldots to construct the answer that contains only one-letter palindromes. This infinite string has no palindromic substrings of longer length: if the first and the last characters of its substring (longer than 2) are equal, then its second from the beginning and second from the ending characters differ.

The tricky case is A=2. We will prove that for N\ge 9 the minimum longest palindromic substring length is 4.

First, let’s prove that for strings of length N\ge 9 there always exists a palindromic substring of length at least 4. Let’s call consecutive equal characters a block. For example, string aabbaba consists of 5 blocks: aa,bb,a,b,a. If one of the blocks is 4 characters or longer, the substring is found. Otherwise, all blocks are of length \le 3. Whenever some block of length 2 or 3 is not the first nor the last block in the string, we have a palindromic substring of length 4 and 5 respectively. If this is not the case, all blocks, except maybe the leftmost and rightmost ones, are of length 1. As the length of the string is at least 9 and the lengths of the leftmost and rightmost blocks are at most 6 there are at least 3 one-letter blocks which are not leftmost and rightmost. Then there exists a palindromic substring ababa or babab of length 5, formed by these blocks and their neighbours, if needed.

It is easy to see that the prefixes of the infinite string \underbrace{aabbab}_{ ext{period}}~aabbab~aabbab~aabbab~\ldots contain no palindromic substrings of length greater than 4: to verify this, consider each character as a candidate for an odd-length palindromic substring center, and each pair of adjacent characters as a candidate for an even-length palindromic substring center. Both cases quickly lead to the contradiction.

For A=2, N\le 8, find the answers by brute force in O(2^N\cdot n^3): for each of the possible 2^N binary strings, check whether each of the O(N^2) substrings is palindromic in O(N).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

RELATED PROBLEMS:

#2

Hello please help me to understand this “The tricky case is A=2A=2. We will prove that for N≥9N≥9 the minimum longest palindromic substring length is 4.”
for N=11,a=2
aaabababbbb=5
aaabaabbbbb=5
aaababbabbb=5
please let me know for which instance it is 4

#3

You should make it like that for N=11 A=2
aababbaabab
Here the length of longest palindromic substring is 4
You can repeat the aababb sequence as many times you want always you will get length is 4

#4

Superb problem, I personally feel that this is the best problem in November Challenge ignoring the prerequisites of other problems and concentrating on just the thinking capacity of the problem. Problems like this increase the quality of the contests. Thumbs up to setter.

#5

“For A=2,N≤8A=2,N≤8, find the answers by brute force in O(2N⋅n3)O(2N⋅n3): for each of the possible 2N2N binary strings, check whether each of the O(N2)O(N2) substrings is palindromic in O(N)O(N).”
For a=2 and n<=8 my solution is O(n)

#6

The solution to this problem is not obvious at all. I got a partial output correct for N<=10. The mistake I did was that I generated a string with shortest longest palindromic substring as L for string lengths 2^(L-1) + 1 to 2^L.

#7

Is their any other way than hit and trial to come up with the sequence

#8

Is the difficulty correct? It by no means is medium problem

#9

Hello! It is 4 for example for “aabbabaabba”, as it is stated in the editorial (to obtain the answer for any N, repeat the string “aabbab” sufficient number of times). What we are trying to prove is that there can be no string for which the maximum palindromic substring has length <4, i.e. 1, 2 or 3.