CCL6 - EDITORIAL

PROBLEM LINK

Practice

Contest

Author: Prahalad Singh

Tester:

Editorialist: Sanyam Aggarwal

DIFFICULTY

HARD

PREREQUISITES

Suffix Tree
Dynamic Programming
String Theory

PROBLEM

In the Seventh episode of the Third Season of Rick and Morty as Rick and Morty were preparing to go to Atlantis, they were interrupted by Rick and Morty’s pair from the Citadel of Ricks looking for donations to the Citadel Redevelopment fund. Our Rick and Morty refute the possibility of donation with hostility and the pair left (pointing out that our Rick was the one to say no).

Imagine a scenario where our Rick chose to give them one more opportunity to Rick from Citadel after all Rick from Citadel looked precisely like him. So our Rick asked them a problem based on pairs, which Rick and Morty from Citadel couldn’t tackle since they were busy collecting donations, you liked the idea of donations for a social cause and chose to help them to crack the problem.

They were given a string str, determine the total n number of ways to cut string str to substrings such that if there are n (n is always even) substrings S_i (1≤i≤n) such that str=S_1S_2S_3S_4……..S_(n−1)S_n, then S_i=S_n−i+1 S_i=S_n−i+1 for all i(1 ≤i≤ n). Since the answer can be huge, calculate its modulo 10^9+7.

EXPLANATION

Let n be the length of the string s. Consider the string nstr = str[0]str[n - 1]str[1]str[n - 2]str[2]str[n - 3]...str[n / 2 - 1]str[n / 2]. The problem can be reduced to finding the number of ways to partition string nstr into palindromic substrings of even length.

Proof: Let k be the total number of partitions. Let
S_i = S_{k-i+1} for S_1S_2S_3...S_n where m denotes length of p_i and x_j denotes j_{th} character of p_i. The part of string str corresponding to these two partitions is p_1p_mp_2p_{m - 1}...p_{m - 1}p_2p_mp_1 and this an even length palindrome. Similarly, the converse is also true.

Dynamic programming can be used to solve the problem. Let dp[i] be the number of ways to partition t[1…i] into even length palindromes. Then, dp[i]=sigma(dp[i-1]) where nstr[j + 1...i] is an even length palindrome. Of course for odd i, dp[i] = 0.

we can use an EER tree to implement the solution. Further, we can avoid the use of any suffix structure by following the algorithm described here https://arxiv.org/pdf/1403.2431.pdf .

To know more about suffix tree: https://www.hackerearth.com/practice/data-structures/advanced-data-structures/suffix-trees/tutorial/

SOLUTION

Setter’s Solution
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define endl        '\n'
using namespace std;
const int MAXN=1000005;
string s;
struct PalindromicTree {
    int N,cur;
    vector<map<int,int>> next;
    vector<int> link,start,len,diff,slink;
     PalindromicTree(): N(0),cur(0)
{ 
 node();
 len[0]=-1;
 node();
 }
int node(){
                      next.emplace_back();
                      link.emplace_back(0);
                      start.emplace_back(0);
                      len.emplace_back(0);
                      diff.emplace_back(0);
                      slink.emplace_back(0);
                      return N++;
                   }
void add_letter(int idx){
                                          while(true){
                                          if(idx-len[cur]-1>=0 && s[idx-len[cur]-1]==s[idx]);
  cur=link[cur];
                                     } 
if(next[cur].find(s[idx])!=next[cur].end()){                                                                                  cur=next[cur][s[idx]];                                                                           
return;                                                                       }                                                                                                                                                                                                                   
node();                                                                                                                                                                                                                                
next[cur][s[idx]]=N-1;                                                                                                                                                                                                                                        
len[N-1]=len[cur]+2;                                                                                                                                                                                                                                                
start[N-1]=idx-len[N-1]+1;                                                                                                                                                                                                                                                        
if(len[N-1]==1){                                                                                                                                                                                                                                                                    
link[N-1]=diff[N-1]=slink[N-1]=1;                                                                                                                                                                                                                                                                                
cur=N-1;                                                                                                                                                                                                                                                                                            
return;
}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           while(true){                                                                                                                                                                                                                                                                                                                        cur=link[cur];                                                                                                                                                                                                                                                                                                                                    if(idx-len[cur]-1>=0 && s[idx-len[cur]-1]==s[idx]);                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       }                                                                                                                                                                                                                                                                                                                                                                    

link[N-1]=next[cur][s[idx]];                                                                                                                                                                                                                                                                                                                                                                           
diff[N-1]=len[N-1]-len[link[N-1]];                                                                                                                                                                                                                                                                                                                                                                                    
if(diff[N-1]==diff[link[N-1]])                                                                                                                                                                                                                                                                                                                                                                                               
slink[N-1]=slink[link[N-1]];                                                                                                                                                                                                                                                                                                                                                                                                        
else                                                                                                                                                                                                                                                                                                                                                                                                                    
slink[N-1]=link[N-1];                                                                                                                                                                                                                                                                                                                                                                                                                            
cur=N-1;                                                                                                                                                                                                                                                                                                                                                                                                                                    }                                                                                                                                                                                                                                                                                                                                                             };                                                                                                                                                                                                                                                                                                                                                                                                                       
ll dp[MAXN],sans[MAXN];                                                                                                                                                                                                                                                                                                                                                                                                                                
int main() 
{                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      
    std::ios::sync_with_stdio(false);                                                                                                                                                                                                                                                                                                                                                                                                                                        
    cin.tie(0);                                                                                                                                                                                                                                                                                                                                                                                                                                            
    cout.tie(0);                                                                                                                                                                                                                                                                                                                                                                                                                                                
    PalindromicTree pt;                                                                                                                                                                                                                                                                                                                                                                                                                                                    
    int i,cur;                                                                                                                                                                                                                                                                                                                                                                                                                                                        
string str;                                                                                                                                                                                                                                                                                                                                                                                                                                                           
cin>>str;                                                                                                                                                                                                                                                                                                                                                                                                                                                                
for(i=0;i<sz(str)/2;i++){                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
s.pb(str[i]);                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
s.pb(str[sz(str)-i-1]);                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
dp[0]=1;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
for(i=1;i<=sz(s);i++){                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
pt.add_letter(i-1);                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
for(cur=pt.cur;cur>1;cur=pt.slink[cur])
{
sans[cur]=dp[i-pt.len[pt.slink[cur]]-pt.diff[cur]];
if(pt.diff[cur]==pt.diff[pt.link[cur]])
sans[cur]=(sans[cur]+sans[pt.link[cur]])%hell;
dp[i]=(dp[i]+sans[cur])%hell;
 }
 if(i&1)
 dp[i]=0;
}
cout<<dp[sz(s)];                                                                               
return 0;                                                                                
}                                                                                
1 Like