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:
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;
}