Representation as graph problem

First, we consider how to solve it without caring the complexity.

Consider an \(N\)-vertex graph. If \(S_i=S_j\) is required, add a blue edge between vertices \(i\) and \(j\); if \(S_i\neq S_j\) is required, add a red edge between vertices \(i\) and \(j\).

First, for each \(i\), since \((S_{i-A_i},S_{i-A_i+1},\dots,S_{i+A_i})\) needs to be a palindrome, add blue edges \((i-A_i, i+A_i), (i-A_i+1,i+A_i-1), \dots, (i-1,i+1)\).

Then, for each \(i\), if \(2\leq i-A_i,i+A_i\leq N-1\), then \((S_{i-A_i-1},S_{i-A_i+1},\dots,S_{i+A_i+1})\) must not be a palindrome, so \(S_{i-A_i-1}\neq S_{i+A_i+1}\) is required; add a red edge \((i-A_i-1,i+A_i+1)\).

Vertices contained in a connected component formed by blue edges have to take the same value. So, contract such a connected component. Then assign a value to each connected component so that vertices connected by any red edge take different values.

After contracting, if there is a self-loop formed by a red edge, then it is impossible to assign values to the connected components, meaning that no \(S\) satisfies the conditions.

If such a self-loop does not exist, inspect connected components in ascending order of vertex indices, then greedily assign the smallest integer that is not used used by other connected components adjacent by a red edge.

The issue of the solution we have described is that there are at most \(O(N^2)\) edges. So we need to reduce the number of blue edges to be added without breaking the connectivity with respect to blue edges.

Optimization using Manacher’s algorithm

By using Manacher’s algorithm, the number of blue edges can be reduced to \(O(N)\). Manacher’s algorithm can find the length of the maximal palindrome centered at each character of a given string in a total of \(O(N)\) time.

The idea of Manacher’s algorithm is to use the result so far to skip inspecting parts that are already known to be palindromes. Refer to the following articles for more detailed explanation of the algorithm.

• Japanese: 文字列の頭良い感じの線形アルゴリズムたち２
• English: Manacher’s Algorithm - Finding all sub-palindromes in \(O(N)\)

Based on the idea of Manacher’s algorithm, the following pseudocode correctly adds blue edges, if there exists \(S\) that satisfies the conditions.

i = j = 0
while i < N:
    while j < A[i] + 1:
        unite(i - j, i + j)
        j += 1

    k = 1
    while i - k >= 0 and k + A[i - k] + 1 < j:
        k += 1
    i += k
    j -= k

Here, note that we use \(0\)-based indexing for the indices of \(A\) and the vertices. The function unite(u, v) adds a blue edge between vertices \(u\) and \(v\).

We analyze the time complexity of this algorithm. At a glance, it seems \(O(N^2)\) as it involves a double loop, but we claim that it is actually \(O(N)\).

First, we estimate how many times the while loop while j < A[i] + 1 at line 3 is executed. Considering the value \(i+j\),

• By lines 10 and 11, \(i+j\) remains invariant.
• \(i+j\) changes only at line 5, which increases by one every time
• By the condition of the while loop at line 3, \(i+j \leq i+A[i] \leq i+(N-i-1) < N\).

Therefore, the while loop at line 3 iterates at most \(N\) times.

Next, we analyze how many times the while loop while i - k >= 0 and k + A[i - k] + 1 < j at line 8 is executed. Considering the value \(i\),

• \(k\) is the number of repetitions of the while loop at line 8.
• \(i\) is the sum of \(k\), which corresponds to the total number of repetitions of the while loop at line 8.
• By the condition of the while loop at line 2, \(i < N\).

Therefore, the while loop at line 8 iterates at most \(N\) times.

Hence, this algorithm has been proven to run in a total of \(O(N)\) time.

This algorithm works only when a conforming \(S\) exists. Thus, we need to check if the resulting \(S\) actually satisfies the condition, which can be checked in \(O(N)\) time using Manacher’s algorithm again.