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

×

CHEFHPAL - Editorial

1
1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

MEDIUM

PREREQUISITES:

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}*{\text{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}*{\text{period}}~aabbab~aabbab~aabbab~\ldots$.

EXPLANATION:

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

For $A>2$, take the prefix of the string $\underbrace{abc}_{\text{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}_{\text{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:

This question is marked "community wiki".

asked 13 Nov, 06:35

melfice's gravatar image

2★melfice
412
accept rate: 0%

edited 14 Nov, 19:12

admin's gravatar image

0★admin ♦♦
16.9k347485513

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

(15 Nov, 10:34) vijju123 ♦5★

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

link

answered 15 Nov, 09:35

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 0%

edited 15 Nov, 09:36

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.

(15 Nov, 18:19) melfice2★

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

link

answered 15 Nov, 10:29

chhekur's gravatar image

3★chhekur
1
accept rate: 0%

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.

link

answered 15 Nov, 14:20

jagreetdg's gravatar image

4★jagreetdg
354
accept rate: 14%

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

link

answered 2 days ago

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 0%

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.

link

answered 2 days ago

devsaw's gravatar image

3★devsaw
1
accept rate: 0%

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,987
×1,879
×253
×94

question asked: 13 Nov, 06:35

question was seen: 575 times

last updated: 2 days ago