XORIT - Editorial

Practice

Contest: Division 1

Contest: Division 2

Setter: Kasra Mazaheri

Tester: Arshia Soltani

Editorialist: Kasra Mazaheri

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 <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 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){
}
long long readIntLn(long long l,long long 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;
while(q--){
ll l,r;
//cin>>l>>r;
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.

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

(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.

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

19 Likes

i didnâ€™t under stand the even part approach can you elaborate

Iâ€™m Glad that you liked the problem!

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

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: CodeChef: Practical coding for everyone

1 Like