PROBLEM LINK:
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. 
