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();
}
}