XORABC-Editorial

PROBLEM LINK:

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

Setter: Jeevan Jyot Singh
Tester: Istvan Nagy, Aryan
Editorialist: Vijay

DIFFICULTY:

Easy

PREREQUISITES:

Bit Manipulation

PROBLEM:

JJ gives Chef a number X and challenges Chef to come up with three distinct numbers A, B, and C such that:

  • 0≤A,B,C<2^{30};
  • (A⊕B)+(B⊕C)+(C⊕A)=X.

Help Chef come up with three such numbers or determine that no such tuple exists.

Here, denotes the bitwise XOR operation.

EXPLANATION:

Observation: We can show that the parity of X cannot be odd. Suppose we define the parities of A,B ,C and then use the equation to obtain the parity of X.

Case 1: All are odd
In this case all the xor values will be even. Since the sum of even numbers is even. Thus X is even.

Case 2: Any two of the numbers are odd
In this case two of the pairs will give odd xor value and remaining even. Since the sum of two odd value is even . Thus X is even in this case also.

Case 3: Only one of the numbers is odd
In this case also two of the pairs will give odd xor value and remaining even. Thus X is even in this case also.

Case 4: All are even
In this case all xor values will be even . Thus X is even in this case also.

Now we know that answer does not exist for odd values of X. So,considering that X is even we can construct the tuples as follows.
Let’s say we choose one the numbers as 0.
I claim that this does not effect the existence of solution. Suppose some solution tuple (a,b,c) satisfying both conditions in the problem exist such that a>0,b>0 and c>0. Then we can always get another tuple with exactly one number equal to 0 by xoring all numbers with one of the number of tuple . Let’s say we choose to xor with c , then we will have (a⊕ c,b⊕ c,0) as c⊕ c=0 .

Now we can simplify our original equation by putting C=0.
We have , A + B+ A⊕ B =X … (1)

Let’s define S=X/2 and S' be the value of any set bit in S.
If there is only one set bit in S we cannot form a valid tuple otherwise we can always construct solution tuple by choosing tuple (S,S',0)

We can see that by choosing tuple (S,S',0) equation (1) becomes S+S'+S⊕ S'=2*S=X
Thus forming a valid tuple.

TIME COMPLEXITY:

O(log(X)) depending upon the method used for finding the set bit.

SOLUTION:

Editorialist's Solution
#include <bits/stdc++.h>


using namespace std;

#define nline '\n'
void solve()
{

int x;
cin>>x;

if(x%2==1){
     cout<<-1<<nline;
}
else{
    for(int i=0;i<30;i++){
        if(((1<<i)&(x/2)) && (x/2!=1<<i)){
           cout<<(x/2)<<" "<<(1<<i)<<" "<<0<<nline;   // cout<<S<<" "<<S'<<" "<<0<<nline; 
           return;
        }
    }

    cout<<-1<<nline;
}


}



int main()
{   

   
   int t=1;
   cin >> t;

   while (t--)
   {
       solve();
   }
}

2 Likes

Please explain why there will be no solution when X is a power of 2.

1 Like

In that case, the number will have only one set bit and as given in the editorial if S is having only one set bit then no tuple exist.

1 Like

hey @masteranimax Thanks for sharing your doubt

As mentioned in the editorial the solution tuple is (S, S^′,0)
where S= X/2 and S^′ be the value of any set bit in S.

If X is power of 2 then X/2 will also power of 2. Then S and S^′ will be equal.
That’s why X cannot be power of 2

2 Likes

please tell why this code is giving wrong answer?

#include <bits/stdc++.h>

using namespace std;

int main()
{
int t;
cin>>t;
for(int i=0;i<t;i++)
{
double x;
cin>>x;
if((int)(x)%2==1)
cout<<"-1\n";
else
{
if((floor)(log(x)/log(2))==(ceil)(log(x)/log(2)))
{
cout<<"-1\n";
}

    else
    {
      cout<<"0 "<<x/2<<' '<<pow(2,(floor)(log(x/2)/log(2)))<<"\n";
    }
  }
}

return 0;

}

hey can someone intuitively explain why no answer exists when it is a power of 2.
with proof (intuitive please)