 # CHANDF - EDITORIAL

Author: Harshil Mehta
Editorialists: Alei Reyes, Harshil Mehta
Tester: Danya Smelskiy

EASY - MEDIUM

# PREREQUISITES:

Bitwise operations, Brute forces

# PROBLEM:

Given X, Y, find the minimum Z between L and R (inclusive) that maximizes F(X,Y,Z) = (X \& Z) \cdot (Y \& Z).

# NOTATION:

1. Let’s denote the bitwise-AND as ‘\&’ and the bitwise-OR as ’ | '.

2. Let’s represent the numbers as binary strings, and denote the i-th most significant bit of number S by S[i]. For example the string (binary) representation of 18 is S=10010, note that S=1. For simplicity let’s consider that all strings have the same length (we can append zeroes to the left if necessary).

3. Let S[L...R] denote the substring that goes from L to R inclusive. e.g S=10100 then S[1..4]=0100

4. The longest common prefix of two strings A and B is the maximum L such that the first L characters of A are equal to the first L characters of B. Note that this is equivalent to the minimum index i (0-indexed) such that A[i] \neq B[i]. If A=B, then their longest common prefix is equal to |A|

# QUICK EXPLANATION:

If there are no bounds for L and R, then F is maximum when Z=X|Y in which case F = X \cdot Y.
We can brute force all prefixes of L and R, toggle their next bits in order to get Z less than R and greater than L and append the bits of X | Y at the end.

# EXPLANATION:

#### Subtask 1: 0\leq Z \leq 2\cdot max(X,Y)

Given an integer X, how to find the smallest Z that maximizes P=X \& Z?

• Note that P is not greater than X, after applying the bitwise AND some of the bits of X will be toggled off, and no bit of X will be toggled on. Formally there is no index i such that X[i]=0 and P[i]=1 (because 0 \& B = 0 for any B).
• Therefore the minimum Z that maximizes P is X i.e the maximum value of P is X \& X = X.

To maximize F=(X \& Z) \cdot (Y \& Z) we would like to have the maximum (X \& Z) and the maximum (Y \& Z), how to find a Z that maximizes both terms at the same time?

• For each i, if X[i]=1 then Z[i] must also be equal to 1, in that way the i-th bit will not be toggled off after applying the bitwise AND.
• Similarly, if Y[i]=1 then Z[i] must also be equal to 1
• Note that the previous two conditions are satisfied by Z=X|Y

Example: Let X = 0101 and Y = 1001, note that 1111 maximizes F, however to minimize Z we only need the bits turned on of both numbers i.e Z=X|Y = 1101

#### Subtask 2: 0 \leq Z\leq R

Now we’ll solve the problem when there is only an upper bound i.e L=0
For simplicity let’s suppose that the optimum Z is strictly smaller than R.

Let’s suppose that the longest common prefix of Z and R is k (To find the optimum Z we can brute force all the possible k) in other words, let k be the smallest index in which R and Z are different. Since Z \lt R, then R[k]=1 and Z[k]=0.

The first k bits of Z guarantee that it will be smaller than R so we have the freedom of turning on any of the bits at positions greater than k, similarly to the previous subtask, in order to minimize Z we have to use the bits of X|Y i.e Z[i]=X[i] | Y[i], i \gt k.

Example: Let X = 000100, Y = 100001 and L = 0, R = 010010.
Let’s bruteforce all the possible longest common preffix of Z and R:

• k=1, we turn off R and append bits of X | Y: Z = 000101.
• k=4, we turn off R and append bits of X | Y : Z= 010001.
• Thus, the optimum Z = 000101.

#### Subtask 3: L \le Z \le R.

For simplicity let’s suppose that L \lt R.

Let k be the longest common preffix of L and R, then Z[0...k-1]=L[0..k-1]=R[0..k-1], since the first index at which L and R are different is k, then R[k]=1 and L[k]=0 (because L \lt R).

Let M be the longest common prefix of Z and R (To find the optimum we can brute force all possible M). There are two cases:

• If M > k: Then Z is already bigger than L, and the problem is reduced to the case when there is only an upper bound.
• If M=k: Then Z is already smaller than R, and the problem is reduced to the case when there is only a lower bound, which can be solved similarly, by brute-forcing all the possible longest common prefixes of Z and L.

Example: Let X = 000100, Y = 100001 and L = 001010, R = 010100.

• Let’s see the case when M = k, let’s try for all i (i \gt k) where L[i] = 0, and turn on Z[i] = 1 to make Z \ge L and append the bits of X|Y.

• i = 3, we turn on L and append bits of X|Y : Z = 001101.
• i = 5, we turn on L and append bits of X|Y : Z = 001011.
• Thus, the optimum Z = 1101.

There are also some approaches where modified binary search can be used to find the optimal Z which maximizes the F(X, Y, Z).

# COMMON ERRORS:

• Not finding the greedy approach of bit-traversal brute force, as there is no O(1) solution possible.
• Always check the function F at the Z = L and Z = R.
• Beware of cases where X,Y,L,R = 0.
• Keep a filter while selecting Z such that L \le Z \le R and Z is as minimal as possible that maximizes the F(X, Y, Z).

The overall complexity of this approach is O(bits * bits) per each test case where bits are the total bits of this number in its binary form.

# SOLUTIONS:

Setter's Solution
//   ^_HAR HAR MAHADEV_^
//   |Om Namah shivaya|

// AUTHOR: Harshil Mehta

#include <bits/stdc++.h>
//For ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include<boost/multiprecision/cpp_int.hpp>
#define mod 1000000007
#define test int t; cin>>t; while(t--)
#define init(arr,val) memset(arr,val,sizeof(arr))
#define f(i,a,b) for(int i=a;i<b;i++)
#define fr(i,a,b) for(int i=a;i>=b;i--)
#define ll long long int
#define fast ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(a) a.begin(),a.end()
#define br "\n"
//using namespace boost::multiprecision;
using namespace std;
// For ordered_set
using namespace __gnu_pbds;
template <typename T>
using ord_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int maxn = 1e5;

ll x , y , l , r ;
ll sol = LLONG_MAX , tmp_sol = 0;
// Product Function
ll func(ll z) {
return ((x & z) * (y & z)) ;
}
ll brute_force() {
ll mx = -1 ;
ll z = 0;
f(i,l,r+1) {
if(mx < func(i)) {
mx = func(i) ;
z = i ;
}
}
return z ;
}
// Auxillary function for obtaining prefix bits which are common
int get_pre() {
tmp_sol = 0 ;
int k = 0;
for(int i = 42 ; i >= 0; i--) {
if((r & (1LL << i)) == (l & (1LL << i))) {
if((r & (1LL << i))) {
tmp_sol |= (1LL << i) ;
}
} else {
k = i ;
break ;
}
}
return k;
}
void solve() {
cin >> x >> y >> l >> r ;
ll _or = (x|y) ;
//ll ans_bf = brute_force();
ll mx = func(l) ,t_sol = tmp_sol ;
sol = l ;
int k = get_pre() ;
for(int i = k ; i >= 0 ; i --) {
// intialising container with prefixed value
t_sol = tmp_sol ;
// taking all possible prefix of R
for(int j = k ; j >= i + 1; j--) {
if(r & (1LL<<j)) {
t_sol |= (1LL << j) ;
}
}
// switching i th bit as Z should be smaller than R (not needed as it is already OFF)
t_sol &= (~(1LL << i));
// Copying next bits of X OR Y for maximizing F
for(int j = i - 1; j >= 0 ; j--) {
if(_or & (1LL << j)) {
t_sol |= (1LL << j) ;
}
}
// checking for validations
if(t_sol <= r && t_sol >= l) {
// selecting optimal solution
if(mx < func(t_sol)) {
mx = func(t_sol) ;
sol = t_sol ;
}
// taking minimal possible Z
if(mx == func(t_sol))sol = min(t_sol , sol) ;
}
}
for(int i = k ; i >= 0 ; i --) {
// intialising container with prefixed value
t_sol = tmp_sol ;
// taking all possible prefix of R
for(int j = k ; j >= i + 1; j--) {
if(l & (1LL<<j)) {
t_sol |= (1LL << j) ;
}
}
// turning i th bit as Z should be greater than L
t_sol |= (1LL << i);
// Copying next bits of X OR Y for maximizing F
for(int j = i - 1; j >= 0 ; j--) {
if(_or & (1LL << j)) {
t_sol |= (1LL << j) ;
}
}
// checking for validations
if(t_sol <= r && t_sol >=l) {
// selecting optimal solution
if(mx < func(t_sol)) {
mx = func(t_sol) ;
sol = t_sol ;
}
// taking minimal possible Z
if(mx == func(t_sol))sol = min(t_sol , sol) ;
}
}
// Checking for upper bound and lower bound
if(func(r) > mx) {
sol = r ;
}
cout << sol << br ;
sol = LLONG_MAX;
}
int main() {
fast ;
int t = 1;
cin >> t;
while(t--) {
solve();
}
return 0;
}

Tester's solution
#include <iostream>
#include <string>
#include <cassert>
#include <cstdio>
using namespace std;

const long long MX = 1e12;

long long optimal_z;
long long result;
long long x, y, l, r;

long long f(long long x, long long y, long long z) {
return (x & z) * (y & z);
}

void update_ans(long long z) {
long long cur = f(x, y, z);
if (cur > result || (cur == result && z < optimal_z)) {
optimal_z = z;
result = cur;
}
}

void print_binary(long long x) {
string res = "";
for (long long i = 42; i >= 0; --i) {
if (x & (1ll << i))
res += "1";
else
res += "0";
}
cout << res << '\n';
}

void solve(int test_id) {
scanf("%lld %lld %lld %lld\n", &x, &y, &l, &r);
//assert(l == 0 && r >= 2ll * max(x, y));
assert(0 <= x && x <= MX);
assert(0 <= y && y <= MX);
assert(0 <= l && l <= MX);
assert(0 <= r && r <= MX);
assert(l <= r);

optimal_z = r;
result = f(x, y, optimal_z);
update_ans(l);
bool is_less = false;
long long bits_or = (x | y);

for (long long i = 42; i >= 0; --i) {
long long p = (1ll << i);
if ((r & p) && (is_less || !(l & p))) {
long long cur = 0;
for (long long k = 42; k > i; --k) {
long long p = (1ll << k);
if (r & p)
cur |= p;
}
bool is_bigger = is_less;
for (long long k = i - 1; k >= 0; --k) {
long long p = (1ll << k);
if (!(l & p)) {
if (bits_or & p) {
cur |= p;
is_bigger = true;
}
} else {
if (!is_bigger || (bits_or & p))
cur |= p;
}
}
if (l <= cur && cur <= r)
update_ans(cur);
is_less = true;
}
}
printf("%lld\n", optimal_z);
return;
}

int main(int argc, const char * argv[]) {
#ifdef __APPLE__
freopen("/Users/danya.smelskiy/Documents/Danya/Resources/input.txt","r",stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tests;
scanf("%d\n", &tests);
for (int i = 0; i < tests; ++i) {
solve(i);
}
return 0;
}

55 Likes

Nice editorial !!

6 Likes

Agreed

4 Likes

https://www.codechef.com/viewsolution/32677957
Am i not doing the same thing as mentioned for 2nd subtask?

In the first subtask if both x and y are of the order 2^32 or bigger ,then the value x|y will be larger than 2^62 and it should not pass the subtask,correct me if I’m wrong

1 Like

X|Y of numbers less than 2^32 will be less than 2^32 4 Likes

if x and y both are equal to 2^35 then x|y will be equal to 2^35 now in this case the value of F will be 2^70 but it is stated in the question that it should not exceed 2^62 ,correct me if I’m wrong

They have chosen values such that it won’t ever exceed 2^62. Constraints says that.

2 Likes

It was given in the question that the max value is less than 2^62 …
The test cases were such that the max value is less than 2^62

You are missing only one case where X, Y = 10^{10} and R \le X|Y.

2 Likes

I could not understand the example for subtask 1:

Example: Let X = 0101X=0101 and Y = 1011Y=1011, note that 111111 maximizes FF, however to minimize ZZ we only need the bits turned on of both numbers i.e Z=X|Y = 1101


In this case Z=X|Y = 1111, Why is the this not the case ?

https://www.codechef.com/viewsolution/32708857
for case 2 only, in which cases is my code failing ? i have tried a modified one sided binary search approach.

@harshil21 sir in the explanation of sub-task 2, you made an error while turning off R.
It should be Z=0100101. 1 Like

Fixed typo.
Thanks!

1 Like

“Common error”
What if X = 0 and Y = 3 and L = 0, R = 10?

7 Likes

If one out of x or y becomes 0 then ans should be 0.So u should check for that first…

1 Like

• L=0L=0
• R≥2⋅max(X,Y)

*should it not be R<=2⋅max(X,Y)

can someone explain this with reference to that in solution for sub-task 1 Subtask
0 ≤Z ≤2⋅max(X,Y)

i used same approach for this after reading this (as it was unclear), but it gave WA on task 1 too, seems silly but it should work

#include
using namespace std;
#define ll long long
int main() {
int t;
cin>>t;
//t=1;
while(t–)
{
ll x,y,l,r;
cin>>x>>y>>l>>r;

   cout<< (x|y)<<"\n";
}
return 0;


}

in problem it is said it won’t exceed 2^62

Your code shows an overflow error for X, Y \ge 10^{9}.

you should also check the case when either x=0 or y=0
the answer should be zero in that case.

1 Like