CHANDF - EDITORIAL

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:

  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[3]=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[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;
}
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 :stuck_out_tongue:

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[4].
It should be Z=0100101. :slight_smile:

1 Like

Fixed typo.
Thanks!

1 Like

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

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

Subtask #1 (15 points) :

  • 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() {
// your code goes here
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