TED24 - EDITORIAL

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 :slight_smile:


#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(Solution: 56271109 | CodeChef)