CDSW155 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice

Contest

Author: Chintu Kumar

Editorialist: Chintu Kumar

DIFFICULTY:

MEDIUM-HARD

PROBLEM

This problem asks you to find the palindromic prefix of maximum charm (i.e. length ) for every suffix such that the length should not exceed a particular value(denoted by allowed[]).

So, in simple terms you can say that for every i in the range(0,n-1) inclusive, you have to find the largest palindrome (palindrome with max length) with i as the starting point such that it’s length doesn’t exceed allowed[i].

PREREQUISITES:

Manacher’s Algorithm

EXPLANATION:

For a given string, Manacher’s algorithm gives you the maximum length of the palindrome that can be
formed using  i as the center for every i in the range(0,n-1) inclusive (considering both even and odd length
palindromes).

So, for a given i can center we can easily find the smallest k such that string starting from k and i as center is
palindromes.
so, for odd length palindromes you need to find smallest k such that the substring (k-i,k+1) is a palindrome. let’s say this value is ‘OddK’

for even length palindromes , find the smallest k such that the substring (k-i,k+i-1) is a palindrome. let’s say this value is ‘EvenK’

Now, for computing the answer for any given i (suffix[i]) we can compute what can be the range for center of the palindrome ,so that the substring is not invalid (repulsive as stated in the question)

for odd length palindromes the center can be in the range (i + (allowed[i]-1)/2)
for even length palindromes the center can be in the range (i + allowed[i]/2)

so , the final answer for a given i can be computed by finding the largest j such that j is in the range described above and  K-value(j) <= i (K-value can be either OddK/EvenK depending on the odd/even type palindrome you are considering). Then choose the palindrome with the bigger length, that will give you the answer for that particular i.

This part can be done in O(logN) (or maybe better) using binary search or using some other approach.
So, doing this for all the i will give total complexity of O(NlogN).

Notes -
Considering 0-based indexes everywhere
for both even and odd length palindromes center is considered at (start + length/2) position

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution can be found here.