Editorial -RGAND

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Yusuf Kharodawala

Tester: Radoslav Dimitrov

Editorialist: Raja Vardhan Reddy

DIFFICULTY:

Easy

PREREQUISITES:

Bit operations.

PROBLEM:

You are given positive integers L and R. You have to find the sum

S=∑_{i=L}^{i<=R}(L∧(L+1)∧…∧i),

where denotes the bitwise AND operation. Since the sum could be large, compute it modulo 10^9+7.

EXPLANATION

Let X_i=L∧(L+1)∧...∧i), for i>=L. Here denotes bitwise AND operation.

If we consider a particular bit, say j^{th} bit, in the binary representation of all X_i. Let the number of terms in which it is 1 be c_j.
Then,

\sum_{i=L}^{i<=R} X_i = \sum_{j=0}^{j<60}c_j*2^j.

How to compute c_j ?

Claim : If we consider any particular bit in the binary representation of Xis, it will be 1 in some number of consecutive terms from the beginning of the sequence , and then 0 in remaining terms of the sequence".

Proof: Let us consider jth bit.

  • If it is 1, in all the terms, the claim is true.
  • If it becomes 0 in some term, let the first term at which it becomes 0 be X_K. Now, any further term in the sequence X_T can be written as X_T=X_K∧(k+1)...∧T, and since j^{th} bit is 0 in X_K, it is 0 in X_T also. Hence, the claim is true!

The first term in which the j^{th} bit becomes 0 is X_K where K is the smallest integer >=L with j^{th} bit is 0.

  • K=L, if j^{th} bit is 0 in L.
  • K=L+(2^j-(L\& (2^j-1))) , if j^{th} bit is 1 in L.
    Let’s look at how this comes.
    For exapmle, let L=26, in binary form L=“11010” and let’s consider 3rd(0-based) bit i,e 11010 (highlighted bit).
    L+1 = 27 = “11011”
    L+2 = 28 = “11100”.
    L+3 = 29 = “11101”.
    L+4 = 30 = “11110”.
    L+5 = 31 = “11111”.
    L+6 = 32 =“100000”.
    We see that , it remains 1 until all bits smaller than j are all 1.
    Let P be the number where all bits smaller than j are all 1, then K=P+1.(from the way we defined K).
    If we observe, the bits which are >=j i.e, j^{th} bit, j+1^{th} bit,…, they are same in L and P.
    Therefore, P and L differ only in first j bits i.e (0^{th} bit, 1^{st} bit, …(j-1)^{th} bit)
    Hence, P-L = (value of first j bits in P) - (value of first j bits in L).
    Value of first j bits in P : (2^j-1) , because all j bits are 1’s.
    Value of first j bits in L : (L\&(2^j-1)), because (2^j-1) in binary representation is simply, “111…11” ( j 1’s ) , (L\&(2^j-1)) gives the value of first j bits of L, because any bit beyond j is 0 in (2^j-1).
    Hence,
    P-L = (2^j-1) - (L\&(2^j-1)).
    =>P=L+(2^j-1) - (L\&(2^j-1)).
    and,
    K=P+1
    =>K=L+(2^j-1) - (L\&(2^j-1))+1.
    =>K=L +2^j - (L\&(2^j-1)).

Therefore, c_j=min(K-L,R-L+1).

TIME COMPLEXITY:

Calculating c_j : O(1) per j, Total time : O(log R) for all log R bits.
Calculating \sum_{i=L}^{i<=R} X_i : O(log R).
Total Time complexity : O(log R) per test case.

SOLUTIONS:

Setter's Solution
import java.util.*;
import java.io.*;
class Solution{
 
    final static long mod = (long)1e9+7;
 
    public static void main(String[] args){ 
        
            FastReader s = new FastReader(System.in);
            PrintWriter w = new PrintWriter(System.out);
 
            int t = s.nextInt();
 
            while(t-->0){
                long L = s.nextLong(), R = s.nextLong(), ans = 0, cur = L, pow = 1;
                for(int i = 0; cur > 0; i++, cur >>= 1, pow <<= 1, pow %= mod) {
                    if((cur&1) == 0) continue;
                    long temp = cur + 1;        //This operation sets the first unset bit after i
                    temp <<= i;                 //Now we need to left shift temp by i, since our current cur is right shifted i times.
                    ans += pow * ((Math.min(R, temp - 1) - L + 1)%mod);
                    ans %= mod;
                }
                w.print(ans + "\n");
            }
 
            w.close();
        
    }
 
    static class FastReader { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader(InputStream i) { br = new BufferedReader(new InputStreamReader(i)); } 
  
        String next() { 
            while (st == null || !st.hasMoreElements()) { 
                try{ 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() { return Integer.parseInt(next()); }
 
        long nextLong() { return Long.parseLong(next()); }
 
    } 
}  
Tester's Solution
#include <bits/stdc++.h>
#define endl '\n'
 
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
 
using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
const int mod = (int)1e9 + 7;
 
int64_t L, R;
 
void read() {
    cin >> L >> R;
}
 
void solve() {
    int64_t answer = 0, mask = 0;
    for(int64_t i = 1; i <= R; i <<= 1ll) {
        if(L & i) {
            int64_t mult_by = i - (L & mask);
            chkmin(mult_by, R - L + 1);
 
            mult_by %= mod;
            answer = (answer + (i % mod) * 1ll * mult_by) % mod;
        }
 
        mask |= i;
    }
 
    cout << answer << endl;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int T;
    cin >> T;
    while(T--) {
        read();
        solve();
    }
 
    return 0;
}
Editorialist's Solution
//raja1999

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;


//std::ios::sync_with_stdio(false);

main(){
    std::ios::sync_with_stdio(false); cin.tie(NULL);
    int t,t1;
    cin>>t;
    t1=t;
    while(t--){
        int l,r,act=0,req=0,val,ans=0,i;
        cin>>l>>r;
        for(i=0;i<60;i++){
            val=min(r-l+1,req-act+1);
            val%=mod;
            if(l&(1LL<<i)){
                ans+=(val*((1LL<<i)%mod))%mod;
                ans%=mod;
                act+=(1LL<<i);
            }
            req+=(1LL<<i);
        }
        cout<<ans<<endl;
    }
    return 0;
} 

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

7 Likes

Not able to understand editorial.
Can anyone tell in simple language

20 Likes

I am not able to understand the given editorial.I am new to programming.Can anyone please help me out?

8 Likes

Please make the editorial more simple to understand .

10 Likes

I might have thought in different way but my hand picked test cases are running perfectly fine. Please help. @kharyusuf
My Code: -

#include “iostream”
#include “math.h”
#define lli long long int
#define fo(i, a, b) for(int i = a; i < b; i++)
using namespace std;

int main() {
lli MOD = 1000000007;
lli t;
cin >> t;
while(t–) {
lli l, r;
cin >> l >> r;
int k = log2(l);
lli LeftNumber = (lli)pow(2, k);
lli RightNumber = (lli)pow(2, k+1);
lli cnt;// = 0;
if(LeftNumber==l) {
if(r < RightNumber) cnt = r - l + 1;
else cnt = RightNumber - l;
cout << ((cnt%MOD)(l%MOD))%MOD << endl;
} else {
if(r < RightNumber) cnt = r - l;
else cnt = RightNumber - l - 1;
cout << (((cnt%MOD)
(LeftNumber%MOD))%MOD + l%MOD)%MOD << endl;
}
}
}

1 Like

How this formula came?

1 Like

@vijju123 bro, please share your editorial for this question which can be understandable by everyone.

13 Likes

Difficulty: EASY? :sweat_smile:

11 Likes

ofc xD

1 Like

I am unable to understand this formula.

Look
Say it is 11010 to 100000
Look at the second 1
This one 1(1)010
J=3.
11010
11011
11100
11101
11110
11111
100000
It stays a one until the numbers after it all become a one.
The number after it is 2 initially and 7 finally.
So it is added 7-2+1 times.
=8-2.
The 2 is just
L&(2^j -1)
And 8 is just 2^j
So it becomes
2^j -L&(2^j -1)

9 Likes

can anyone spot where i’m going wrong it will be a great help
link to my solution-https://www.codechef.com/viewsolution/29087154

Can anyone tell me if my approach is correct or not? If its not correct, then in which case it will fail.
Basically, I am trying to calculate the next power of 2 from the given l. Because the answer will be decided by the smallest power of 2 less than or equal to l (say x) and the next power of 2. We have to add (r-l) number of times x where r is the minimum of 2x and r(originally given). for the cases such as {10,11,12,13} since l has first rightmost set bit at position 2(1 based indexing), so we have to add 2l to the ans since 10 + 10^11 will both give 10 as answer, and then repeat the above process for the remaining numbers till next power of 2.
Link to my solution. https://ideone.com/yq4tlM
Any feedback is appreciated.

hey my approch is similar to yours
waiting for any feedback to verify :grin::grin:

Well, I initially had the same thought but when you consider n i.e. 10**18 and also the number of test cases i.e. 10**5, the above method will probably time out.

hey…can anyone help me what’s wrong with my code
I used slightly different approch instead of bit wise addition , I started to
add L whole as many time it occure as sum by considering its least significant 1, and then
next L correspond to next least significant 1 and so on. it
https://www.codechef.com/viewsolution/29092520

it would be helpful if anyone can suggest whats wrong with it

As we know, as the series progresses, bits will always be unset since we are doing BITWISE AND.

The most number of bits in L are 60.

So, using zero-based indexing, lets iterate i from 0-59.

if the ith bit of L is set, we find the smallest number > L whose ith bit is NOT set. Let this number be X.
Then we simply add (min(R, X-1)-L+1)*(2^i) to our answer.

Finding X is also straight forward. We set the first unset bit >i in L and unset rest of the bits. This will always be the smallest number >L whose ith bit is unset.

5 Likes

Thanks

Read above comment …

I am currently busy finishing Jan20 editorials which got delayed due to my personal life issues. But I am flattered by your and community’s love :slight_smile:

11 Likes