Problem Link:
Contest
Practice
Author: Chirantan Muliya
Tester: Tushar Sain
Editorialist: Chirantan Muliya
Difficulty
MEDIUM
PREREQUISITES
Binary numbering system, Bit manipulation, PnC
EXPLANATION & SOLUTION:
Take log_2(10^3)=10,log_2(10^9)=30,log_2(10^{18})=60.
(1) Subtask1:
Brute force approach check for all numbers between a to b if number of 0 bits are 3 or not…
Time Complexity: O( (B-A) * 10 ) = O(10^4)
Space complexity: O(1)
(2) Subtask2:
Count number of bits in A and B, Check all possible combinations with 3 zeroes for bits_a and bits_b and increase count for those numbers which are in range [A,B].
Time Complexity: O( (bits_a^3+bits_b^3) * T ) = O( (30)^3 * 100) = O ( 10^6)
Space complexity: O(1)
(3) Subtask3:
Hint: Precomputation for all bits (0…61) in Subtask2 will remove T factor.
Time Complexity: O( bits_a^3 + bits_b^3 ) = O( (60)^3) = O(10^5)
Space complexity: O(10^5)
Setter's Solution :
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define loopf(i, a, b) for (ll i = a; i < b; i++)
#define loopb(i, a, b) for (ll i = a; i > b; i--)
#define pb push_back
#define fast \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);
#define ff first
#define ss second
#define vc vector
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mapii map<int, int>
#define mapll map<ll, ll>
#define all(x) x.begin(), x.end()
#define endl "\n"
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define read(a) \
for (auto &i : a) \
cin >> i
#define print(a) \
for (auto i : a) \
cout << i << " "
#define ub(v, i) upper_bound(all(v), i)
#define lb(v, i) lower_bound(all(v), i)
const ll M = 1e9 + 7;
const ll N = 100001;
vc<ll> v, pow2;
void solve()
{
ll l, r;
cin >> l >> r;
cout << ub(v, r) - lb(v, l) << endl;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
fast
int t = 0;
cin >> t;
pow2.resize(65); // for safe side taking 65.. we can take 61 also
pow2[0] = 1;
ll xx = 2;
loopf(i, 1, 65) pow2[i] = xx, xx <<= 1; // generating 2^i
loopf(i, 3, 64)
{
ll curr = pow2[i + 1] - 1; // generating 2^(i+1)-1 which will be 111...1 i+1 times
loopf(j, 0, i) loopf(k, 0, j) loopf(l, 0, k) // taking all possible combinations for three 0 bits except for MSB
v.pb(curr - pow2[j] - pow2[k] - pow2[l]);
// subtracting pow2[j] will make jth bit 0 and so on
// e.g. for curr=1111, we will subtract 0100 0010 0001 which will give us 1000
}
sort(all(v));
int c = 1;
while (c <= t)
{
solve(), c++;
}
}
Please comment below for any doubts or if you have alternative solution(s)
Here is my solution without precomputing using simple combinatorics:)
(I realised i did a very small looking huge mistake in my code XD so i had to delete my previous post )
To be honest , i really liked your solution of precomputing , when i first saw this problem the same idea came to my mind , but i didn’t realised that the numbers will not be many and we can do precomputation . Thanks a lot , learnt something new today 
#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
#define all(v) v.begin(),v.end()
#define vi vector <int>
#define sim template<typename T
sim > istream &operator>>(istream &is , vector<T> &container){
for(auto &item : container ){
is >> item;
}
return is;
}
sim > ostream &operator<<(ostream &os , vector<T> &container){
auto itr = container.begin();
for(auto item : container){
os << item;
if(++itr != container.end()) os << ' ';
}
return os;
}
int combo(int n , int r){
if(min({n , r , n - r}) < 0) return 0;
if(r == 0) return 1;
if(r == 1){
return n;
}
if(r == 2){
return (n * (n - 1))/2;
}
if(r == 3) return (n * (n - 1) * (n - 2))/6;
}
void SOLVE(){
auto binary = [](int x) -> string{
string res = "";
for( ; x > 0; x >>= 1) res.push_back(x % 2 + '0');
reverse(all(res));
return res;
};
auto isIt = [&binary](int x) -> int{
int count = log2(x) - __builtin_popcount(x) ;
return count == 3;
};
auto right = [&binary](int L) -> int{
string l = binary(L);
int d = l.size();
int req = 3;
int ans = ((d - __builtin_popcount(L)) == req);
for(int i = 0; i < d; i++){
if(l[i] == '1') continue;
ans += combo(d - i - 1 , req);
req--;
}
return ans;
};
auto left = [&binary](int R) -> int{
string r = binary(R);
int d = r.size();
int req = 3;
int ans = ((d - __builtin_popcount(R)) == req);
for(int i = 1; i < d; i++){
if(r[i] == '0'){
req--;
continue;
}
ans += combo(d - i - 1 , req - 1);
}
return ans;
};
int L , R; cin >> L >> R;
string l = binary(L) , r = binary(R);
int ans = 0;
if(l.size() == r.size()){
int digits = l.size();
ans = combo(digits - 1 , 3);
if(L - 1 >= 1ll << (digits - 1)) ans -= left(L - 1);
if(R + 1 <= (1ll << digits) - 1) ans -= right(R + 1);
}
else{
ans = right(L) + left(R);
for(int i = l.size() + 1; i <= r.size() - 1; i++){
ans += combo(i - 1 , 3);
}
}
cout << ans << "\n";
}
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
int t = 1;cin >> t;
while(t--){
SOLVE();
}
}
Though for larger number of zeroes , we couldn’t possibly write multiples loops for precomputing and the numbers can increase too , so we then have to calculate the answer using combinatorics with respect to some mod
@sain2801 Bro , actually i am not able to submit my code for practice tab it is showing me some error , can u please confirm when will the problem be available for practice . Though i am getting correct outputs in stress testing , but still it would be great if i can confirm whether it is fully correct or not.
where can i submit the solution after the contest has ended ? it says access denied
Hey!! @prakhar_jn check now you can submit it in practice link here
Hey @letsdosmtgdiff I looked your code I think it is correct only though you can check once submitting here. You did a great observation there!! Thank you for letting me know another approach.
1 Like
Thanks bro, i checked and it got accepted(CodeChef: Practical coding for everyone)