that’s more work for the tester too 
Mine did get AC. Although I use Pypy but it’s still Python.
Shouldn’t the answer be f(s1)+f(s2)-f(lcs(s1,s2))? Because lcs(s1,s2) will return a string s3 and we have to apply the function f(s3) to determine exactly how many indices satisfies Ci≠Ci+1.
2 Likes
Thanks for keeping it simple 
True- I never meant that adding that clause was to make it tougher. Point was, seeing his dp states and table I thought it would have been a nice addition to the problem.
@sapfire @vijju123 some tweaking for x =1 and x=2 with lcs approach got me AC on this one . But can anyone explain to me the D.P. approach , I am clueless on that .
@abhi55 Thanks for answering my doubt. I understood the part of optimization of my LCS function but I did not exactly understood the first part. " but you should do that consecutive diffrent character only in string implementation before LCS in o(n) and after that lcs it will give correct answer" Can you please explain this again? Sorry for this, I did not get my mistake in the program. I have found out LCS including repetition but my function “findCharacters(String)” will always return be the number of indices satisfying Ci≠Ci+1.
i am saying that suppose you have string aabccdee now you can see that consecutive same character will make no change in total cost like in above string you first minimize it in abcde by removing repition of same character which are consecutive in o(n) then perform LCS part on it
#include<bits/stdc++.h>
using namespace std;
int lcs(char* X, char* Y, int m, int n)
{
int L[m + 1][n + 1];
int i, j;
for (i = 0; i <= m; i++) {
for (j = 0; j <= n; j++) {
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i - 1] == Y[j - 1])
L[i][j] = L[i - 1][j - 1] + 1;
else
L[i][j] = max(L[i - 1][j], L[i][j - 1]);
}
}
/* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */
return L[m][n];
}
int main()
{
int t; cin>>t;
while(t–)
{
int n,m; cin>>n>>m;
char a[n];
char b[m];
int x=1,y=1;
for(int i=0;i<n;i++) {
cin>>a[i];
if(i==0) continue;
if(a[i-1] != a[i]) x++;
}
for(int i=0;i<m;i++) {
cin>>b[i];
if(i==0) continue;
if(b[i-1] != b[i]) y++;
}
int res = lcs(a,b,n,m);
// cout<<x+y<<endl;
cout<<x+y-res<<"\n";
}
}
what is the error guys?
why my solution is giving tle
// Problem: String Merging
// Contest: CodeChef - Practice(Easy)
// URL: STRMRG Problem - CodeChef
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#include
#include
#include<unordered_map>
#include
#include<unordered_set>
#include
#include
#include
#include
#include<string.h>
#include
#include
#include<math.h>
#include
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// #define int long long int
#define d1(x) cout<<#x<<“: “<<x<<endl
#define d2(x, y) cout<<#x<<”: “<<x<<” | “<<#y<<”: “<<y<<endl
#define d3(x, y, z) cout<<#x<<”:” <<x<<" | “<<#y<<”: “<<y<<” | “<<#z<<”: “<<z<<endl
#define d4(a, b, c, d) cout<<#a<<”: “<<a<<” | “<<#b<<”: “<<b<<” | “<<#c<<”: “<<c<<” | “<<#d<<”: “<<d<<endl
#define d5(a, b, c, d, e) cout<<#a<<”: “<<a<<” | “<<#b<<”: “<<b<<” | “<<#c<<”: “<<c<<” | “<<#d<<”: “<<d<<” | "<<#e<< ": “<<e<<endl
#define d6(a, b, c, d, e, f) cout<<#a<<”: “<<a<<” | “<<#b<<”: “<<b<<” | “<<#c<<”: “<<c<<” | “<<#d<<”: “<<d<<” | "<<#e<< ": “<<e<<” | “<<#f<<”: "<<f<<endl
/*SOME SHORTCUTS*/
#define f(i,a,b) for(int i=a;i<b;i++)
#define fr(i,a,b) for(int i=a;i>=b;i–)
#define lb lower_bound
#define ub upper_bound
#define ll long long int
#define pb push_back
#define pf push_front
#define lcm(a, b) ((a) * (b)) / __gcd(a, b)
#define mp make_pair
#define in insert
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
// #define memset(a) memset(a,0,sizeof(a))
const int MOD = 1e9 + 7;
const int mod = 1e9 + 7;
int cnt1=0,cnt2=0,cnt3=0,cnt4=0,cnt5=0,ans1=0,ans2=0,ans3=0;
// bool prime[2000001];
bool prime[1000001];
/*int f[400005],inverse[400005];
int divide(int n)
{return pow1(n,mod-2); }
int ncr(int n, int r)
{if(n<r) return 0;return (f[n]*((divide(f[r]) * divide(f[n-r])) % mod)) % mod; } */
bool comp(string s1, string s2){
if(s1.size()>s2.size()){
return true;
}
else if(s1.size()<s2.size()){
return false;
}
else{
if(s1>s2){
return false;
}
else{
return true;
}
}
}
void sieve() {
memset(prime, true, sizeof(prime));
for (int i = 2; i * i <= 1000000; i++)
if (prime[i])
for (int j = i * i; j <= 1000000; j+= i)
prime[j] = false;
prime[0] = prime[1] = false;
}
string s1,s2;
int n,m;
int dp[5005][5005][2];
int find1(int ind1,int ind2 ,int flag1){
if(dp[ind1][ind2][flag1]!=-1){
return dp[ind1][ind2][flag1];
}
if(ind1==n && ind2==m){
return 0;
}
char a1;
if(flag1==0){
a1=s1[ind1-1];
}
else{
a1=s2[ind2-1];
}
int p1=0;
if(ind1==n){
if(s2[ind2]!=a1){
return dp[ind1][ind2][flag1]=1+find1(ind1,ind2+1,1);
}
return dp[ind1][ind2][flag1]=find1(ind1,ind2+1,1);
}
if(ind2==m){
if(s1[ind1]!=a1){
return dp[ind1][ind2][flag1]=1+find1(ind1+1,ind2,0);
}
return dp[ind1][ind2][flag1]=find1(ind1+1,ind2,0);
}
int p2=0;
if(s1[ind1]!=a1){
p1++;
}
if(s2[ind2]!=a1){
p2++;
}
return dp[ind1][ind2][flag1]=min(p1+find1(ind1+1,ind2,0),p2+find1(ind1,ind2+1,1));
}
void solve(){
cin>>n>>m;
f(i,0,n+2){
f(j,0,m+2){
f(k,0,2){
dp[i][j][k]=-1;
}
}
}
cin>>s1>>s2;
int z1=1+min(find1(1,0,0),find1(0,1,1));
cout<<z1<<endl;
return;
}
int main(){
//sieve();
IOS;
int t=1;
cin>>t;
while(t–){
solve();
}
return 0;
}