BREAKUP-EDITORIAL

PROBLEM LINK:

Practice
Contest

Author: yoga2001
Tester: hellb0y_suru
Editorialist: yoga2001

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

PROBLEM:

Given N strings(phone numbers),find the maximum number of operations required to delete the strings.The strings can be deleted individually or concatenated into groups in the order of indices and then deleted.An operation is defined as deleting a contiguous part of the string with same characters.

EXPLANATION:

  • Concatenate all the strings,that’s the most optimal way.
  • We will solve this whole big string using dynammic programming.

The DP Algorithm:

Let dp[l,r] be the answer for substring s[l,l+1,…,r].

Then we have two cases:

The first letter of the substring is deleted separately from the rest, then dp[l,r] =1+dp[l+1,r]

The first letter of the substring is deleted alongside with some other letter (both letters must be equal), then dp[l,r]=min l<i \leq r, Si=Sr(dp[l+1,i-1]+dp[i,r]) .

SOLUTIONS:

Setter's and Editorialist's Solution
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	ll t, n;
	string x;
	cin >> t;
	while(t--) {
		cin >> n;
		string s = "";
		for(int i=0;i<n;i++) {
			cin >> x;
			s+=x;
		}
		n = s.size();
		ll dp[n+1][n+1];
    	memset(dp, 0, sizeof(dp));
    	for(ll i=0;i<n;i++){
    	    dp[i][1]=1;
    	}
    	ll zero = 0;
    	for(ll i=2;i<=n;i++){
    	    for(ll j=i-1;j<n;j++){
    	        dp[j-i+1][i]=dp[j-i+1][i-1]+1;
    	        for(ll z=j;z>=j-i+1;z--){
    	            if(s[j]==s[z]){
    	                dp[j-i+1][i]=min(dp[j-i+1][i],dp[j-i+1][z-j+i]+dp[z+1][max(zero,j-1-z)]);
    	            }
    	        }
    	    }
    	}
    	cout<<dp[0][n]<<endl;
	}
	return 0;
}
Tester's Solution
#include<bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define forr(i,n) for(ll i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(0) ; cout.tie(0);

using namespace std;


string s;

int dp[550][550];

int get(int i, int j){
    if(i>j) return 0;
    else{
        return dp[i][j];
    }
}

int dpUP(int n){
    
    for(int r=0;r<=n;r++){
        for(int l=0;l<=r;l++){
           dp[l][r] = min(dp[l][r] , 1 + get(l,r-1));
            for(int i=l;i<r;i++){
                if(s[i] == s[r]){
                    dp[l][r] = min(dp[l][r] , get( l , i ) + get(i+1 , r-1) );
                }
            }
        }
    }
    return dp[0][n];
}

void __sol(){
    
    int n ; cin >> n;
    string kk;
    s = "";
   
    forr(i,n){
       cin >> kk ;
       s+= kk;
    }
   
   int len = s.size();
   for(int i=0;i<=len+1;i++){
       for(int j=0;j<=len+1;j++){
           dp[i][j]=INT_MAX;
       }
   }
    cout << dpUP(len-1) << "\n";
    
    return;
}


int main(){

    fastio
    ll tc=1; cin >> tc;
    while(tc--) __sol();
    return 0;
}

Time Complexity : O(n^3) where n is the total length of the concatenated string.


PS: I tried to explain it in a simple way.Hope you enjoyed solving this problem in Code Chronicles 2.0.Please don’t go through breakups.Thank You!

3 Likes

Great Editorial @yoga2001 :slight_smile:

2 Likes