PROBLEM LINK:
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 :
- If X > R : Then it’s trivial that C(R,X) = 0.
- 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.
- 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) :
- If R is a supermask of X, add 1 to the result.
- Define R_i to be the i-th bit of R. X_i is defined similarly.
- 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
- 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.
- 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. 