MINOPS - Editorial

editorial
, , , ,
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

43

bro avoid using set use vector and then check your logic .

44

2 Solutions

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

typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;

#define FOR(i, n)  for(int i=0; i<(n); i++)
#define FORA(i, a, n) for(int i = a; i <= (n); ++i)
#define FORD(i, a, n) for(int i = a; i >= (n); --i);
#define mod 1000000007
#define pi 2acos(0.0)
#define MP make_pair
#define PB push_back
#define EB emplace_back // its's faster than push_back
#define F first
#define S second
#define sz(x) (int)(x).size()
#define what_is(x) cerr << #x << "is" << x << endl;
#define gcd(a, b) __gcd(num1 , num2)
int32_t main()
{
   	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin>>t;
    // Method 1  - > Traverse  k from k = 1 till k_max;
    while(t--) {
    	string s,r; cin >> s >> r;
    	int n = s.length();
    	if(s==r) {
    		cout << 0 << '\n';
    		continue;
    	}
    	int i = 0;
    	while(i < n) {
    		if(s[i]==r[i])
    			i++;
    		else
    			break;
    	}
    	int j = 0;
    	while(j < n) {
    		if(s[n-j-1]==r[n-j-1])
    			j++;
    		else
    			break;
    	}
    	int l_max = n - i - j; // values of l_max excluding the starting \
    	same values and ending same values;
    	int k_min = 1;
    	int ans = k_min*l_max;
    	vi equal_intervals;
    	int count = 0;
    	for(; i < n; i++) {
    		if(s[i]==r[i])
    			count++;
    		else
    		{
    			if(count>0)
    				equal_intervals.PB(count);
    			count = 0;
    		}
    	}
    	sort(equal_intervals.begin(), equal_intervals.end(), greater<int>());
    	for(int equal_iterval : equal_intervals) {
    		l_max -= equal_iterval;
    		k_min++;
    		// cout << k_min*l_max << '\n';
    		ans = min(ans, k_min*l_max);
    	}
    	cout << ans << '\n';
    }


    // Method 2: - > Traverse  k from k = k_max till 1;
 //    while(t--) {
 //    	string s,r; cin >> s >> r;
	// 	int n = s.length();
	// 	bool check = 0;
	// 	int count_equal = 0;
	// 	int k_max = 0;
	// 	int l_min = 0;
	// 	vi equal_values;
	// 	for(int i=0; i<n; i++) {
	// 		if(s[i]==r[i]) {
	// 			if(check)
	// 				count_equal++;
	// 		}
	// 		else {
	// 			if(!check) {
	// 				k_max++;
	// 				check = 1;
	// 			}
	// 			l_min++;
	// 			if(count_equal > 0) {
	// 				equal_values.PB(count_equal);
	// 				count_equal = 0;
	// 				k_max++;
	// 			}
	// 		}
	// 	}
	// 	sort(equal_values.begin(), equal_values.end());
	// 	int ans = k_max*l_min;
	// 	for(int equ_val : equal_values) {
	// 		l_min += equ_val;
	// 		k_max -= 1;
	// 		ans = min(ans, k_max*l_min);
	// 	}
	// 	cout << ans << '\n';
	// }		
    return 0;
}
45

Guys this is best video for this tutuorial. Watch this

4 Likes
46

whats wrong with this code
#include <bits/stdc++.h>
using namespace std;
char s[1000000],r[1000000];
//bool bysort(pair<long long int,long long int> &a,pair<long long int,long long int> &b){
//}
int main() {
long long int t,i,count,sum,k,l,ans,n,k1,sum1,a,b;
scanf("%lli",&t);
while(t–){
vectorv;
scanf("%s",s);
scanf("%s",r);
count=0;
l=0;
k=0;
sum=0;
a=0;
b=0;
n=strlen(s);
for(i=0;i<n;i++){
if(s[i]!=r[i]){
if(count==0){
k++;
a=i+1;}
count++;
}
else{
sum=sum+count;
if(count>0){
if(k>1)
v.push_back(a-b-1);
b=a+count-1;
count=0;
}
}
}
if(s[i-1]!=r[i-1]){
sum=sum+count;
v.push_back(a-b-1);
b=a+count-1;
count=0;
}
sort(v.begin(),v.end());
l=k;
ans=ksum;
for(i=0;i<(l-1);i++){
sum=sum+v[i];
k=k-1;
ans=min(ans,ksum);
}
printf("%lli\n",(ans));
}
// your code goes here
return 0;
}

47

Yes obviously we can, but each bridging decreases k by 1 right? hence if we bridge together say 5 islands, its effectively reducing k by 4. hence we only bridge two consecutive islands for every decrease in k by 1.

1 Like
48

Can anyone tell me where my code is wrong?
Link-CodeChef: Practical coding for everyone

49

Ok, got it Thanks a lot for explaining :grinning:

50

Thankyou for all the observation. It was really helpful

51

got it thanks!

52

Great Editorial!