DAND - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Kasra Mazaheri

Tester: Arshia Soltani

Editorialist: Kasra Mazaheri

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Bit Manipulation, Observation

PROBLEM:

You are given three integers L, R and K. You have to find the maximum bitwise-and value of exactly K distinct integers in the interval [L,R].

QUICK EXPLANATION

  • We can build the answer bit by bit, from the highest bit to the lowest.
  • At each iteration we need to check if there are at least K numbers in the interval [L,R] that are a supermask of our current answer. Recall that A is a supermask of B if and only if B is a submask of A.
  • We can solve the problem independently for [0,R] and [0,L-1] and combine these results to get the number of such supermasks in [L,R].
  • We then define C(R, X) to be the number of integers in the interval [0, R] that are a supermask of X. Also define hb(R) to be the index of the highest set bit in the binary representation of R and popcount(R) to be the number of set bits in R. Then in order to calculate C(R,X) there are a few cases to consider :
    – If X > R then C(R,X)=0
    – If X < 2^{hb(R)} then C(R,X) = C(R-2^{hb(R)},X) + 2^{hb(R) - popcount(X)}
    – Otherwise C(R,X) = C(R-2^{hb(R)}, X-2^{hb(R)})
  • Thus we can calculate the value of C(R,K) for a given R and X in O(log(R)). However this is too slow. We can improve the complexity by realizing that the cases of C(R,answer) barely changes as we change only one bit in answer every time. So we can actually keep track of C(R,answer) and C(L-1,answer) as we create answer bit by bit. The required changes can then be implemented in O(1) giving us an acceptable solution.

EXPLANATION

We will build the answer bit by bit, from the highest bit to the lowest. So at each step we’re interested to know if there are at least K numbers in the interval [L,R] that are a supermask of X where X is the current answer we have made (using higher bits). It’s easy to see that if there are at least K such numbers, then the answer is at least X. Define C'(L,R,X) to be the number of such integers in [L,R] that are a supermask of X. Then we’ll have C'(L,R,X) = C'(0,R,X) - C'(0,L-1,X). So we can calculate these two values independently. So for now on we focus on calculating the value of C(R,X) = C'(0,R,X). We can calculate this value recursively by solving few cases :

  1. If X > R : Then it’s trivial that C(R,X) = 0.
  2. If X < 2^{hb(R)} : We can divide the numbers in [0,R] into [0,2^{hb(R)}) and [2^{hb(R)},R]. For the second group of numbers the answer is C(R-2^{hb(R)},X) as the hb(R)-th bit doesn’t matter. For the first group however, we can calculate the answer right away. Those bits that are set in X should also be set in supermasks of X, but all the other bits can be either 0 or 1. We have hb(R) bits in total, popcount(X) of which should be set to 1. Thus we can have 2^{hb(R)-popcount(X)} different numbers that are a supermask of X in the first group.
  3. Otherwise : We know that K has the hb(R)-th bit set and so has every number in [2^{hb(R)},R]. So for every number A \in [0,R-2^{hb(R)}] such that A is a supermask of X-2^{hb(R)}, we can add 2^{hb(R)} to it and it will be a supermask of X. It’s easy to see that the opposite case is just the same. So we actually have C(R,X) = C(R-2^{hb(R)},X-2^{hb(R)}).

We can see that at the first case the answer is calculated right away. In the other two cases, R is always reduced by at least half, so there can only be O(log(R)) iterations in total. We now have a working O(log(R)^2) solution. We can do better though. Consider the following algorithm that calculates the value of C(R,X) :

  1. If R is a supermask of X, add 1 to the result.
  2. Define R_i to be the i-th bit of R. X_i is defined similarly.
  3. Loop over i from L = 59 to 0. We assume at the i-th iteration that the values of R_j and X_j for all j < i are set to 0. We will discover them at their own iteration
  4. Case 1 : If X \le R and we encounter R_i=1 and X_i=0, we add 2^i to the answer, since we assume the first i bits of X to be 0 as we have not discovered them yet. We then set X_i=1 as all the numbers that didn’t have the i-th bit have already been counted. So we should only count those that have the i-th bit set.
  5. Case 2 : If we encounter X_i=1, then all those 2^j we have added in case 1 should be divided by 2 since we assumed X_i=0 back then (and thus considered two options for it) whereas now we know X_i=1 and all those numbers should have had the i-th bit set (only one option). Since exactly half of them had this bit, we can divide the result we calculated by two. Additionally if R_i=0, we know that from now on X will always be larger than R.

We can see that this algorithm indeed does the same thing as the recursive one. The only difference between them is that this one assumes the undiscovered bits of X to be 0 at every iteration. Recall that we are building the answer bit by bit from the highest to the lowest. So when we’re checking if we can have the i-th bit of our answer set, all the lower bits j < i are set to 0. The second algorithm already assumes this fact, so we can actually stop it at the i-th iteration. Since there wouldn’t be any case 2 from now on, we only have to handle the first case when X \le R. Having in mind that there wouldn’t be any more set bits in X, we can safely say that case 1 will add 2^j for every j < i that R_j=1 if X \le R and 0 otherwise. We can keep track of these values both for R and L-1 as we build our answer and update it accordingly. All the required changes are done in O(1) so we achieve an O(log(R)) solution in total. Refer to the implementations for more details.

TIME COMPLEXITY

The time complexity is O(Q \times log(R)).

SOLUTIONS:

Setter's Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
#define Bit(a, b) ((a) >> (b) & 1LL)
using namespace std;
typedef long long ll;
inline ll Solve(ll l, ll r, ll k)
{
	ll MX = 0, Cnt = 0;
	ll pr = 0, pl = 0;
	bool tr = 1, tl = 1;
	for (int i = 59; ~ i; i --)
	{
		Cnt = (pr >> 1) - (pl >> 1);
		if (tr & Bit(r, i))
			Cnt += (r & ((1LL << i) - 1)) + 1;
		if (tl & Bit(l, i))
			Cnt -= (l & ((1LL << i) - 1)) + 1;
		if (Cnt >= k)
		{
			MX |= 1LL << i;
			pl >>= 1; tl &= Bit(l, i);
			pr >>= 1; tr &= Bit(r, i);
		}
		else
		{
			pl |= (tl & Bit(l, i)) << i;
			pr |= (tr & Bit(r, i)) << i;
		}
	}
	return (MX);
}
int main()
{
	int q;
	scanf("%d", &q);
	for (; q; q --)
	{
		ll l, r, k;
		scanf("%lld%lld%lld", &l, &r, &k);
		printf("%lld\n", Solve(max(l - 1, 0LL), r, k));
	}
	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,' ');
}
//=======================================================================//
 
 
 
struct M{
	ll base;
	ll x;
	ll Sposht=0;
	ll Sjelo=0;
	ll maj;
 
	inline ll get(int i){
		if(i<maj || ((x>>i)&1) || (!((base>>i)&1)))return 0;
		return (1LL<<i);
	}
	void bild(){
		Sjelo=base;
	}
	ll check(int ind){
		if(!((base>>ind)&1)){
			return ((Sposht+get(ind+1))>>1);
		}else{
			return Sjelo-get(ind)+((Sposht+get(ind+1))>>1);
		}
	}
	void add(bool b,int ind){
		Sposht+=get(ind+1);
		Sjelo-=get(ind);
		if(b){
			Sposht>>=1;
			x+=(1LL<<ind);
			if(!((base>>ind)&1)){
				Sjelo=0;
				maj=ind;
			}
		}
	}
};
M sefr;
 
ll solve(ll l,ll r,ll k){
	M a,b;
	a=sefr;
	b=sefr;
 
	a.base=r+1;
	b.base=l;
	
	a.bild();
	b.bild();
	ll ans=0;
	for(ll i=61;i>=0;i--){
		ans+=(1LL<<i);
		if(a.check(i)-b.check(i)<k){
			ans^=(1LL<<i);
			a.add(0,i);
			b.add(0,i);
		}else{
			a.add(1,i);
			b.add(1,i);
		}
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);	
	sefr.x=0;
	sefr.maj=0;
 
	ll q;
	//cin>>q;
	q=readIntLn(1,1e6);
	cout<<endl;
	while(q--){
		ll l,r,k;
		//cin>>l>>r>>k;
		l=readIntSp(0,1e18);
		r=readIntSp(l,1e18);
		k=readIntLn(1,r-l+1);
		cout<<solve(l,r,k)<<endl;
	}
}

Feel free to share your approach. As usual, suggestions are warmly welcomed. :slight_smile:

https://www.codechef.com/viewsolution/28459896
Can someone help me understand why this solution is getting a tle?

Why isnt the following logic working:

(starting from msb)

  1. for index i(numbered from left) and current ans=mask, find count of numbers(ones) that are in the range and of the form (mask|(1<<i))
    eg, for range=[8,11],mask=1000 and i=1 we can get ones = 2 [10(1010) and 11(1011)]

  2. if ones < k and (range length - ones)<k then we have already got the answer(mask)

  3. if ones>=k then update l and mask [mask= mask | (1<<i) ]

  4. else update r

Please have a look at my solution.

It gives correct solutions for sample test case

1 Like

I am sorry, but please can you please submit code explaining your optimised approach. I am trying to understand it for 2 days.

1 Like

If you just want a testcase where it fails, consider:

1
63 77 7

(the answer should be 65, according to the Tester’s code).

1 Like

Thanks for the reminder. I could have generated a failing test case on my own.
Also I got where I am mistaken. My logic is wrong.

1 Like

I don’t understand your question. I have already put my code in the editorial. What part of the editorial don’t you understand?

Can you plz… explain/comment your code that is there in the editorial. I am finding it hard to connect it with the explanation

Can you comment your code as per the editorial ?

// In The Name Of The Queen
#include <bits/stdc++.h>
#define Bit(a, b) ((a) >> (b) & 1LL)
using namespace std;
typedef long long ll;
inline ll Solve(ll l, ll r, ll k)
{
	ll MX = 0;	//target number we are constructing
	ll cnt = 0;
	ll pr = 0, pl = 0;
	bool tr = 1, tl = 1;
	for (int i = 10; ~ i; i --)
	{
		cnt = (pr >> 1) - (pl >> 1);
		if (tr & Bit(r, i)){
			// number of numbers between 0-r that have the ith bit set
			// (this is where we add 2^j for each j<i where Rj = 1)
			// additional + 1 for when all bits from 0 to i-1 are 0; 
			cnt += (r & ((1LL << i) - 1)) + 1;
		}
		if (tl & Bit(l, i)){
			//similar to above
			cnt -= (l & ((1LL << i) - 1)) + 1;
		}
		if (cnt >= k){
			// if cnt >= k then we can set this bit in ans
			MX |= 1LL << i;
			pl >>= 1; tl &= Bit(l, i);
			pr >>= 1; tr &= Bit(r, i);
		}else{
			//if cnt < k then this bit of ans is 0;
			//out of numbers [0, 2^i-1] with ith bit not set, 
			//exactly half of them will have a subsequent bit j set (that will form part of MX)
			//furthermore exactly half of these half will have the next subsequent bit in the MX set 
			//(which is why we divide pr and pl by 2 in the if case)
			pl |= (tl & Bit(l, i)) << i;
			pr |= (tr & Bit(r, i)) << i;
		}
	}
	return (MX);
}
int main()
{
	int q;
	scanf("%d", &q);
	for (; q; q --)
	{
		ll l, r, k;
		scanf("%lld%lld%lld", &l, &r, &k);
		printf("%lld\n", Solve(max(l - 1, 0LL), r, k));
	}
	return 0;
}
1 Like

Thanks for your effort , can you kindly explain the essence of pr or pl variable?