# CHANDF - EDITORIAL

**URL:** <https://discuss.codechef.com/t/chandf-editorial/63302>\
**Category:** editorial\
**Tags:** brute-force, easy-medium, editorial, may20, harshil21, bitwise-operation\
**Created:** [May 11, 2020, 9:30am UTC](https://discuss.codechef.com/t/chandf-editorial/63302 "2020-05-11T09:30:02Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![harshil21](https://discuss.codechef.com/user_avatar/discuss.codechef.com/harshil21/32/11855_2.png) [@harshil21](https://discuss.codechef.com/u/harshil21)\
**Post date:** [May 11, 2020, 9:30am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/1 "2020-05-11T09:30:02Z")

</div>

# PROBLEM LINK

[Practice](https://www.codechef.com/problems/CHANDF)  
[Div-2 Contest](https://www.codechef.com/MAY20B/problems/CHANDF)  
[Div-1 Contest](https://www.codechef.com/MAY20A/problems/CHANDF)

_Author:_ [Harshil Mehta](https://www.codechef.com/users/harshil21)  
_Editorialists:_ [Alei Reyes](https://www.codechef.com/users/alei), [Harshil Mehta](https://www.codechef.com/users/harshil21)  
_Tester:_ [Danya Smelskiy](https://www.codechef.com/users/smelskiy)

# DIFFICULTY:

EASY - MEDIUM

# PREREQUISITES:

[Bitwise operations](https://en.wikipedia.org/wiki/Bitwise_operation), 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](https://en.wikipedia.org/wiki/Bitwise_operation#AND) as ‘\&’ and the bitwise-[OR](https://en.wikipedia.org/wiki/Bitwise_operation#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 = 0 **0** 0101.
- k=4, we turn off R[4] and append bits of X | Y : Z= 0100 **0** 1.
- 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.

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

---

<div class="post-metadata">

**Author:** ![euler\_euler](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@euler\_euler](https://discuss.codechef.com/u/euler_euler)\
**Post date:** [May 11, 2020, 9:52am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/2 "2020-05-11T09:52:58Z")

</div>

Nice editorial !!

---

<div class="post-metadata">

**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\
**Post date:** [May 11, 2020, 9:54am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/3 "2020-05-11T09:54:57Z")

</div>

Agreed

---

<div class="post-metadata">

**Author:** ![pulkit\_mittal](https://discuss.codechef.com/user_avatar/discuss.codechef.com/pulkit_mittal/32/24644_2.png) [@pulkit\_mittal](https://discuss.codechef.com/u/pulkit_mittal)\
**Post date:** [May 11, 2020, 10:00am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/4 "2020-05-11T10:00:33Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![ronythakur](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ronythakur/32/320019_2.png) [@ronythakur](https://discuss.codechef.com/u/ronythakur)\
**Post date:** [May 11, 2020, 10:02am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/5 "2020-05-11T10:02:45Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\
**Post date:** [May 11, 2020, 10:04am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/6 "2020-05-11T10:04:12Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![ronythakur](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ronythakur/32/320019_2.png) [@ronythakur](https://discuss.codechef.com/u/ronythakur)\
**Post date:** [May 11, 2020, 10:07am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/8 "2020-05-11T10:07:47Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\
**Post date:** [May 11, 2020, 10:10am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/9 "2020-05-11T10:10:19Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![sinmoyyy](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sinmoyyy/32/3653_2.png) [@sinmoyyy](https://discuss.codechef.com/u/sinmoyyy)\
**Post date:** [May 11, 2020, 10:12am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/10 "2020-05-11T10:12:13Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![harshil21](https://discuss.codechef.com/user_avatar/discuss.codechef.com/harshil21/32/11855_2.png) [@harshil21](https://discuss.codechef.com/u/harshil21)\
**Post date:** [May 11, 2020, 10:17am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/11 "2020-05-11T10:17:14Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![rajasalok1996](https://discuss.codechef.com/user_avatar/discuss.codechef.com/rajasalok1996/32/8863_2.png) [@rajasalok1996](https://discuss.codechef.com/u/rajasalok1996)\
**Post date:** [May 11, 2020, 10:28am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/12 "2020-05-11T10:28:52Z")

</div>

I could not understand the example for subtask 1:

```auto
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 ?

---

<div class="post-metadata">

**Author:** ![anon82810326](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon82810326](https://discuss.codechef.com/u/anon82810326)\
**Post date:** [May 11, 2020, 10:30am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/13 "2020-05-11T10:30:28Z")

</div>

[https://www.codechef.com/viewsolution/32708857](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.

---

<div class="post-metadata">

**Author:** ![itachi\_13](https://discuss.codechef.com/user_avatar/discuss.codechef.com/itachi_13/32/15430_2.png) [@itachi\_13](https://discuss.codechef.com/u/itachi_13)\
**Post date:** [May 11, 2020, 10:33am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/14 "2020-05-11T10:33:25Z")

</div>

@harshil21 sir in the explanation of sub-task 2, you made an error while turning off R[4].  
It should be Z=01001 **0** 1. 🙂

---

<div class="post-metadata">

**Author:** ![harshil21](https://discuss.codechef.com/user_avatar/discuss.codechef.com/harshil21/32/11855_2.png) [@harshil21](https://discuss.codechef.com/u/harshil21)\
**Post date:** [May 11, 2020, 10:34am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/15 "2020-05-11T10:34:02Z")

</div>

Fixed typo.  
Thanks!

---

<div class="post-metadata">

**Author:** ![harshil21](https://discuss.codechef.com/user_avatar/discuss.codechef.com/harshil21/32/11855_2.png) [@harshil21](https://discuss.codechef.com/u/harshil21)\
**Post date:** [May 11, 2020, 10:39am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/17 "2020-05-11T10:39:46Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![shantanu689](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shantanu689/32/107374_2.png) [@shantanu689](https://discuss.codechef.com/u/shantanu689)\
**Post date:** [May 11, 2020, 10:41am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/18 "2020-05-11T10:41:13Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![arvinder7945](https://discuss.codechef.com/user_avatar/discuss.codechef.com/arvinder7945/32/3653_2.png) [@arvinder7945](https://discuss.codechef.com/u/arvinder7945)\
**Post date:** [May 11, 2020, 10:41am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/19 "2020-05-11T10:41:25Z")

</div>

**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;

```

}

---

<div class="post-metadata">

**Author:** ![doramon](https://discuss.codechef.com/user_avatar/discuss.codechef.com/doramon/32/24644_2.png) [@doramon](https://discuss.codechef.com/u/doramon)\
**Post date:** [May 11, 2020, 10:43am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/20 "2020-05-11T10:43:57Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![harshil21](https://discuss.codechef.com/user_avatar/discuss.codechef.com/harshil21/32/11855_2.png) [@harshil21](https://discuss.codechef.com/u/harshil21)\
**Post date:** [May 11, 2020, 10:44am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/21 "2020-05-11T10:44:06Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![nomansid08](https://discuss.codechef.com/user_avatar/discuss.codechef.com/nomansid08/32/3653_2.png) [@nomansid08](https://discuss.codechef.com/u/nomansid08)\
**Post date:** [May 11, 2020, 10:45am UTC](https://discuss.codechef.com/t/chandf-editorial/63302/22 "2020-05-11T10:45:23Z")

</div>

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

[Next page](https://discuss.codechef.com/t/chandf-editorial/63302.md?page=2)