XORMUL - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Jeevan Jyot Singh
Tester: Takuki Kurokawa
Editorialist: Yash Kulkarni

DIFFICULTY:

1739

PREREQUISITES:

Bit Manipulation

PROBLEM:

JJ has three integers N, A and B where 0 \le A, B \lt 2^N. He wants to find a third integer X such that:

  • 0 \le X \lt 2^N
  • the value of (A \oplus X) \times (B \oplus X) is maximum.

Can you help him find such an integer X? If there are multiple integers which satisfy the given conditions, print any.

EXPLANATION:

We need to consider only the first N bits of A, B, and X because all are < 2^N. Let us consider the i^{th} bit of A and B. There are 3 possibilities:

  • i^{th} bits of both A and B are set (1). If we keep the i^{th} bit of X as 0 then the i^{th} bits in both (A \oplus X) and (B \oplus X) are set. This clearly maximizes the product.
  • i^{th} bits of both A and B are not set (0). If we keep the i^{th} bit of X as 1 then the i^{th} bits in both (A \oplus X) and (B \oplus X) are set (1). This clearly maximizes the product.
  • i^{th} bits of A and B are both different i.e. one set (1) and one not set (0). In this case irrespective of what the i^{th} bit in X is, one among the i^{th} bits in (A \oplus X) and (B \oplus X) is set (1) and the other is not set (0).

From the first two points it is clear that we can write (A \oplus X) as C + D and (B \oplus X) as C + E, such that C is the number having set (1) bits at all positions where the bits of A and B are same and has all other bits not set (0).
From the third point, D and E have a fixed sum (2^N - C -1) which is equal to that number having set (1) bits at all positions where the bits of A and B are different and has all other bits not set (0).

The product to be maximized simplifies to (C + D) \times (C + E) = C^2 + C \times (2^N - C - 1) + E \times D. The first two terms are fixed based on A, B, and N. The last term involves maximizing the product of two integers having fixed sum. For this, it is clear that we will choose X so that D and E are as close as possible.

Let us say that for D the most significant bit where A and B differ is set (1), then E should be such that it has set bits at all other positions (leaving the most significant position) where A and B differ. This is because 2^K \geq 2^{K_1} + 2^{K_2} + ... 2^{K_X}, where all K_1, K_1, … K_X are distinct and < K.

In summary, X is chosen so that:

  • (A \oplus X) and (B \oplus X) have set bits at all positions where A and B have same bits.
  • Either (A \oplus X) or (B \oplus X) has a set bit at the most significant bit position where A and B differ and at all other positions it has 0 bits and vice versa.

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Setter's solution
using namespace std;

int main()
{
    int T; cin >> T;
    while(T--)
    {
        int n, a, b; cin >> n >> a >> b;
        int ans = 0;
        bool fst = 1;
        for(int i = n - 1; i >= 0; i--)
        {
            bool A = a >> i & 1;
            bool B = b >> i & 1;
            if(!A and !B)
                ans |= 1 << i;
            if(A and !B)
            {
                if(fst) 
                    fst = false;
                else
                    ans |= 1 << i;
            }
            if(!A and B)
            {
                if(fst)
                    ans |= 1 << i, fst = false;
                else
                    ;
            }
        }
        cout << ans << endl;
    }
    return 0;
}
Editorialist's Solution
using namespace std;

int main() {
	int T;
	cin >> T;
	while(T--){
	    int n,a,b;
	    cin >> n >> a >> b;
	    int c=0;
	    bool ok=true;
	    for(int i=n-1;i>=0;i--){
	        if(((1<<i)&a)==((1<<i)&b)){
	            if(((1<<i)&a)==0)c+=(1<<i);
	        }
	        else if(ok){
	            if(((1<<i)&b))c+=(1<<i);
	            ok=false;
	        }
	        else{
	            if(((1<<i)&a))c+=(1<<i);
	        }
	    }
	    cout << c << endl;
	}
	return 0;
}
1 Like

Actually we can just check for every bit if turning bit on will be good or bad, be greedy !!!
We will iterate for all positions from 1 to N-1 if it’s good we will add it to res else no need, we will keep updating result every time

#include <bits/stdc++.h>
#define int long long int

void solve(){
    int n, a, b;
    std::cin >> n >> a >> b;
    int num = (1<<(n-1)), ans = 0;
    for(int i=0; i<n; i++){
        int k = num+ans;
        int x = (a^ans)*(b^ans);
        int y = (a^k)*(b^k);
        if(y > x)
            ans += num;
        num >>= 1;
    }
    std::cout << ans << "\n";
}
     
signed main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // ONLINE_JUDGE

    int t = 1;
    std::cin >> t;
    while(t--){
        solve();
    }
}

Can reduce few lines of code, probably not a good idea

void solve(){
    int n, a, b;
    std::cin >> n >> a >> b;
    int x = (1<<n), y = 0;
    while(x >>= 1)
        y += ((a^(x+y))*(b^(x+y)) > (a^y)*(b^y)) ? x : 0;
    std::cout << y << "\n";
}
13 Likes

what does variable num represents in your code?

i guess it is same as 1<<i

Initially,
num == 2^(N-1)

num can’t take value greater than or equal to 2^N…that’s why, it’s like (n-1)th set bit, I will check for every bit from (n-1)th position to 0th position if it’s better for this bit to be set in x, if it’s optimal I will add that bit to answer, it’s like saying ans |= num

Why?

1 Like

A Simple Solution was to check for each bit greedily. Since our answer X cannot be greater than 2^(N), we can directly start checking from N-1th bit if setting this bit will result in a bigger product or not. This too we will check only if the current bit is set in one number and is not set in other number. In case the current bit is not set in both numbers, we can directly set this bit in X as it will increase the numbers by that bit after xorring with X. If current bit is set in both numbers, then we will not add this bit to X.

given two numbers x and y such that x+y=c (constant).
to maximize p=xy ,it can be proven that x=y=c/2 (by taking derivative and setting it to zero).

Thus product is maximized when two numbers are equal.
Consequently, we will move towards the greater product when two numbers tend towards being equal to each other (since the function is continuous).

3 Likes

Its given that D and E have a fixed sum equal to 2^N - C but I found that fixed sum is equal to 2^N - 1 - C. Kindly check this in the editorial.
Thanks!

1 Like

Can you ples tell, why it is giving WA!
I also approached the ques , same way as you did.

'''
if x==y==0 , set the bit
elif x==y==1 , unset the bit
elif x==0 , y==1 or x==1, y==0:
    we are sure we can set the bit(bcz either it will benefit from a or benefit from b), but we need to see...
    secondly , we want product to be maximised, so eventually we want 
    a^x and b^x to have minimum difference and be close as much as possible.
    
    So, we need to see if difference is increasing, we will set the bit such that min(a, b) will benefit and difference will decrease..
'''

def solve():
    n ,a ,b = map(int, input().split())
    c = 0
    for i in range(n-1, - 1, -1):
        x = a&(1<<i)
        y = b&(1<<i)
        
        if x==0 and y==0:
            c+=(1<<i)
        elif (x==0 and y==1) or (x==1 and y==0):
            cur = (a^c)*(b^c)  # ans with unset
            newc = c+(1<<i)
            new = (a^newc)*(b^newc) # ans with set
            
            if new>cur:
                c = newc

    print(c)

for testis in range(int(input())):
    solve()

Thanks.

well could add some proof for why you started out with the most significant bit (1<<n) and not from the 0th bit?

Well, it’s matter of choice, you can do it both ways

#include <bits/stdc++.h>
#define int long long int

void solve(){
    int n, a, b;
    std::cin >> n >> a >> b;
    int num = 1, ans = 0;
    while(n--){
        int k = num+ans;
        int x = (a^ans)*(b^ans);
        int y = (a^k)*(b^k);
        if(y > x)
            ans += num;
        num <<= 1;
    }
    std::cout << ans << "\n";
}
     
signed main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // ONLINE_JUDGE

    int t = 1;
    std::cin >> t;
    while(t--){
        solve();
    }
}

Here, starting from first bit

Change this to

        x = (a>>i)&1
        y = (b>>i)&1

It will get accepted

1 Like

Hey, thanks for reply.
Aren’t both the same things?
We are checking if ith bit is set or not…
What is mistake in my way of checking.

Suppose a = 13 i.e. 1101, we have to check 3rd bit is set or not

  1. a&(1<<2) = (1101)&(0100) == 100 which is not equal to 1
  2. (a>>2)&1 = (0001)&(0001) == 001 which is equal to 1

If you want your code to work using first operation then change if and elif conditions to !x and !y, !x and y or x and !y…Don’t compare with x==0, x==1, this will give wrong answer

1 Like

Accepted

def solve():
    n ,a ,b = map(int, input().split())
    c = 0
    for i in range(n-1, - 1, -1):
        x = a&(1<<i)
        y = b&(1<<i)
        
        if x == 0 and y == 0:
            c+=(1<<i)
        elif (x == 0 and y) or (x and y == 0):
            cur = (a^c)*(b^c)  # ans with unset
            newc = c+(1<<i)
            new = (a^newc)*(b^newc) # ans with set
            
            if new>cur:
                c = newc

    print(c)

for testis in range(int(input())):
    solve()

That was very silly, I shud have checked =0 and !=0.

Thnx for the reply. Appreciate it.

1 Like

Bro you have done a tiny but big mistake. when you take AND of two numbers it can be any value. Not just 1 and 0. If bit is not set, then AND would be 0 using the mask(1<<i) but suppose if bit was set, the AND of that bit and mask would be a power of 2 not necesserily 1. If it was 1st bit, then AND would be 2, if 2nd bit, then 4. Simple words Take AND of 6 and 2, and we are checking for 1st bit ,then it is 2 not 1, cause in binary we see them as (110 and 010) and when you take their AND it becomes 010 which is 2 not 1 so in your if condition where you have written x==1 or y==1, write x!=0 or y!=0.

1 Like
												// Be greedy !!!
void Solve() {
	ll n, a, b;
	cin >> n >> a >> b;

	ll x = 0;

	for (ll i = n - 1; i >= 0; i--) {
		// need to check whether by set this bit is maximize the result or not
		ll prev = (a ^ x) * (b ^ x);
		ll cur = (a ^ (x + (1LL << i))) * (b ^ ((x + (1LL << i))));
		if (cur > prev) {
			x += (1LL << i);
		}
	}

	cout << x << endl;
}

why greedy approach should work?