Palindromic Deletions
National Olympiad — Regional round (2018 season)
Submission name: palc.cpp
Problem summary
Count choices of positions to retain that form a nonempty palindrome. Different position sets count separately even if their resulting strings are equal. Deleting no letters is allowed. Return the answer modulo 1,000,000,007.
Input
One string of lowercase Latin letters.
Output
The number of valid deletion choices modulo 1,000,000,007.
Constraints
2 ≤ N ≤ 100.
Worked example
Official sample, transcribed with whitespace restored from the PDF.
Input
aba
Output
5
Solution analysis
- Let dp[l][r] count nonempty palindromic subsequences by their retained positions inside the interval [l,r]. A single position contributes one; an empty interval contributes zero. Fill intervals by increasing length.
- First add the solutions omitting the left endpoint and those omitting the right endpoint. Their intersection is the solutions omitting both, so subtract dp[l+1][r−1]. If the endpoint letters match, also add every palindrome using both: the endpoints alone, or the endpoints wrapped around any interior palindrome. Thus matching endpoints give dp[l+1][r]+dp[l][r−1]+1; unequal endpoints give the usual inclusion-exclusion expression.
- For aba, the three single retained positions give three choices. Retaining positions 1 and 3 gives aa, and retaining all three gives aba. These five choices explain why the empty string is excluded.
Why it works
Induct on interval length. The endpoint-omission union contains exactly the palindromes not using both endpoints, with its double counting removed. Both endpoints can be used precisely when their letters agree, and removing them is a bijection to interior palindromes together with the empty interior. The recurrence therefore counts every eligible position set exactly once.
Watch out. Equal strings from different position sets remain distinct. Normalize negative modular values. The examples exclude deleting every character.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
string s;
cin>>s;
int n=int(s.size());
const long long mod=1000000007;
vector<vector<long long>>dp(n,vector<long long>(n));
for(int i=0;i<n;++i){
dp[i][i]=1;
}
for(int length=2;length<=n;++length){
for(int l=0;l+length<=n;++l){
int r=l+length-1;
long long inner=length==2?0:dp[l+1][r-1];
long long value=dp[l+1][r]+dp[l][r-1];
// Equal endpoints can wrap an empty or palindromic interior.
value+=s[l]==s[r]?1:-inner;
dp[l][r]=(value%mod+mod)%mod;
}
}
cout<<dp[0][n-1]<<'\n';
}