PROBLEM LINK
Practice
Div-2 Contest
Div-1 Contest
Author: Harshil Mehta
Editorialists: Alei Reyes, Harshil Mehta
Tester: Danya Smelskiy
DIFFICULTY:
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:
-
Let’s denote the bitwise-AND as ‘\&’ and the bitwise-OR as ’ | '.
-
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[3]=1. For simplicity let’s consider that all strings have the same length (we can append zeroes to the left if necessary).
-
Let S[L...R] denote the substring that goes from L to R inclusive. e.g S=10100 then S[1..4]=0100
-
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[1] and append bits of X | Y: Z = 000101.
- k=4, we turn off R[4] 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[3] and append bits of X|Y : Z = 001101.
- i = 5, we turn on L[5] 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.
Thanks for reading!
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() {
//FILE_READ_IN ;
//FILE_READ_OUT;
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;
}
