XORIT - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Kasra Mazaheri

Tester: Arshia Soltani

Editorialist: Kasra Mazaheri

DIFFICULTY:

Easy

PREREQUISITES:

Observation, Bit Manipulation

PROBLEM:

Define XPR(N) to be a pair (A,B) such that :

  • 1 \le A \le B \le N

  • A \oplus B = N

  • The value of A is minimized.

If there is no valid pair for a number N, then XPR(N) = (-1,-1).

Define function F(N) to be the value of B in XPR(N). Function G(L,R) is then defined as \sum\limits_{i = L}^R {F(i)}. Calulate G(L, R) for Q queries.

QUICK EXPLANATION

  • A and B should not have any common bits set.
  • If N = 2^K for some 0 \le K, then XPR(N) = (-1,-1). Otherwise A = 2^{lb(N)} and B = N \oplus A where lb(N) is the lowest bit of N.
  • G(L,R) can be rewritten as G(1,R) - G(1,L-1).
  • We can find the opposite summation, the values of A, much easier.
  • Half of the numbers in [1, R] have lb(i) = 0. Half of the rest have lb(i) = 1. Half of the rest have lb(i) = 2 and so on.

EXPLANATION

It can be proven that A should have at least one common set bit with N. Otherwise B would be N | A and since 1 \le A, we’ll have N < B. It can be further proved that A and B will not have any common set bits since if they had a common bit, we could’ve set it to zero in both of them, the value of A \oplus B would still equal N but the value of A decreases which is contradictory with the fact of it being minimal. It’s then easy to see that if N = 2^K there can be no valid pair and so XPR(N) = (-1,-1). Otherwise we can always pick A =2^{lb(N)}. This will always be the optimal answer since A should have at least one common bit with N.

We can rewrite G(L, R) as G(1, R) - G(1, L - 1) in order to simplify our calculations.
For now we’ll consider F(N) = 0 for all N = 2^K. Define F'(N) as the value of A in XPR(N). As a result of above observations, F(N) = N - F'(N). We can then define G'(R) as \sum\limits_{i = 1}^R {F'(i)}. As a result, G(1,R) = \frac{R \times (R+1)}{2} - G'(R). Now we only need to calculate G'(R).

So for each number from 1 to R we have to sum up the value of their lowest bit. This can be handled in the following way :

  • There are \lceil{\frac{R}{2}}\rceil odd numbers that have their lb = 1.
  • The even numbers contribute G'(\lfloor{\frac{R}{2}}\rfloor) \times 2 in total. This is because they’re the same as the numbers in [1,\lfloor{\frac{R}{2}}\rfloor], only multiplied by two. So the value of their lowest bit is also multiplied by two.

We can finally subtract the number of numbers in [1,R] that are equal to some 2^K. This will automatically handle the cases where F(N) = -1.

TIME COMPLEXITY

The time complexity is O(log(N)) per test case.

SOLUTIONS:

Setter's Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll Get(ll n)
{
	ll tot = n * (n + 1) / 2;
	for (ll b = 1; n; n >>= 1, b <<= 1)
		tot -= (n + 1) / 2 * b, tot --;
	return (tot);
}
int main()
{
	int q;
	scanf("%d", &q);
	for (; q; q --)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		printf("%lld\n", Get(r) - Get(l - 1));
	}
	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
 
long long gcd(long long a, long long 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=1e4+500;
 
 
ll get(ll n){
	if(n==0){
		return 0;
	}
	ll ans=(n+1)/2;
	ans+=get(n/2)*2;
	return(ans);
}
ll bit(ll n){
	if(n==0){
		return 0;
	}
	return bit(n/2)+1;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll q;
	//cin>>q;
	q=readIntLn(1,1e5);
	while(q--){
		ll l,r;
		//cin>>l>>r;
		l=readIntSp(1,1e18);
		r=readIntLn(l,1e18);
		ll ans=(r-l+1)*(r+l)/2;
		ans-=get(r)-get(l-1);
		ans-=bit(r)-bit(l-1);
		cout<<ans<<endl;
	}
}

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

14 Likes

That sentence starting with “The even numbers contribute…” seems to be the key point of the editorial.
Can you explain it again? Somehow there must be a recursion to calculate the higher bits, and somehow we need to consider the upper bound r. How?

2 Likes

THAT WAS A NICE OBSERVATION TO COUNT THE REVERSE WAY LIKED THE EDITORIAL

1 Like

Was wandering with the same approach last night but you clarified my doubt very clearly .Hats off to you @kmaaszraa for nice question and then nice editorial.

can anybody explain why need to mutiply by 2 in case of even numbers .

Have a looka t these for easy solution
comment if you do not understand anything
my solution

So the value of their lowest bit is also multiplied by two in case of even numbers. I am unable to understand why we need to multiply by two ??

1 Like

Absolutely amazing the way the total number of numbers having a particular bit set was founded, i had to struggle a lot to find those numbers, nice question and editorial

Basically, you have to add,

(2 ^ i) * (count of numbers from (1 to N), whose LSB is in the ith bit.

and for every bit, you also have to add 1 to the previous result. ( because, for cases like :

1, 2, 4, 8, 16 …

The total generated value is the SUM of A only.

Let X = SUM of A only.

Now, subtract the X from SUM of [1.... N] .

Examples :
1
1 10

Lets us break it into the 4 bit representation :

0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0

Now,
LSB ( 0th bit ) = 5 * (2 ^ 0) = 5
LSB ( 1st bit ) = 3 * (2 ^ 1) = 6
LSB ( 2nd bit ) = 1 * (2 ^ 2) = 4
LSB ( 3rd bit ) = 1 * (2 ^ 3) = 8

Add them along with a ( + 1 ) in each step to deduct the powers of two.

Now, SUM OF A = 23 + 4 = 27.

SUM OF B = 55 - 27 = 28. :slight_smile:

12 Likes

I’m plain dumb, yesterday tried the question for over an hour and now unable to understand the “EXPLANATION” part of EDITORIAL.

1 Like

Am getting a TLE in my solution. I added the optimisation for odd values. Not sure how else i can optimise this further. Can someone help out?
https://www.codechef.com/viewsolution/28459823

18 Likes

i didn’t under stand the even part approach can you elaborate

I’m Glad that you liked the problem!

Glad you liked the problem! :slight_smile:

1 Like

Sure. Consider the binary representation of the numbers. All the even numbers have their first bit equal to zero. Now if we omit the first zero in them, they’ll actually be divided by 2. So if we omit the first zero in all the even numbers in the interval [1,R], we’ll get all the numbers in the interval [1,\lfloor\frac{R}{2}\rfloor]. It’s easy to see that lb(2N) = lb(N)+1 since we’re adding a zero to the beginning of N. So 2^{lb(2N)} = 2^{lb(N)+1} = 2^{lb(N)} \times 2. So we can find the sum of the lowest bits of all the even numbers in the interval [1,R] via the some of the lowest bit of the numbers in the interval [1, \lfloor\frac{R}{2}\rfloor]. As explained above, this value is equal to G'(\lfloor\frac{R}{2}\rfloor) \times 2.

1 Like

Very Helpful!

1 Like

see basically I think you understood that when N=3 then B =2 and A =1 that is right most set bit and also A+B=N as they will not share any bit . for the condition A,B>=1&&A,B<=N then observe carefully all the odd values have first that is 0th rightmost bit as set in the numbers then in rest N/2 numbers the second rightmost bit will be set and it goes on till n reaches 0 This was a part to observe for example take l=1 r=10
there are 10 numbers
1 2 3 4 5 6 7 8 9 10
count of numbers having 0th bit as set =5(1,3,5,7,9) (ceil value of 10/2)
count of numbers having 1st bit as set=3(2,6,10) (ceil value of 5/2)
remaining numbers 5-3=2
count of numbers having 2nd bit as set=1(4) (ceil value of 2/2)
remaining numbers 2-1=1;
count of numbers having 3rd bit as set=1(8) (ceil value of 1/2)
remaining numbers 0
and process ends.
and it g

Nice explanation!

Hey! Would you please make a tutorial for 2nd question of december cook off PRFYIT
Link: https://www.codechef.com/COOK113B/problems/PRFYIT

1 Like