SQMA02 - Editorial

PROBLEM LINK:

Practice

DIFFICULTY:

MEDIUM

PREREQUISITES:

Manacher’s Algorithm O(n)

PROBLEM:

Given a string in “compact notation”(see the problem), find the number of substrings that are palindrome.

EXPLANATION:

The problem was a straightforward application of Manacher’s Algorithm. This Algo was originally proposed to find the longest palindrome in a string. However, for each “center” c, it finds the length of the longest palindrome “centered” at c. Therefore, we can use it to find the number of palindromes “centered” at c as well. Handling the fact that strings are given in compact notation is relatively straightforward.

Many elegant descriptions of Manacher’s Algorithm can be found on internet

In very short, Manacher’s Algorithm can be written as follows.

1 | int p[N+1], mx = 0, id = 0;
2 | // length of longest palindrome centred at i is 2 * p[i]-1.
3 | for (i = 1; i <= N; i++) {
4 |     p[i] = mx > i ? min(p[2 * id-i], mx-i) : 1;
5 |     while (s[i + p[i]] == s[i - p[i]]) p[i]++;
6 |     if (i + p[i] > mx) {
7 |         mx = i + p[i];
8 |         id = i;
9 |     }
10| }

Let the compacted string be (c1, k1), (c2, k2), … (cN, kN).

  • Palindromes that contain only a single character repeated several times can be counted as:

Assuming reader understands Manacher’s Algorithm, here is how to modify it for this problem:
Σ ki * (ki +1) / 2

  • Palindromes that span over more than 1 contiguous segment of compressed string can be computed by also maintaining an array q, which stores the length of the longest “decompressed” palindrome centered at the ith segment.:

q[i] = ki-p[i]+1 + ki-p[i]+2 … + ki + … ki+p[i]-2 + ki+p[i]-1
There will also be minor changes like:

  1. We need not put interleaving '#'es because center of every palindromic substring is the center of some “compressed” segment(unless it fully lies inside a segment).
  2. In line no 5, compare the characters as well as the lengths of the segments.
  3. 1. If the segments i-p[i] and i+p[i] do not have same lengths, but have the same character, then q[i] would need to adjusted by adding 2*min(ki-p[i], ki+p[i]).

The final Answer is
Σ ki * (ki +1) / 2 + ⌈q[i]/2⌉ - ⌈ki/2]
if you are having difficulty in understanding it please go through this_link although the problem is not the same, the algorithm explained there.

SOLUTIONS:

Solution
#include <iostream>
using namespace std;

char s[122222];
int n, m;
pair<char, int> a[122222];
int range[122222];
int sum[122222];

long long call_handle()
{
//manachar algorithm
int center = 1;
range[1] = 1;

a[0] = make_pair('#', 0);
a[m + 1] = make_pair('@', 0);

for (int i = 1; i <= m; i++)
{
    range[i] = 1;
    if (center + range[center] - 1 >= i)
    {
        range[i] = range[center * 2 - i];
        if (i + range[i] < center + range[center])
            continue;
        else
            range[i] = center + range[center] - i;
    }

    while (a[i - range[i]] == a[i + range[i]])
        range[i]++;
    center = i;
}
//end of manachar algorithm

long long res = 0;
sum[0] = 0;
for (int i = 1; i <= m; i++)
    sum[i] = a[i].second + sum[i - 1];

for (int i = 1; i <= m; i++)
{
    //counting the palindrom that contain only one kind of character
    res += (long long)(a[i].second + 1) * (a[i].second) / 2;

    //if range[i] > 1, we add to the result the number of palindroms with center at i.
    //we have to subtract (a[i].second + 1)/2 palindroms which are already couted in             the previous step.
    if (range[i] > 1)
    {
        res -= (a[i].second + 1) / 2;
        int u = i - range[i] + 1, v = i + range[i] - 1;
        res += (sum[v] - sum[u - 1] + 1) / 2;
        if (a[u - 1].first == a[v + 1].first)
            res += min(a[u - 1].second, a[v + 1].second);
    }
    else if (a[i - 1].first == a[i + 1].first)
        res += min(a[i - 1].second, a[i + 1].second);
}

return res;
}

int main()
{
int t;
scanf("%d\n", &t);

int sum = 0;
while (t--)
{
    cin >> m;

    for (int i = 1; i <= m; i++)
        cin >> a[i].first >> a[i].second;

    cout << call_handle() << endl;
   }

return 0;
}