DOR - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Kasra Mazaheri

Tester: Arshia

Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Understanding of OR operation, Bit manipulation (here and here).

PROBLEM:

Given two integer L and R, find the maximum value of A | B for L \leq A, B \leq R where | denotes OR operation.

QUICK EXPLANATION

  • Let us find the Most significant bit B position where bit L and R differ. Since L \leq R, L shall have this bit as 0 and R shall have this bit as 1.
  • The maximum OR value we can obtain, when written in binary form has all bits significant than the B-th bit same as both L and R, and all bits from B-th bit shall be set.

EXPLANATION

Writing operands in binary form, OR operation sets ith bit ON if either of the operands has ith bit ON.

So, our aim is to have maximum number of bits set.

Now, consider binary representations of both L and R, from the most significant bit (MSB) to least significant bit (LSB).

Suppose the first x bits are the same for both L and R. Then all possible A and B have the first x bits the same as L and R, since even if a single bit among these x bits change, the value shall move outside range [L, R] which is not allowed.

Consider example,

001100010
001100110

In the above example, the first six bits are the same for both L and R, so all A and B such that L \leq A, B \leq R holds have these as first six bits and their OR too have these as first six bits.

Lemma: We can obtain all bits set after first x bits where the first x bits of L and R are the same.

Now, ignoring the first x bits, we found a mismatch at the bit. At this point, we can construct A such that the mismatched bit is not set for A and all bits less significant than the current bit is set. Similarly, We can construct B such that mismatch bit is set for B and all subsequent bits are not set in B.

Their OR shall have all bits including mismatch bit set.

Why such A is valid
Since we set all bits ON after mismatch bit in A, A is the largest number with mismatch bit off, and thus, is guaranteed to lie between range [L, R] as L has mismatch bit unset while R has mismatch bit set.

Why such B is valid
Since we set all bits OFF after mismatch bit in B, B is the smallest number with mismatch bit ON, and thus, is guaranteed to lie between range [L, R] as L has mismatch bit unset while R has mismatch bit set.

Applying this logic to our example, we have A = 001100011 and B = 001100100 and their OR is 001100111 which is maximum possible.

Hence, all we need to do is to find the Most significant mismatch bit which can be done by iterating from MST to LSB and comparing bits. Tutorials on Bit manipulation can be referred to in prerequisites.

TIME COMPLEXITY

Time complexity is O(log_2(R)) per test case.

SOLUTIONS:

Setter's Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	int q;
	scanf("%d", &q);
	for (; q; q --)
	{
	    ll l, r;
	    scanf("%lld%lld", &l, &r);
	    ll Mx = 0, i = 60;
	    for (; ~ i; i --, Mx |= (l & (1LL << i)))
	        if ((l ^ r) >> i & 1LL)
	            break;
	    Mx |= (1LL << (i + 1)) - 1;
	    printf("%lld\n", Mx);
	}
	return 0;
}
Tester's Solution
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}

#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>

using namespace :: std;


//=======================================================================//
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
	    char g=getchar();
	    if(g=='-'){
	        assert(fi==-1);
	        is_neg=true;
	        continue;
	    }
	    if('0'<=g && g<='9'){
	        x*=10;
	        x+=g-'0';
	        if(cnt==0){
	            fi=g-'0';
	        }
	        cnt++;
	        assert(fi!=0 || cnt==1);
	        assert(fi!=0 || is_neg==false);

	        assert(!(cnt>19 || ( cnt==19 && fi>1) ));
	    } else if(g==endd){
	        assert(cnt>0);
	        if(is_neg){
	            x= -x;
	        }
	        assert(l<=x && x<=r);
	        return x;
	    } else {
	        assert(false);
	    }
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
	    char g=getchar();
	    assert(g!=-1);
	    if(g==endd){
	        break;
	    }
	    cnt++;
	    ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
//=======================================================================//



const ll maxn=1e5+500;
const ll inf=1e9+800;
const ll mod=1e9+7;

ll solve(ll l,ll r,ll k){
	if(k==1)return r;
	ll ans=0;
	for(ll i=0;i<62;i++){
		if(!(((l>>i)&1)==0 && ((r>>i)&1)==0 && (r-l)<(1LL<<i))){
			ans+=(1LL<<i);
		}
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll t;
	t=readIntLn(1,(ll)1e5);
	for(ll i=0;i<t;i++){
		ll l,r;
		l=readIntSp(0,(ll)1e18);
		r=readIntLn(l,(ll)1e18);
		cout<<solve(l,r,2)<<endl;
	}
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class DOR{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    long l = nl(), r = nl();
	    long ans = 0;
	    boolean f = false;
	    for(int b = 60; b >= 0; b--){
	        if(((l>>b)&1) != ((r>>b)&1))f = true;
	        if(f)ans |= 1l<<b;
	        else if(((l>>b)&1)==1)ans |= 1l<<b;
	    }
	    pn(ans);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new DOR().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

20 Likes

Bonus : try other two variants AND , XOR :blush:

4 Likes

Such a beautiful editorial. Thanks.

8 Likes

For AND, Will ‘r’ be answer in every case ?

2 Likes
4 Likes
3 Likes

In DOR problem, L<=A,B<=B. That means we can choose A and B as same . So will it not be better if we choose largest value twice , R&R= R.

Any reason why I’m getting NZEC for this?
https://www.codechef.com/viewsolution/27506997

I’m pretty new CodeChef but this solution worked flawlessly on my machine. NZEC implies runtime error, right? But since it ran on my machine I can’t see the reason for NZEC

https://www.codechef.com/viewsolution/27511785
Why i am getting WA? thanks !

I used the same approach as in editorial I think so. But its getting WA. Can anyone please help me out with this.
My_solution

1 Like

I got the solution correct just by replacing default pow function (which is I don’t know why malfunctioning ) with my own power-function. Thank You :slightly_smiling_face:

3 Likes

Those who are getting WA, one of reason can be left-shift or right-shift operations if you are using any.
For example: If you want 63 consecutive ones i.e. 2^63 - 1. You must upcast one of operands to (unsigned) long long like this (1ULL<<63) - 1;
I solved it much earlier but got two times WA just because this silly mistake.
And also use proper brackets around these operators.
:grinning:

2 Likes

No we can’t do this.
For example take L = 1 and R = 100
now if we take R&R = 100, but the maximum possible OR value is 127 which occurs for many pairs like A=63 B=64, A=95 B=100 and so on.
Try to write a normal brute force for the question and see the pattern and analyze it, hopefully you will get the final idea.
Happy coding!

https://www.codechef.com/viewsolution/27510835
dont able to recognize why i am getting tle for this ?

hi, your code isn’t working when L==R
Try 15 15 as input

Same happened with me bro. I’m furious now, I didn’t know this during the contest. Thanks btw.

can anyone suggest why this code getting wrong answer??
#include
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int countBits(ll number)
{
return (int)log2(number)+1;
}
int main() {
int t;cin>>t;
while(t–){
ll L,R;cin>>L>>R;
ll n=L^R;
int a=countBits(n);
for(int i=0;i<a;i++)
R=(R|(1 << i));
cout<<R<<endl;

}
}

@taran_1407
Problem Setter, tester. Plz do use of comment in your code. So that everyone can get the logic of your code.

7 Likes

power function is the problem here.As it returns a double it doesn’t always guarantee a correct output in case of integers. Use (lli)(pow(x,y) + 0.5) in this case.

2 Likes

Thanks for the tip bro :smile:.