Minimum Palindrome Partition
National Olympiad — Regional round (2011 season)
Submission name: palind.cpp
Problem summary
Split a binary sequence into the fewest contiguous palindromes. Print an optimal set of cut positions, numbered from 1. If the whole sequence is a palindrome, print only 1.
Input
N, followed by N binary characters separated by whitespace.
Output
The minimum number P of pieces; if P>1, a second line containing the P−1 increasing cut positions. Any optimal partition is allowed.
Constraints
3 ≤ N ≤ 10000.
Worked example
An independently prepared example for this explanation.
Input
16 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0
Output
2 2
Solution analysis
- Let best[k] be the minimum palindrome count for the first k characters, with best[0]=0. If the substring from left through right is a palindrome, it can be the last piece, giving candidate best[left]+1 for best[right+1].
- Process right endpoints in increasing order. A substring is a palindrome when its endpoint characters agree and its interior is a palindrome. Keep a single array palindrome[left] for the previous right endpoint; update left in increasing order so palindrome[left+1] still describes the old interior.
- When a candidate improves best[right+1], remember left as its previous prefix length. Backtracking these saved prefix lengths recovers the cuts; reverse them to print increasing positions.
- In the sample, the first two characters form 11 and the remaining fourteen characters form 00011000011000. Both pieces are palindromes, but the complete sequence is not, so two pieces and the cut after position 2 are optimal.
Why it works
The palindrome recurrence is exact: matching endpoints reduce the question to the interior, with lengths one and two as base cases. Every partition of a nonempty prefix has one final palindromic piece, and the recurrence considers every possible start of that piece. All shorter-prefix optima are already final, so induction proves best values optimal. Stored predecessor lengths reconstruct a partition attaining the optimum.
Watch out. Update left from small to large; the opposite order overwrites the interior flags too early. Read characters with operator>> so both spaced digits and an uninterrupted binary string work. Output a blank-free single line when P=1, and distinguish zero-based substring indices from one-based cut positions.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<char>sequence(n),palindrome(n+1,false);
for(char&digit:sequence){
cin>>digit;
}
vector<int>best(n+1,n+1),previous(n+1,-1);
best[0]=0;
for(int right=0;right<n;++right){
for(int left=0;left<=right;++left){
// Increasing left preserves the previous right endpoint's interior.
palindrome[left]=sequence[left]==sequence[right]&&(right-left<2||palindrome[left+1]);
if(palindrome[left]&&best[left]+1<best[right+1]){
best[right+1]=best[left]+1;
previous[right+1]=left;
}
}
}
cout<<best[n]<<'\n';
if(best[n]>1){
vector<int>cuts;
for(int length=n;previous[length]>0;length=previous[length]){
cuts.push_back(previous[length]);
}
reverse(cuts.begin(),cuts.end());
for(size_t i=0;i<cuts.size();++i){
if(i>0){
cout<<' ';
}
cout<<cuts[i];
}
cout<<'\n';
}
}