FLIP - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter:
Tester: Rahul Dugar
Editorialist: Taranpreet Singh

DIFFICULTY

Simple

PREREQUISITES

None

PROBLEM

Given two binary strings A and B of same length, we need to determine the minimum number of operations to apply on A to convert A into B.

An operation involves picking an odd length substring of A and flipping all bits at odd position within this substring

QUICK EXPLANATION

  • Since each operation can affect positions of only same parity modulo 2, we can divide this into two simpler sub-problems, by splitting
  • Dividing both A and B into two strings each, odd indexed positions in one string (A_o and B_o) and even indexed positions in other string (A_e and B_e).
  • The operation now becomes to flip a consecutive segment, either in A_o or in A_e, in order to make A_o same as B_o and A_e same as B_e
  • It can be solved by a single pass over each string, maintaining the number of flips needed to make prefix of A_o and B_o and extending at each step.

EXPLANATION

Let’s consider an example of operation A = 0101101011, we apply operation at substring
A_{3,7} = 11010, we get 0100111111, as only bits at position 3, 5 and 7 are flipped in original string. Similarly, if operation is applied at A_{2,4}, we get 0111111011 as only positions 2 and 4 are flipped.

Crucial Observation
It’s easy to prove that no matter which substring we choose, the operation only affects either odd positioned bits, or even positioned bits.

Let’s split A into two strings A_o containing odd positioned bits of A in original order, and A_e containing even positioned bits of A in original order. Let’s do same for B.

Since our operation always affected consecutive bits of same parity, the operation on A is equivalent to flipping a consecutive sub-string of A_o or A_e, and the goal becomes to make A_o same as B_o and A_e same as B_e

Since both sub-problems are same, Let’s just focus on making A_e same as B_e

Another thing we can prove is that in optimal case, no two operation sub-strings would overlap, since for the overlap interval, flipping it twice gives same sub-string.

Hence, for each position, we can determine whether it needs to be flipped or not (by taking XOR of A_o and A_e). Let’s call this C_o

It’s intuitive to prove that the number of flips needed is the number of blocks consisting of ones in C_o.

We can similarly find C_e and add the operations needed for both odd and even positioned bits separately to get required number of operations.

TIME COMPLEXITY

Time complexity is O(N) per test case.

SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int N = 2e5 + 5;

int32_t main()
{
	IOS;
	int t;
	cin >> t;
	assert(t >= 1 && t <= 1000);
	int sumlen = 0;
	while(t--)
	{
		string a, b;
		cin >> a >> b;
		assert(a.size() == b.size());
		assert(a.size() >= 1 && a.size() <= 1e5);
		sumlen += a.size();
		assert(sumlen <= 1e5);
		int ans = 0;
		int n = a.size();
		for(int i = 0; i < n; i += 2)
		{
			if(a[i] == b[i])
				continue;
			while(i < n && a[i] != b[i])
				i += 2;
			ans++;
		}
		for(int i = 1; i < n; i += 2)
		{
			if(a[i] == b[i])
				continue;
			while(i < n && a[i] != b[i])
				i += 2;
			ans++;
		}
		cout << ans << endl;
	}
	return 0;
}
Tester's Solution
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}

long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);

			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}

int sum_n=0;
int holve(string a, string b) {
	int d=0,an=0;
	for(int i=0; i<sz(a); i++) {
		if(d) {
			if(a[i]==b[i])
				d=0;
		} else {
			if(a[i]!=b[i]) {
				d=1;
				an++;
			}
		}
	}
	return an;
}
void solve() {
	string a=readStringLn(1,100000);
	string b=readStringLn(sz(a),sz(a));
	int n=sz(a);
	sum_n+=n;
	assert(sum_n<=100000);
	string pa,pb,ppa,ppb;
	for(int i=0; i<n; i++) {
		if(i&1) {
			pa+=a[i];
			pb+=b[i];
		} else {
			ppa+=a[i];
			ppb+=b[i];
		}
	}
	cout<<holve(pa,pb)+holve(ppa,ppb)<<endl;
}

signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(7);
	int t=readIntLn(1,1000);
//	cin>>t;
	fr(i,1,t)
		solve();
	assert(getchar()==EOF);
#ifdef rd
//	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class FLIP{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
	String A = n(), B = n();
	StringBuilder[] a = new StringBuilder[]{new StringBuilder(), new StringBuilder()};
	StringBuilder[] b = new StringBuilder[]{new StringBuilder(), new StringBuilder()};
	int N = A.length();
	hold(A.length() == B.length());
	for(int i = 0; i< N; i++){
	    a[i%2].append(A.charAt(i));
	    b[i%2].append(B.charAt(i));
	}
	pn(calc(a[0].toString(), b[0].toString())+calc(a[1].toString(), b[1].toString()));
    }
    int calc(String A, String B) throws Exception{
	hold(A.length() == B.length());
	int flip = 0, ans = 0;
	for(int i = 0; i< A.length(); i++){
	    int d = (A.charAt(i)-'0')^(B.charAt(i)-'0');
	    if(d != flip){
	        ans++;
	        flip ^= 1;
	    }
	}
	return (ans+1)/2;
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
	in = new FastReader();
	out = new PrintWriter(System.out);
	//Solution Credits: Taranpreet Singh
	int T = (multipleTC)?ni():1;
	pre();for(int t = 1; t<= T; t++)solve(t);
	out.flush();
	out.close();
    }
    public static void main(String[] args) throws Exception{
	new FLIP().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
	BufferedReader br;
	StringTokenizer st;
	public FastReader(){
	    br = new BufferedReader(new InputStreamReader(System.in));
	}

	public FastReader(String s) throws Exception{
	    br = new BufferedReader(new FileReader(s));
	}

	String next() throws Exception{
	    while (st == null || !st.hasMoreElements()){
	        try{
	            st = new StringTokenizer(br.readLine());
	        }catch (IOException  e){
	            throw new Exception(e.toString());
	        }
	    }
	    return st.nextToken();
	}

	String nextLine() throws Exception{
	    String str = "";
	    try{   
	        str = br.readLine();
	    }catch (IOException e){
	        throw new Exception(e.toString());
	    }  
	    return str;
	}
    }
}

VIDEO EDITORIAL (Hindi):

VIDEO EDITORIAL (English):

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

1 Like

if any one needs

5 Likes

I did same approach test cases were also running fine but it showed me wrong answer can someone please review my code .
https://www.codechef.com/viewsolution/39771120

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

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        int sum=0;
        string a;
        string b;
        cin>>a;
        cin>>b;
        
        int i=0,j=0;
        while(i<a.size() && j<a.size())
        {
            if(a[i]==b[i])
            {
                i=i+2;
                j=j+2;
            }
            else
            {
                if(j==a.size()-1 || j==a.size()-2)
                {
                    sum++;
                    break;
                }
                else
                {
                    j=j+2;
                    if(a[j]==b[j])
                    {
                        if(j==a.size()-1 || j==a.size()-2)
                        {
                            sum++;
                            break;
                        }
                        else
                        {
                            sum++;
                            j=j+2;
                            i=j;
                        }
                    }
                    else
                    {
                        if(j==a.size()-1 || a.size()-2 )
                        {
                            sum++;
                            break;
                        }
                        else
                        {
                            j=j+2;
                        }
                    }
                }
            }
        }
        
        i=1,j=1;
        while(i<a.size() && j<a.size())
        {
            if(a[i]==b[i])
            {
                i=i+2;
                j=j+2;
            }
            else
            {
                if(j==a.size()-1 || j==a.size()-2)
                {
                    sum++;
                    break;
                }
                else
                {
                    j=j+2;
                    if(a[j]==b[j])
                    {
                        if(j==a.size()-1 || j==a.size()-2)
                        {
                            sum++;
                            break;
                        }
                        else
                        {
                            sum++;
                            j=j+2;
                            i=j;
                        }
                    }
                    else
                    {
                        if(j==a.size()-1 || a.size()-2 )
                        {
                            sum++;
                            break;
                        }
                        else
                        {
                            j=j+2;
                        }
                    }
                }
            }
        }
        
        cout<<sum<<endl;
    }
    return 0;
}
1 Like

This is my algo i think its easy to understand

Link : https://www.codechef.com/viewsolution/39750955

string a, b; cin >> a >> b;
int count = 0;
for (int i = 0; i < a.size(); ++i) {
if (a[i] != b[i]) {
count++;
if (i >= 2) {
if (a[i - 2] != b[i - 2])
count–;
}
}
}
cout << count << endl;

12 Likes

I took a slightly different approach, I just want to preface that my approach might be more difficult or easier to understand according to one’s inclinations.

The basis of my approach is that for every mismatch, we should do one “flip operation” (similar to XOR of 1). However, since we are able to group consecutive odd/even bits into the same flip operation, for each incremental “group” we are allowed to reduce the # of flip operations (res) by 1.

With this in mind, my code basically compares strings a and b. Then it creates an ArrayList that holds the indexes of the mismatches. Using this new ArrayList I created a method, named calc, that goes through the ArrayList and checks to see if the current, ith, index is an even/odd (checks for both even and odd) pair with the next (i+1) index. However, there is one special case that we have to keep in mind, it is possible for a even/odd pair to have an opposing mismatch (an even indexed mismatch, if the ith index is an odd index mismatch and vice versa) which could mess up our incremental approach, therefore I added a special case to test for this, by checking the i+2 index, if available.

Here is the code:

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

class Solution {
    public static ArrayList<Integer> form(String a, String b) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                list.add(i);
            }
        }
        return list;
    }

    public static int calc(ArrayList<Integer> list) {
        // res is initialized to the number of mismatches, then every time we find a
        // match we subtract one from res only if the two indexes of mismatches have a
        // difference of 2 therefore denoting that they can be grouped
        int res = list.size();
        for (int i = 0; i < list.size() - 1; i++) {
            // if (ith element + 2) is equal to the i+1 element then we can reduce 1 from
            if (list.get(i) + 2 == list.get(i + 1)) {
                res--;
                // this is the special conditon case for when the ArrayList of mismatches has an
                // opposite indexed mismatch in between two mismatch pairs. Ex: list = {2,3,4} 3
                // would be the opposite indexed mismatch because it is between 2 and 4 which
                // are an even-indexed mismatch pair.
            } else if (list.get(i) + 1 == list.get(i + 1)) {
                if (i < list.size() - 2 && (list.get(i) + 2 == list.get(i + 2))) {
                    res--;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        FastReader fr = new FastReader();
        int t = fr.nextInt();
        while (t-- > 0) {
            String a = fr.nextLine();
            String b = fr.nextLine();
            ArrayList<Integer> list = form(a, b);
            System.out.println(calc(list));
        }
    }

    // fast JAVA I/O class
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

Let me know if you have any questions or tips!

1 Like

Why is this solution not giving tle for this ques. Since more than o(n) should give tle.

What is time complexity of this code.

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;

while (t > 0)
{
	string a, b;

	cin >> a >> b;
	int  count = 0;

	for (int i = 0; i < a.length(); i++)
	{
		if (a[i] == b[i])
		{
			continue;
		}
		++count;
		for (int j = i; j < b.length()&&a[j]!=b[j]; j = j + 2)
		{
			
			
				a[j] = b[j];

			
		}
	}
	cout << count << endl;




	--t;

}


return 0;

}

O(n)

Can someone tell why this is giving WA:-

#include<bits/stdc++.h>

#define ll long long int
#define vi vector<int>
#define pb push_back


using namespace std;


int main() {
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);
//    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        string source;
        cin>>source;
        string target;
        cin>>target;
        if(source == target){
            cout<<0<<"\n";
            continue;
        }
        int to_change = 0;
        for(int i = 0;i<source.size();i++){
            if(source[i] != target[i]) to_change++;
        }
        int ans = 0;
        while(to_change != 0){
            if(to_change % 2 == 0){
                ans++;
                to_change = ((to_change-1)/2) + 1;
            }
            else{
                ans++;
                to_change = to_change/2;
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}
1 Like

Your code is failing on the following test case:

1
1010110111111
0101001111110

Expected Output - 3
Your output - 2

1 Like

Your code is failing on the following test case:

1
1010110111111
0101001111110

Expected Output - 3
Your output - 4

I think because length of string in each test case is not 10^5 , so it works.

can someone pls help
it is failing for some hidden test and I’m unable to figure that out

#include<bits/stdc++.h>
using namespace std;
int t,l,mini=0,maxi=0,c=0;
string a,b;
void change(int mini,int maxi)
{
    for(int i=mini;i<=maxi;i=i+2)
    {
        if(a[i]=='0')
        {
            a[i]='1';
        }
        else if(a[i]== '1')
        {
            a[i]='0';
        }
    }
    c++;
}

int main()
{
    cin>>t;
    while(t--)
    {
        c=0;
        cin>>a;
        cin>>b;
        l=a.length();
     for(int i=0;i<l;i++)
     {
         if(a[i]!=b[i]&&l==1)
         {
             a[i]=b[i];
             c++;
             break;
         }
         else if(a[i]!=b[i])
         {
             mini=i;
         for(int j=2;i+j<l;j=j+2)
         {
             if(a[i+j]==b[i+j])
             {
                 maxi=i+(j-2);
                 break;
             }
         }
         if(maxi>=mini)
         {
         change(mini,maxi);
         }
         else
         {
             change(mini,l-1);
         }
         }
     }
     cout<<c<<"\n";
    }
return 0;
}

Was this code accepted .
Actually i have also the same way but it failed uncertainly.

@taran_1407
Check last three para, isn’t it by taking xor of Ao and Bo

this code here using maps is way easier to understand :
string a,b;
cin>>a>>b;

int n=a.size() ;

map<int,int> mp ;

rep(i,n)
{
	if(a[i]!=b[i])
	{
		mp[i]++;
	}
}

int ans=0;
trav(i,mp)
{
	if(mp.find(i.f-2)==mp.end())
		++ans;
}
cout<<ans<<"\n";

can you please explain how you got output as 3?
I am finding it little hard to understand, as we will do either odd flip or even flip, but finallly after both flipping we will get A==B, so it will take only two steps to make A==B.
please explain, I tried understanding it but could not get.

edit: got the logic, and understood that substring is of odd-length, can’t be of whole of even-length, so it has to break down into two odd substrings,
also, nice editorial.

Show your code @kajal_1483