Editorial for COCI '21 Contest 6 #4 Palindromi

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

For the first subtask, we can iterate over all substrings of the new string after each concatenation and check (e.g. using hashing) how many different palindromes there are. In this way, for a word of length $l$ $l$ , we can find the number of subpalindromes in $\mathcal O(l^2)$ $O (l^{2})$ so the total time complexity is $\mathcal O(n^3)$ $O (n^{3})$ . We can notice that when connecting two strings, it is enough to iterate over only the substrings which begin in the first word and end in the second one. In this way, connecting two words of length $a$ $a$ and $b$ $b$ is done in $\mathcal O(ab)$ $O (a b)$ , which turns out to be $\mathcal O(n^2)$ $O (n^{2})$ in total, solving the second subtask.

The following fact is useful for the remaining subtasks: if we append a character $c$ $c$ to any string $s$ $s$ to the left or to the right, the number of different palindromes of $s$ $s$ will increase by at most $1$ $1$ . Consequently, the total number of distinct palindromes in a string of length $n$ $n$ can be at most $n$ $n$ . Furthermore, there exists a data structure which maintains all the different subpalindromes of a string $s$ $s$ and the relations they have to each other. This data structure is called a palindromic tree or eertree. As mentioned, there are $n$ $n$ subpalindromes and it's possible to maintain this data structure using $\mathcal O(n)$ $O (n)$ space and amortized $\mathcal O(n)$ $O (n)$ time.

In short, each subpalindrome of $s$ $s$ is represented by a node. If $p$ $p$ is a subpalindrome of $s$ $s$ and $c$ $c$ is a character such that $cpc$ $c p c$ is also a subpalindrome of $s$ $s$ , then there is an edge between $p$ $p$ and $cpc$ $c p c$ labeled with $c$ $c$ . Additionally, for each subpalindrome $p$ $p$ , we'll have a suffix link towards the longest proper suffix of $p$ $p$ which is also a palindrome. The eertree supports the operation $add(c)$ $a d d (c)$ which appends the character $c$ $c$ to the end of the current string $s$ $s$ . This function can be implemented in amortized $\mathcal O(1)$ $O (1)$ in the following way: at all times, we maintain the longest suffix $t$ $t$ of the current string $s$ $s$ which is also a palindrome. When adding the character $c$ $c$ , if there is another character $c$ $c$ in front of $t$ $t$ , we simply extend $t$ $t$ to $ctc$ $c t c$ . Otherwise, we iterate through the suffix link chain $t, suf[t], suf[suf[t]], \dots$ $t, s u f [t], s u f [s u f [t]], \dots$ until we find the first palindrome in front of which is $c$ $c$ . Implementing this idea (according to the link provided above) was sufficient for the third subtask.

For the final subtask, we need to make a couple of modifications:

Instead of the time complexity of $add(c)$ $a d d (c)$ being amortized $\mathcal O(1)$ $O (1)$ , we can make it so that it is (non-amortized) $\mathcal O(\sigma)$ $O (σ)$ , where $\sigma$ $σ$ is the alphabet size. In our case, the alphabet consists only of the characters 0 and 1, so we consider the time complexity to be $\mathcal O(1)$ $O (1)$ . Along with $suf[node]$ $s u f [n o d e]$ , it is enough to keep track of two additional values: $suf_0[node]$ $s u f_{0} [n o d e]$ and $suf_1[node]$ $s u f_{1} [n o d e]$ , which represent the longest proper suffix in front of which is the character 0 or 1 respectively. All the mentioned values can be computed in $\mathcal O(1)$ $O (1)$ when adding a new node.
Instead of having a function $add(c)$ $a d d (c)$ which adds the character $c$ $c$ to the right, we'll support adding character both to the left and to the right. To do this, we maintain both the longest prefix and the longest suffix palindrome of the current string. When adding a character to the right, this affects only the longest suffix palindrome, and when adding it to the left it affects only the longest prefix palindrome. The only exception is when the entire string becomes a palindrome, in which case the longest prefix and suffix palindromes are equal and are equal to the entire string. Since the time complexity is no longer amortized, appending to both sides is done in $\mathcal O(1)$ $O (1)$ .
We'll append the smaller string to the larger string. If the right string is smaller than the left string, we successively add characters from the right string to the right end of the left string. If the left string is smaller, we successively add characters from the left string to the left end of the right string. It can be shown that the number of times a character gets added to a string is $\mathcal O(n \log n)$ $O (n \log n)$ , and since we have a data structure which supports these additions in $\mathcal O(1)$ $O (1)$ , the total time complexity is also $\mathcal O(n \log n)$ $O (n \log n)$ .

Comments

There are no comments at the moment.