IRSTXOR - Editorial

semal10 · March 13, 2021, 1:50pm

PROBLEM LINK:

Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest

Author: Semal Sherathia
Tester: Felipe Mota
Editorialist: Alei Reyes

DIFFICULTY:

SIMPLE

PREREQUISITES:

Greedy, Bit-Manipulation

PROBLEM:

You are given an integer C. Let d be the smallest integer such that 2^d is strictly greater than C.

Consider all pairs of non-negative integers (A,B) such that A,B \lt 2^d and A \oplus B = C (\oplus denotes the bitwise XOR operation). Find the maximum value of A \cdot B over all these pairs.

QUICK EXPLANATION:

We can think greedily here in terms of bit representation and see that when two numbers are as close as possible to each other, they yield maximum product given their sum is constant. So, to make them close as possible , we can set MSB (which is set in C) in A, and all other set bits in C we can set in B to make them both closer. And for every unset bit in C , we can set that bit in both A and B to make it max possible number.

EXPLANATION:

You would need basic XOR concept to understand this problem. The XORed result has either two kind of bits in binary representation.

If ith bit is 0 in C then ith bit of A and B should be either 0 or 1 in both the integers. Since we need maximized product so we will always set ith bit = 1 in A and B whenever ith bit is 0 in C.

Now interesting case comes when ith bit is 1 in C. We know that either one of A or B has ith bit set and other unset. If you list put every possible combinations you will notice that the sum of A and B remains constant. And when sum of A and B is constant we get maximum product when A and B are at close to each other.

Eg A+B = 6.

Possible Combinations :

  A      B      Product
  1      5         5
  2      4         8
  3      3         9

So we get max product 9 when A and B are very close to each other.

So to make A and B close to each other, we apply greedy approach and it goes as follows :

For MSB set bit in C we will set that bit in A and for all the other set bit in C, we will make that bit set in B. So that A and B are close to each other and product maximises.

Let’s see one such example.
C = 13 , Binary representation : 1101.

When iterating from right to left in binary of C, we get first MSB set in C, so we will set that in A. Following bit is also set but now onwards whenever set bit is present in C, we will set that bit in B to make them both closer. So, 2nd and 4th bit (from right side) in C is set and likewise we should set in B. Now the 3rd bit is unset in C, so we will set that bit in both A and B to yield maximum number itself.

After this logic, we have A as 1010 in binary (10 in decimal) and B as 0111 in binary (7 in decimal). And the maximum product will have to be 70.

Also note that the lengths of A and B in their binary representation should be equal of that of C. So no other pair of A and B yields maximum product while satisfying this condition too.

SOLUTIONS:

Setter's Solution

#include<bits/stdc++.h>
#include<climits>

using namespace std;

#define debug(x,y) cout<<(#x)<<" " <<(#y)<<" is " << (x) <<" "<< (y) << endl
#define watch(x) cout<<(#x)<<" is " << (x) << endl
#define fast ios_base::sync_with_stdio(false)
#define fie(i,a,b) for(i=a;i<b;i++)
#define MOD 1000000007
#define mod 998244353
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define ll long long
#define lld long long int
#define ALL(x) (x).begin(),(x).end()

typedef vector<lld> vi;
typedef vector<vector<lld>> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<pair<lld, lld>> vpi;
typedef long long LL;

string convert(lld n) {
	string s = "";
	while (n > 0) {
		if (n % 2 == 1) s = "1" + s;
		else s = "0" + s;
		n /= 2;
	}
	return s;
}

lld convertBack(string s) {
	lld n = 0 , p = 1;
	for (lld i = s.length() - 1; i >= 0; i--) {
		n += ((s[i] - '0') * p);
		p *= 2;
	}
	return n;
}

int main() {
	fast;
	cin.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w" , stdout);
#endif
	lld t, n, i;
	cin >> t;
	while (t-- > 0) {
		//converting number to binary
		cin >> n;
		string s = convert(n);
		string a = "" , b = "";
		bool first = false;
		//greedy approach mentioned in editorial
		//brief explanation again here :
		//if ith bit is 0 in original number then, ith bit in A & B should be 1 to maximise product.
		//if ith bit is 1 in original number then the MSB of C should be set in A and all the other set bit in C should be set in B.
		//So that both the numbers A & B are close to each other in their magnitude which results in maximum product.
		for (i = 0; i < s.length(); i++) {
			if (s[i] == '0') {
				a += "1";
				b += "1";
			}
			else {
				if (first) {
					a += "0";
					b += "1";
				}
				else {
					a += "1";
					b += "0";
					first = true;
				}
			}
		}
		//convert back from binary representation to their respective numbers.
		lld n1 = convertBack(a);
		lld n2 = convertBack(b);
		cout << n1*n2 << endl;
	}
}

Tester's Solution

steve004 · March 15, 2021, 11:10am

Can someone please explain how does the given method ensures that A and B are close to each other?

varunn_14 · March 15, 2021, 11:36am

Let me Just explain this with a simple example and then generalize.
Firstly we’ll consider a string of size 4 as an example.

If we only set the msb bit we’ll end with A = “1000” => 8.
If we set all other bits other than msb we’ll end up with B = “0111” => 7.
Here as you see the A and B values are close to each other and they are the maximum possible values as such.
Now this can simply be extended to any length of string as, if A = set only msb gives us value n, then B = set all bits other than msb always gives us value n-1.
This is the basic rule.

Now as said in the question, let us take the same example 13 => “1101” and trace it.

For MSB set in C we set it in A -------so A = "1_ _ _ ", B = “0 _ _ _”.
For other bits if 0 in C we’ll set both A and B ------------so A = “1_ 1 _” , B = “0 _ 1 _”.
For other bits if 1 in C we’ll only set bit in B --------------so A = “1010”, B = “0111”.

This is making the values A and B close and is maximising the product value.
Hope this clears your doubt.

adityanand09 · March 15, 2021, 11:43am

basically the answer is (((1<<(d-1))-1)^c) * ((1<<(d-1)) - 1)

surya_2002 · March 15, 2021, 11:53am

I’m getting correct for all giventestcases but its not accepting
could u explain why??
#include <stdio.h>

int main(void ) {

// your code goes here

int t;

scanf("%d",&t);

while(t–)

{long long int d=1,i=0,f[100000],count=0,a=1,b=1;

long long int c;

scanf("%lld",&c);

while(d<c)

{d=2*d;}

for(a=1 ;a<d;a++)

{for(b=1 ;b<d;b++)

if((a&(~b)|b&(~a))==c)

{f[i]=a*b;

count++;

i++; } }

// printf("%d\n",count);

//int max=f[0];

for(int i=1;i<count;i++)

{if(f[0]<f[i])

{f[0]=f[i];}

}

printf("%lld\n",f[0]);

}

return 0;

}

skaarss · March 15, 2021, 1:20pm

For a 6 length binary number each bit’s value is 32, 16, 8, 4, 2, 1
here the MSB is 32 > (16+8+4+2+1) , you can try these for any length and the MSB should be greater than the summation of all other bits so the decimal with 1 as the MSB is always greater than any number with MSB as 0.

sleepytoad · March 15, 2021, 3:14pm

Can anyone explain why this solution is not accepted and giving WA for first 3 test cases:

import java.util.;
import java.lang.;
import java.io.*;
import java.math.BigInteger;
import java.util.Scanner;
import java.util.StringTokenizer;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{

public static void main (String[] args) throws java.lang.Exception
{
	
	// your code goes here
	
try {	
	Scanner sc=new Scanner(System.in);
	
	int t=sc.nextInt(),n;
	String s,a,b;
	int flag;
	int c,d;
	
	for(int i=0;i<t;i++)
	{
	    
	     n=sc.nextInt();
	    
	   s=Integer.toBinaryString(n);
	    
	     a="";b="";
	    
	     flag=0;
	     int len=s.length();
	    for(int j=0;j<len;j++)
	    {
	        if(s.charAt(j)=='1' && flag==0)
	        {
	            a+="1";
                         
                       flag=1;
	        }
	        
	        else if(s.charAt(j)=='1' && flag==1)
	        {
	            b+="1";
	            a+="0";
	        }
	        
	        else 
	        {
	            a+="1";
	            b+="1";
	        }
	        
	    }
	    
	     c=Integer.parseInt(a,2);
	     d=Integer.parseInt(b,2);
	    

	    long e=(long)c*d;
	   
	   System.out.println(e);
	    
	}}
	
	catch(Exception e){}
	
	
}

}`

But just by adding b+=“0”; before flag=1; in first if condition is accepted.

piyush_121 · March 18, 2021, 7:56am

The approach of maximizing the A and B using Bit Manipulation is great and surely a new thing for a lot of people.
Another approach which is on the same lines but a bit simpler to understand and maybe a lot of other participants followed was :-

First find the value of d for 2^d > C , then take the value of ( 2^(d-1)/2 - 1 ) and set this value to A or B. Now use the property , if A XOR B = C then A XOR C = B.

For example, if C = 13 , 2^d = 16 - > d = 4. so, ( 2^(4-1) - 1 ) = 7 = A .
As, A XOR B = C , so A XOR C should be equal to B , i.e. 7 XOR 13 , which is 10. you have A and B now. Product is your answer.

The explanation behind this concept is, as C = 13 is always >= 2^(d-1). so the MSB here is always 1. to get the MSB as 1. Only one of the two digits, will have MSB as 0 and other will have it as 1. Highest number with MSB 0 would be 2^(d-1) - 1. That would be our A or B. Now using the property we can find the other digit and it will give us correct answer.

You can try to prove the property if you wish or just search the web for it’s proof.

aditya4298 · March 19, 2021, 10:33pm

I used the same aproach but got a TLE with it.

darkknight1077 · March 20, 2021, 6:54pm

Please help me with why the below code is giving WA error for the three test case ,
#include <bits/stdc++.h>
using namespace std;
string toBinary(long long int n)
{ string s;
for (int i = 31; i >= 0; i–) {
int k = n >> i;
if (k & 1)
s = s + “1” ;
else
s = s + “0” ;
}
s.erase(0, min(s.find_first_not_of(‘0’), s.size()-1));
return s;
}
int toInt(string s)
{
long long int n;
n = std::stoi(s, nullptr, 2);
return n;
}
int main() {
// your code goes here

long int t=0,d=0;
string s,a,b;
long long int c=0,max=0;
cin>>t;
while(t--)
{
    cin>>c;
   // d=floor(log2(c)) + 1;
   // d = pow(2,d);
   // for(long int i=d-1;i>0;i--)
   // {
   //     for(long int j = i-1 ; j > 0 ; j--)
   //     {
   //         if( (i ^ j) == c )
   //         {  
   //            // cout<<"I^J:"<< ( i ^ j );
   //             if(max < i * j)
   //             {   
   //                 max = i * j;
                    
   //             }
   //         }
   //     }
   // }
   // cout<<max<<"\n";
   // max = 0
   s = toBinary(c);
   if(s[0] == '1')
   {
       a = "1";
       b = "0";
   }
   for( long long int i = 1 ; i < s.length() ; i++)
   {
       if(s[i]=='1')
       {
           a = a + "0";
           b = b + "1";
       }
       if(s[i]=='0')
       {
           a = a + "1";
           b = b + "1"; 
       }
   }
   
    cout<<toInt(a) * toInt(b)<<"\n";
}

return 0;

}

rockstar_20 · March 25, 2021, 9:54am

for its proof what should i search on web?

prashantexp · March 29, 2021, 5:11pm

Java implementation of given idea .

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef {
	public static void main(String[] args) throws java.lang.Exception{
		Scanner sc        = new Scanner(System.in);
		Codechef ix = new Codechef();
		
		int T = sc.nextInt();
		for(int i = 0; i < T; i++) {
			int x = sc.nextInt();
			long ans = ix.getMaxProduct(x);
			System.out.println(ans);
		}
	}
	
	private long getMaxProduct(int x) {
		String sx = Integer.toBinaryString(x);
		StringBuilder A = new StringBuilder();
		StringBuilder B = new StringBuilder();
		boolean first = true;
		for(int i = 0; i < sx.length(); i++) {
		    if(sx.charAt(i) == '0') {
		        A.append('1');
		        B.append('1');
		    }
		    else {
		        if(first == true) {
		            A.append('1');
		            B.append('0');
		            first = false;
		        }
		        else {
		            A.append('0');
                    B.append('1');
		        }
		    }
		}
		
		long ai = Long.valueOf(A.toString(), 2);
		long bi = Long.valueOf(B.toString(), 2);
		long res = ai * bi;
		return res;
	}
}

adarshcr71234 · September 27, 2022, 6:03pm

as per requirement if msb is 1 then we have to add 1 in a and 0 in b thats why.
hope it help.strong text