Editorial- Lost Algorithm || ECPC10G

pankajsharma1 · November 4, 2020, 1:44pm

PROBLEM LINK:

Contest
Practice

Author and Editorialist: Pankaj Sharma

DIFFICULTY:

HARD .

PREREQUISITES:

Segment tree , manacher’s algorithm , palindromic tree

PROBLEM:

Minimize No of unique palindromic substrings in S by replacing exactly one character of S by 0. Also print the largest index which will give this minimum value.

QUICK EXPLANATION:

Check

if S_i = 0 Then Ans for index i = Total palindromic substrings before operation + No of palindromic substrings created - No of palindromic substrings removed
All Newly created palindromic substrings can be calculated using Manachers Algo.
All removed palindromic substrings can be calculated using Palindromic Tree with range updates.

EXPLANATION:

Observation 1

If 0 occurs at index i then some palindromic substrings are created and some are removed.

Observation 2

Only odd length palindromes can be created because for even length you need two 0’s.

Observation 3

Max no of unique palindromes substrings can be N.

How to approach

All odd length palindromic substrings for each i can be calculated using Manacher’s Algorithm.
You can learn Manachers Algorithm from here.
To remove a palindrome X from S we must include 0 in a position such that 0 overlaps with atleast one character of X from all positions in which X occurs
So for each string X we need to know first and last occurence of it. This can be done using Palindromic Tree.
You can learn Palindromic tree from below resources
Adilet Blog
Codeforces Blog
GeeksforGeeks
We will construct to Palindromic trees one for S and one for Reverse of S .
These will give us first and last occurence of all unique palindromes.
Then we will Use range update of 1 on overlapping of these 2 occurences as it will remove our palindrome. This can be done via segment tree.
So for each i we can get No of palindromes removed.
So we can calculated our answer i.e. No of unique palindromic substrings if S[i] = 0 for each index as Total palindromes before + New Palindromes created - old palindromes destroyed.
Then We will take largest index which will give us min answer.

Time Complexity:

The time complexity is O(N*logN) per test case.
where N=total number characters in string S.

SOLUTIONS:

Editorialist's Solution

#include <bits/stdc++.h>
using namespace std;

typedef long long           ll;
struct node {
  node() : len(0), suffix(1), num(0), first(-1), cant(0) {
    memset(next, 0, sizeof(next));
  }
  // Edges, length of P, node index of longest palindromic suffix,
  // number of palindrome suffixes.
  int next[26], len, suffix, num, first;
  ll cant;
};

struct palindromic_tree {

  string s;
  // Length of s, num of nodes, longest palindromic suffix.
  int len, num, suff;
  vector<node> tree;
  palindromic_tree() : num(2), suff(2) {}

  void initTree() {
    len = s.size();
    tree = vector<node>(len + 3);
    tree[1].len = -1; tree[1].suffix = 1;
    tree[2].len = 0; tree[2].suffix = 1;
    for (int i = 0; i < len; i++) add_letter(i);
    for (int i = len + 2; i >= 0; --i)
      tree[tree[i].suffix].cant += tree[i].cant;
  }

  bool add_letter(int pos) {
    int cur = suff, curlen = 0, let = s[pos] - 'a';
    while (true) {
      curlen = tree[cur].len;
      if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) break;
      cur = tree[cur].suffix;
    }
    if (tree[cur].next[let]) {
      suff = tree[cur].next[let];
      ++tree[suff].cant;
      return false;
    }
    num++;
    suff = num;
    tree[num].len = tree[cur].len + 2;
    tree[num].cant = 1;
    tree[cur].next[let] = num;
    tree[num].first = pos;
    if (tree[num].len == 1) {
      tree[num].suffix = 2;
      tree[num].num = 1;
      return true;
    }
    while (true) {
      cur = tree[cur].suffix;
      curlen = tree[cur].len;
      if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
        tree[num].suffix = tree[cur].next[let];
        break;
      }
    }
    tree[num].num = 1 + tree[tree[num].suffix].num;
    return true;
  }
};
// Segment Tree
struct segtree {
  int size;
  vector<int> v;

  segtree(int n) {
    size = 1;
    while (size < n) size *= 2;
    v = vector<int>(2 * size);
  }

  void add(int a, int b, int i, int j, int p) {
    if (a <= i and j <= b) {
      ++v[p];
      return;
    }
    if (j <= a or b <= i) return;
    add(a, b, i, (i + j) / 2, 2 * p);
    add(a, b, (i + j) / 2, j, 2 * p + 1);
  }

  void add(int l, int r) {
    add(l, r, 0, size, 1);
  }

  int get(int p) {
    p += size;
    int r = v[p];
    while (p > 1) {
      p /= 2;
      r += v[p];
    }
    return r;
  }
};

string preProcess(string s) {
  int n = s.length();
  if (n == 0) return "^$";
  string ret = "^";
  for (int i = 0; i < n; i++) {
    ret += '#';
    ret += s[i];
  }
  ret += "#$";
  return ret;
}
// Manachers algo
vector<int> longestPalindrome(string s) {
  string T = preProcess(s);
  int n = T.length();
  vector<int> P(n);
  int C = 0, R = 0;
  for (int i = 1; i < n - 1; i++) {
    int i_mirror = 2 * C - i; // equals to i' = C - (i-C)
    P[i] = (R > i) ? min(R - i, P[i_mirror]) : 0;
    // Attempt to expand palindrome centered at i
    while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
      P[i]++;
    // If palindrome centered at i expand past R,
    // adjust center based on expanded palindrome.
    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
  }
  return P;
}

void compute(palindromic_tree &front_tree, palindromic_tree &rev_tree, vector<int> &leftSide, vector<int> &rightSide, segtree &middle, int i, int j, int n) {
  if (front_tree.tree[i].first != -1) {
    int l = front_tree.tree[i].first;
    int r = n - 1 - rev_tree.tree[j].first;
    if (l < n - 1) ++rightSide[l + 1];
    if (r) ++leftSide[r - 1];
    middle.add(l + 1, r);
  }
  for (char c = 'a'; c <= 'z'; ++c) {
    if (front_tree.tree[i].next[c - 'a']) {
      compute(front_tree, rev_tree, leftSide, rightSide, middle,
              front_tree.tree[i].next[c - 'a'],
              rev_tree.tree[j].next[c - 'a'], n);
    }
  }
}

void test_case() {
  string s;
  int n;
  cin >> n;
  cin >> s;

  palindromic_tree front_tree, rev_tree;
  front_tree.s = s;
  rev_tree.s = s;

  reverse(rev_tree.s.begin(), rev_tree.s.end());

  rev_tree.initTree();
  front_tree.initTree();
  vector<int> P = longestPalindrome(s);

  segtree middle(n);
  vector<int> leftSide(n), rightSide(n);

  compute(front_tree, rev_tree, leftSide, rightSide, middle, 1, 1, n);
  compute(front_tree, rev_tree, leftSide, rightSide, middle, 2, 2, n);

  for (int i = 1; i < n; ++i)
    rightSide[i] += rightSide[i - 1];
  for (int i = n - 2; i >= 0; --i) leftSide[i] += leftSide[i + 1];


  int largest = 0, mn = INT_MAX;
  for (int i = 0; i < n; ++i) {

    int newly_created =  (P[2 * i + 2] + 1) / 2;
    int res = leftSide[i] + rightSide[i] + newly_created - middle.get(i);

    if (res < mn) {
      mn = res;
      largest = i + 1;
    } else {
      if (res == mn) largest = i + 1;
    }
  }
  cout << mn << " " << largest << "\n";
}

int main() {
  int t;
  cin >> t;
  while (t--) test_case();
}