Partition Bracket Subsequences
National Olympiad — National round (2018 season)
Submission name: braces.cpp
Problem summary
Partition a bracket string into exactly K nonempty consecutive parts. Minimize the sum of longest correct bracket-subsequence lengths. Output both optimal partitions: lexicographically longest and shortest part lengths when compared from the last part backward, together with subsequence witnesses.
Source clarification. The printed constraints say K≥3, but the second official example uses K=2; the algorithm supports every 1≤K≤min(N,200).
Input
A bracket string, then K.
Output
The minimum sum, K formatted part-and-witness lines for the longest-last tie rule, then K lines for the shortest-last rule.
Constraints
N ≤ 1000; 1 ≤ K ≤ min(N,200), including the K=2 official example despite the printed K≥3 bound.
Worked example
An independently prepared example for this explanation.
Input
()() 3
Output
0 1, [1,1], 0: 2, [2,3], 0: 3, [4,4], 0: 1, [1,1], 0: 2, [2,3], 0: 3, [4,4], 0:
Solution analysis
- Precompute cost[l][r], the longest correct bracket-subsequence length in every interval. Scan rightward from each l, keeping unmatched opening brackets; whenever a closing bracket can match one, add two to the cost. This greedy matching maximizes the number of pairs.
- Use dp[t][r]=min(dp[t−1][s]+cost[s+1][r]) over t−1≤s<r. It describes the best split of the first r brackets into t nonempty parts. For every state record both the smallest and the largest optimal s. The smaller s gives the longest last part; the larger s gives the shortest.
- Reconstruct backward from (K,N), consistently using the chosen tie rule. Within each interval greedily match openings with closing brackets and sort the selected positions. For ()() split into three parts, the unique zero-cost partition is ( | )( | ), namely [1,1],[2,3],[4,4].
Why it works
Greedy bracket matching pairs every closing bracket that can be matched; leaving such an opening unused cannot increase any later matching opportunity, proving each interval cost. Every t-part partition has a last cut s, and the preceding t−1 parts must be optimal for their prefix, establishing the recurrence. Last-part length is compared before every earlier length, so choosing the smallest or largest optimal s gives the correct first tie decision; induction on the chosen prefix gives all remaining decisions. Greedy witnesses attain the precomputed interval costs.
Watch out. Parts must be nonempty. A subsequence need not be contiguous. Apply tie-breaking from the end, not the beginning; different valid longest-subsequence witnesses are allowed.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<string>
#include<utility>
#include<vector>
// Algorithm: Precompute cost[l][r], the longest correct bracket-subsequence length in every
// interval.
using namespace std;
int main(){
string text;
int k;
cin>>text>>k;
int n=static_cast<int>(text.size());
vector<vector<int>>cost(n+1,vector<int>(n+1));
for(int left=1;left<=n;left++){
int opening=0;
int matched=0;
for(int right=left;right<=n;right++){
if(text[right-1]=='('){
opening++;
}
else if(opening){
opening--;
matched+=2;
}
cost[left][right]=matched;
}
}
const int infinity=1000000000;
vector<int>previous(n+1,infinity),current(n+1);
vector<vector<int>>longest(k+1,vector<int>(n+1));
vector<vector<int>>shortest=longest;
previous[0]=0;
for(int parts=1;parts<=k;parts++){
fill(current.begin(),current.end(),infinity);
for(int right=parts;right<=n;right++){
for(int cut=parts-1;cut<right;cut++){
int candidate=previous[cut]+cost[cut+1][right];
if(candidate<current[right]){
current[right]=candidate;
longest[parts][right]=cut;
shortest[parts][right]=cut;
}
else if(candidate==current[right]){
shortest[parts][right]=cut;
}
}
}
previous.swap(current);
}
cout<<previous[n]<<'\n';
for(int mode=0;mode<2;mode++){
const auto&choice=mode==0?longest:shortest;
vector<pair<int,int>>intervals;
int right=n;
for(int parts=k;parts>0;parts--){
int cut=choice[parts][right];
intervals.emplace_back(cut+1,right);
right=cut;
}
reverse(intervals.begin(),intervals.end());
for(int part=0;part<k;part++){
int left=intervals[part].first;
int end=intervals[part].second;
vector<int>opening,selected;
for(int position=left;position<=end;position++){
if(text[position-1]=='('){
opening.push_back(position);
}
else if(!opening.empty()){
selected.push_back(opening.back());
opening.pop_back();
selected.push_back(position);
}
}
sort(selected.begin(),selected.end());
cout<<part+1<<", ["<<left<<','<<end<<"], "<<selected.size()<<':';
for(int position:selected){
cout<<' '<<position;
}
cout<<'\n';
}
}
}