BINOP - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest
Practice

Author: Dymtro Berezein
Testers: Istvan Nagy
Editorialist: Praveen Dhinwa

DIFFICULTY:

Easy

PREREQUISITES:

binary operations

PROBLEM:

Chef has a string A. He wants the string to convert into string B by applying the following operations as many times as needed. In each operation, we choose two indices i, j, i \neq j.

result = A_i \, op \, A_j
A_i = result \, op \, A_i
A_j = result \, op \, A_j

op operation could be bitwise AND, XOR or OR operation.

Find out minimum number of operations required or state if it is impossible.

QUICK EXPLANATION:

If A = B, then no operation is required. In fact, problem guarantees that A \neq B.
If A consists of all 1’s or all 0’s, then you can’t convert it to B, as A won’t change with the operations.

Let cnt_0 denote the number of indices where A_i and B_i differ and A_i = 0.
Let cnt_1 denote the number of indices where A_i and B_i differ and A_i = 1.
Then, answer will be max(cnt_0, cnt_1).

EXPLANATION:

If A = B, then no operation is required. In fact, problem guarantees that A \neq B.
If A consists of all 1’s or all 0’s, then you can’t convert it to B, as A won’t change with the operations.

Understanding of operations
Let us try to understand what these operations do?

OR operation:
result = A_i \, OR \, A_j
A_i = result \, OR \, A_i
A_j = result \, OR \, A_j

Which is equivalent to
result = A_i \, OR \, A_j
A_i = result
A_j = result

i.e. either A_i or A_j is 1, you can make both of them equal to 1.

AND operation:
result = A_i \, AND \, A_j
A_i = result \, AND \, A_i
A_j = result \, AND \, A_j

Which is equivalent to
result = A_i \, AND \, A_j
A_i = result
A_j = result

i.e. either A_i or A_j is 0, you can make both of them equal to 0.

XOR operation
result = A_i \, XOR \, A_j
A_i = result \, XOR \, A_i
A_j = result \, XOR \, A_j

Which is equivalent to
result = A_i \, XOR \, A_j
A_i = result \, XOR \, A_i = A_j
A_j = result \, XOR \, A_j = A_i

i.e., you can swap any two elements A_i, A_j, note that this operation will be useful if one of them is 0 and other 1.

Take some example
Let us take some example.

0 0 0 1 1    
1 1 1   0 0

Note that you can not make any operation only among first three zeros to make all of these ones. You can swap first 0 and fourth 1, using XOR operation. After that swap second 0 and fifth 1. Now you will end up with

1 1 0 0 0    
1 1 1   0 0

Now, you can take first one and third zero, and replace third number by 1, by using OR operation. You will end up with

1 1 1 0 0    
1 1 1   0 0

So, in total we required three operations.

Final solution
Let cnt_0 be number of indices i, where A_i = 0 and B_i = 1.
Let cnt_1 be number of indices i, where A_i = 1 and B_i = 1.

Let us think about the cnt_0 elements, where A_i = 0 and B_i = 1. We have to change all of these zeros into ones. Note that this will require at least cnt_0 operations.

Let us think about the cnt_1 elements, where A_i = 1 and B_i = 0. We have to change all of these ones into zeros. Note that this will require at least cnt_1 operations.

Let op = max(cnt_0, cnt_1). We can make the A an B equal in op operations as follows.

  • Let cnt_0 \geq cnt_1. Take cnt_1 0’s and cnt_1 1’s in A and apply the XOR operation to swap 0’s with 1’s. After that you will be left with total cnt_0 - cnt_1 zeros elements to change to one. That you can do by taking each of these zeros with some single one and applying the OR operation.
  • Other case can be handled respectively.

Time Complexity:

\mathcal{O}(n) for iterating over both the strings, where n is size of strings A or B.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester

2

Is this a typo?

Let cnt1 be number of indices i, where Ai=1 and Bi=1.

Let us think about the cnt1 elements, where Ai=1 and Bi=0.

Both lines contradict definition of cnt1.

3

corrected.

4

discussion on this problem:
blog link

5

Can someone tell what’s wrong with this approach?
This is my solution :

6

try the case when both strings are equal. You get -1 as answer which should be 0

7

why i am getting tle…though i run only one loop…my solution link is below
https://www.codechef.com/viewsolution/10290678

thanks

2 Likes
8

My case is altogether different. My code passed all test cases except for one in Subtask#1 and one in Subtask#2
Here is the code


please someone help me out

9

The time complexity of your code is O(tn^2) not O(tn).Do refer to the link below for explanation.

https://www.quora.com/What-is-the-worst-mistake-youve-made-in-competitive-programming/answer/Chirag-Agarwal-15

2 Likes
10

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

int main()
{
int t;
cin>>t;
while(t–)
{
string s1,s2;
cin>>s1>>s2;
int count =0;
int count1=0;
int countone=0;
int countzero=0;
for(int i=0;i<s1.length();i++)
{
if(s1[i]==‘0’) countzero++;
if(s1[i]==‘1’) countone++;
if(s1[i]==‘0’ &&s2[i]==‘1’)
{
count++;

	    }
        if(s1[i]=='1' && s2[i]=='0')
		{
		  count1++;
	    }
	}
	//cout<<countzero<<endl;
	//cout<<countone<<endl;
	if(countzero ==s1.length() ||countone==s1.length())
	cout<<"Unlucky Chef\n";
	else 
	{
	cout<<"Lucky Chef\n";
	cout<<max(count,count1)<<endl;
    }
}

}