Can anyone tell me where my code is wrong?
Link-CodeChef: Practical coding for everyone
Ok, got it Thanks a lot for explaining 
Thankyou for all the observation. It was really helpful
got it thanks!
Great Editorial!
i am getting wrong answer can someone please debug it or provide me some testcases where it can give wrong answer.thanks.
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define endl “\n”
#define pb push_back
#define mp make_pair
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t–)
{
ll n,ans=0,i,k=0,kh=1,l;
string r,s;
cin>>s;
cin>>r;
n=s.length();
vectorv,v1;// vector v contains the indices where s[i]!=r[i]
// vector v1 contains the difference of adjacent element of vevtor v.
for(i=0;i<n;i++){
if(s[i]!=r[i]){
v.push_back(i);
k++;
}}
ll n1=v.size();
if(k==1)
cout<<“1”<<endl;
else{
l=k;
ans=kl;
//cout<<n1;
for(i=0;i<n1-1;i++){
v1.pb(v[i+1]-v[i]-1);
}
for(i=0;i<v1.size();i++){
ans=min(ans,(k-1)(l+v1[i]));
k–;
l=l+v1[i];
}
cout<<ans<<endl;}
}
return 0;
}
Help me find error in my logic - Each “island” will either will be merged with the previous one or won’t. For each island, I maintain a pair, which holds the total number of letters changed till (including ) that island, and the k values. Hence for every new island, the answer (k*l) for the two cases, i.e merged / unmerged, and go with the minimum.
Here is the code
1 Like
I am getting runtime(sigsegv) error on submission , but my code is running perfect for all test cases in my ide . Can Someone help me.
wow ! great explanation !! 
What to elaborate? Just do the other way around - start with a single segment (k = 1) that starts at the leftmost position of non-matching characters and ends at rightmost position of non-matching characters. Then remove the segments of equal characters in descending order of lengths. Each time you do this the number of contiguous segments (k) is incremented by 1, and the total length (l) decreases by the length of the removed segment.
I found this problem and its approach really interesting, can you share some similar sort of problems??
what is wrong in my code?
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--)
{
string s, r;
cin >> s >> r;
int n = s.length();
vector<int> gap;
int l = 0, k = 0, g = 0;
int flag = 1;
int gflag = 0;
int firstTime = 0;
for (int i = 0; i < n; ++i)
{
if (s[i] != r[i])
{
if (gflag)//making array of gaps
{
gap.push_back(g);
g = 0;
}
if (flag)//counting k
{
k++;
flag = 0;
}
l++;
gflag = 0;
firstTime = 1;
}
else
{
if (firstTime)//if starting is different no gap
{
g++;
gflag = 1;
firstTime = 1;
}
flag = 1;
}
}
int ans = k * l;
sort(gap.begin(),gap.end());
int kk = k;
for (int i = 0; i < kk - 1; ++i)
{
if(ans > (k-1)*(l+gap[i])){ //
k--;
l+= gap[i];
ans = k*l;
}
}
cout << ans << '\n';
}
return 0;
}
Please add comments in the code. It’s very difficult for beginners to understand without comments.
1 Like
Great editorial. This question took me longer than I’d like to admit.
To clarify on the Editorialist’s solution:
The variable fst stores the length of each successive gap encountered during the pass. The bool badstuffGot is used to ignore the identical characters in the prefix part (if present).
For eg. if strings are aaababa and aaaaaaa , then the initial aaa shouldn’t be considered.
Due to the nature of the pass, we push in fst into our vector only when we encounter unequal characters. Hence, identical characters in the suffix part of string s, will not be considered, which is correct.
2 Likes
Beautiful and well explained editorial, thanks a lot!
(https://www.codechef.com/viewsolution/32129967)
what is wrong in this solution . please tell atleast one test case
https://www.codechef.com/viewsolution/32137726
Why is this code giving segmentation fault? Please Help;
Clean understandable editorial specially observations its awesome Thanks!!
1 Like
I did it the editorial solution way, and saw some people doing it using priority queue as well. Still got WA in both, what am I missing?
Approach 1: https://www.codechef.com/viewsolution/32136784
Approach 2: https://www.codechef.com/viewsolution/32137788
Your code gives segmentation fault for the test case where both the strings are equal as vector ind will be empty and line 20 will make illegal reference and give sigsev