XORMAX - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: utkarsh_25dec
Testers: IceKnight1093, tejas10p
Editorialist: IceKnight1093

DIFFICULTY:

1229

PREREQUISITES:

None

PROBLEM:

Given two binary strings A and B, find the maximum possible value of A\oplus B if both strings can be rearranged as you wish.

EXPLANATION:

Since we’d like to maximize the xor, we’d like to have as many 1's as possible.

We can obtain a 1 by:

  • Pairing a 0 in A with a 1 in B
  • Pairing a 1 in A with a 0 in B

Now, let A_0 and A_1 be the count of 0's and 1's in A. Similarly define B_0 and B_1.

Notice that we can obtain at most \min(A_0, B_1) ones of the first type, and \min(A_1, B_0) ones of the second type.
Of course, it’s always possible to attain exactly these many ones since they’re independent.

So, our final string has \min(A_0, B_1) + \min(A_1, B_0) ones, and then every other character is 0.
To maximize the xor, place all the ones before the zeroes.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Code (Python) 
for _ in range(int(input())):
    a = input()
    b = input()
    n = len(a)
    a0, a1 = a.count('0'), a.count('1')
    b0, b1 = b.count('0'), b.count('1')
    ones = min(a0, b1) + min(a1, b0)
    print('1'*ones + '0'*(n - ones))
2 Likes
2

Why am I getting time limit exceeded?

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

void solution()
{
    string A, B, C = "";
	cin >> A >> B;
	int one = 0, zero = 0, length = A.length();
	for(int i = 0; i < length; i++)
	{
	    if(A[i] == '1')
	    {
	        one++;
	    }
	    else
        {
            zero++;
        }
        if(B[i] == '1')
        {
            one++;
        }
        else
        {
            zero++;
        }
	}
	int X = min(one, zero);
	for(int i = 0; i < X; i++)
	{
	    C = C + '1';
	}
	for (int i = 0; i<length - X; i++)
	{
	    C = C + '0';
	}
	cout << C<< endl;
}

int main() {
	// your code goes here
	int T;
	cin >> T;
	while(T--)
	{
        solution();
	}
	return 0;
}
3

Your code has complexity \mathcal{O}(N^2) because C = C + '1'; (and C = C + '0';) take \mathcal{O}(N) time, not \mathcal{O}(1).

Instead use C += '1' and C += '0'

4 Likes
4

Thanks for your answer, the problem is solved. However, I have looked through Google about this and most of the answers say that x +=1 and x= x+1 are same. Please explain the time complexity of these two in short.

5

a += b and a = a + b are actually slightly different things if you look at what the operators mean.

a += b means "apply the += operator on a and b. For integers, this means adding b to a. For strings, this means appending b to a (notice that it modifies a, but doesn’t need to touch the existing characters in a).

a = a + b means "create the value a + b, then assign it to a".
For integers, this isn’t a problem because creating the value a + b is easy, but it’s a problem for strings, since you create an entirely new string each time you append something.

For example, say you append c N times to an empty string S one by one using S = S + 'c'

  • In the first iteration, it creates the string c, then assigns it to S
  • In the second iteration, it creates the string cc then assigns it to S
  • In the third iteration, it creates the string ccc then assigns it to S
    \vdots

It’s easy to see that the total length of strings you create is 1 + 2 + 3 + \ldots + N = N(N+1)/2

You can test this yourself easily, just try running the code

string s = "";
for (int i = 0; i < 1000000; ++i) s += '0';

then replace the statement with s = s + '0' and see what happens.

5 Likes
6

Thanks for the explanation.

The s += ‘0’ code runs fast whereas s = s + ‘0’ takes a loooong time and throws SIGTSTP

7

What is wrong with this code ?
It has passed all test cases for Sample 1 , but overall Result is WA

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

string max_xor(string s1,string s2){
    int cnt_0=0,cnt_1=0;
    int n=s1.size();
    string s3="";
    for(int i=0;i<n;i++){
        if(s2[i]=='1')
            cnt_1++;
        else
            cnt_0++;
    }
    for(int i=0;i<n;i++){
        
        if(s1[i]=='1'){
            if(cnt_0>0)
            {
                cnt_0--;
                s3+='1';
            }
            else
                s3+='0';
        }
        else
        {
            if(cnt_1>0)
            {
                cnt_1--;
                s3+='1';
            }
            else
                s3+='0';
        }
    }
    return s3;
}

int main() {
	int T;
	cin>>T;
	while(T--){
	    string A,B;
	    cin>>A>>B;
	    cout<<max_xor(A,B)<<endl;
	}
	return 0;
}
8

Consider

1
101
000

where your code prints 101 but the answer is 110.
You’re correctly computing the number of ones in the answer, they just might not be in the right positions.

9

Thanks a lot, for solving my query and providing the test case.
So to get all 1 at correct place we can use sorting [ Using 2 pointers to avoid Runtime error] in the final string.
OR
what else can we do to make this code work ? , other than using the same solution as in editorial.