MINOPS - Editorial

editorial
, , , ,
22

I did the exact same thing, can you please give me a test case where this code fails:
https://www.codechef.com/viewsolution/32056884

Please let me know my mistake

Thanks

1 Like
23

Very well written editorial…thanks for putting in such efforts.

2 Likes
24

Legends say he is still searching for the example :sweat_smile: :sweat_smile: :sweat_smile:

4 Likes
25

Great explanation!!! Especially, the way the detailed explanation is broken down into several observations is awesome. Please provide editorials for others contests like this.

1 Like
26

badstuffGot:joy:
Nice Editorial!

1 Like
27

thanks a lot

1 Like
28

Alternatively, we can start from k = 1, and go up by removing the segments of equal characters in descending order of lengths.

Here is a very short solution in Python 3.

1 Like
29

eeee thanks :slight_smile: my first time writing edis so any other improvements is also welcome.

1 Like
30

Whats the problem with my code can any one help.
what i am doing is storing the index of element which are same in the string.
if there is gap between indexes>1 then i am increasing length and cnt.
i am taking care of the first and the last indexes i have stored (by calculating v[0]-1And s.size()-V[n-1] and if value is greater than zero the i am increasing cnt
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main()
{
int t;cin>>t;
while(t–)
{
string a,b;cin>>a>>b;
vectorv;
for(int i=0;i<a.size();i++)
{
if(a[i]==b[i])
v.push_back(i+1);
}
if(v.size()==0){
cout<<(a.size()*1)<<endl;
continue;}
// v.push_back(a.size());
ll cnt=0;
ll len=0;
for(int i=0;i<v.size();i++)
{
if(i==0)
{
len+=(v[i]-1);

            if((v[i]-1)>=0)
            cnt++;
        }
        else
        {
          
                len+=(v[i]-v[i-1]-1);
                if((v[i]-v[i-1]-1)!=0)cnt++; 
        }
        //cout<<len<<endl;
    }
    len+=(a.size()-v[v.size()-1]);
    if((a.size()-v[v.size()-1])!=0)
    cnt++;
    cout<<cnt*len<<endl;
    
}

}

31

Hi,@priyanshu_nch your code wrong for
s=bbabbccaabcccacabcbc
r=ccbbbcbabcaccabbaccc
right answer should be 19 but your code give 0. check please

32

anyone plz look at my code what is the problem and what i am missing
solution is -

#include <bits/stdc++.h>
using namespace std;
#define ll long long int

int main()
{
ll t;
cin>>t;
while(t–){
string s1,s2;
cin>>s1>>s2;
ll l=0,k=0,cs=0,cd=0;
vector< ll > v;
//cs is consecutive same char and cd is consecu. diff. element
for(int i=0;i<s1.size();i++){
if(s1[i]==s2[i]){
cs++;
if(cd!=0){
l+=cd, k++, cd=0;
}
}
else{
cd++;
if(cs!=0){
v.push_back(cs), cs=0;
}
}
}
if(cs!=0){
v.push_back(cs);
}
if(cd!=0){
l+=cd,k++;
}
ll ans=k*l;
sort(v.begin(),v.end());

    for(auto i:v){
        
        if(k>=2){
        l+=i;k--;}
        ans=min(ans,k*l);
    }
    cout<<ans<<endl;
}
return 0;

}

33

how is answer 19 ?
sum of lenghts is 11 and cnt is 5 so answer should be 55 rather
I am confused ? length is the number of consecutive no equal elements

35

Got it,Thank you.

36

Can anyone help with debugging my code? I am getting WA.

#include<bits/stdc++.h>
#define int long long
#define endl ‘\n’
#define mod 1000000007
#define inf 1e18
#define w(x) int x; cin>>x; while(x–)
using namespace std;
bool sieve[100007];
void sieve_make()
{
memset(sieve,true,sizeof(sieve));
sieve[0]=sieve[1]=false;
for(int i=2;ii<=100006;i++)
{
if(sieve[i])
{
for(int j=2i;j<=100006;j+=i)
sieve[j]=false;
}
}
}

/ll min(ll a,ll b)
{
if(a<b)
return a;
else
return b;
}/
int modexp(int a,int b,int c)
{
if(a==0) return 0;
if(b==0) return 1;

int ans;
if(b%2==0)
{
	int small=modexp(a,b/2,c);
	ans=(small*small)%c;
}
else
{
	int small=modexp(a,b-1,c);
	ans=(a%c);
	ans=(small*ans)%c;
}
return (ans+c)%c;

}

string rev(string s)
{
reverse(s.begin(), s.end());
return s;
}

int32_t main()
{
ios::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(“input.txt”,“r”,stdin);
freopen(“output.txt”,“w”,stdout);
freopen(“error.txt”,“w”,stderr);
#endif

w(t)
{
	string s,r;
	cin>>s>>r;
	if(s==r)
	{
		cout<<0<<endl;
		continue;
	}
	int k=0,l=0;
	for(int i=0;i<s.length();i++)
	{
		if(s[i]!=r[i])
			l++;
	}
	for(int i=0;i<s.length();i++)
	{
		if(s[i]!=r[i])
		{
			k++;
			int j=i;
			while(j<s.length() and s[j]!=r[j])
				j++;
			i=j;
		}
	}
	int ans=k*l;
	vector<int>equal;
	for(int i=0;i<s.length();i++)
	{
		
		if(s[i]==r[i])
		{
			int j=i;
			int len=0;
			while(j<s.length() and s[j]==r[j])
			{
				len++;
				j++;
			}
			equal.push_back(len);
			i=j;
		}
	}
	sort(equal.begin(),equal.end());
	for(int i=0;i<equal.size() and k>0;i++)
	{
		l+=equal[i];
		k--;
		ans=min(ans,k*l);
	}
	cout<<ans<<endl;
	
}

}

37

Elaborate please?

38

Hey, i approached the problem in a similar way. Instead of taking the islands of unequal characters I took the matching letters (I also took care of matching letters in the starting or the end). I removed the islands of correct characters in decreasing order of their size, I still got WA. Mind helping?

39

CAN SOMEONE PLEASE FIND THE PROBLEM IN MY CODE .

I THINK THAT IT IS PERFORMING WELL FOR ALL CASES BUT STILL GIVING WRONG ANSWER

PLEASE HELP!!

/*************************************************************************************************************************/
#include<bits/stdc++.h>
#define ull unsigned long long
#define lld long long int
#define infi LLONG_MAX
#define ninfi LLONG_MIN
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define e endl
#define mod 1000000007
#define isPowerOfTwo(S) (!(S & (S - 1)))
#define nearestPowerOfTwo(S) ((int)pow(2.0, (int)((log((double)S) / log(2.0)) + 0.5)))
using namespace std ;
/**************************************************************************************************************************/

                                            //to_string(n).length()---predicts length of a integer
                                            //stoi()---converts string to number
                                            //atoi()----converts no to string

/**************************************************************************************************************************/
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 
lld t;
cin>>t;
vector<lld>v;
while(t--){
    string s,s1;
    cin>>s>>s1;
    lld cnt=0,left=0,right=0,one=0;
    v.pb(0);
    for(lld i=0;i<s.length();i++){
        if(s[i]==s1[i]){
            v.pb(0);
        }else{
            v.pb(1);
        }
    }
    v.pb(0);
    for(lld i=0;i<v.size();i++){
        if(v[i]==0 && v[i+1]==1){
            cnt++;
        }
        if(v[i]==1){
            one++;
        }
    }
    for(lld i=v.size()-1;i>=0;i--){
        if(v[i]==1){
            right=i;
            break;
        }
    }
    for(lld i=0;i<v.size();i++){
        if(v[i]==1){
            left=i;
            break;
        }
    }
    cout<<min(cnt*one,right-left+1)<<e;


}

}

/**************************************************************************************************************************/

40

please explain why cant we bridge 3 or more consecutive islands

41

my code is working on all the test cases i can think of but still i am getting WA.
can someone provide some edge cases on which my code is failing.
code : https://www.codechef.com/viewsolution/32111831

42

bro avoid using set use vector and then check your logic