Editorial -RGAND

editorial
24

Why does the first problem always be a Bit Manipulation ? :confused:

3 Likes
25

can anyone help me with this part?
Thanks

26

Is it just me or anyone felt this question was difficult than CFINASUM?

1 Like
27

Just use pen and paper to check the number of steps required to reach from right to left for each ‘1’ bit of the number in binary format, i am sure you(everyone) will understand the following formula upon trying with pen and paper. Because I wasn’t getting the logic so i did use pen and paper to check the mechanism how many steps required to reach each ‘1’ bit in binary format from left to right.

29

I have added the explanation for it in the editorial. Hope its clear now.

2 Likes
30

Check for this test case:
1
14 15

31

check for this test case bro:
1
14 15

32

got my mistake. Thanks @anon58686675

1 Like
33

It’s indeed an easy question.

34

@kharyusuf
I think I have done the same but still my solution is getting wrong verdict -
please have a look

Link - t4W8x2 - Online C++0x Compiler & Debugging Tool - Ideone.com
OR
code:
#include
#include<math.h>
using namespace std;

int MOD = 1000000007L;
typedef long long ll;
ll power(ll a, ll n){ // I've made a recurrence relation here -> a^n = n%2==0 ? a^(n/2) * a^(n/2) : a^(n/2) * a^(n/2) * a  ;
	if(n==1)return a;
	ll x = power(a,n/2) * power(a, n/2);
	if(n%2==1) x*=a;
	return x;
}
int main() {
	
	int t=0;
	scanf("%d",&t);
	while(t--){
		long long l = 0, r=0, ans=0, id=0, n =0;
		scanf("%lld %lld", &l, &r);
		n=l;
		while(n!=0){
			n/=2;
			id++;
		}
		long long x = power(2,id);
		x--;
		if(r>x){
			x = x-l+1;
		}
		else x = r-l+1;
		
		ans = (x%MOD * l%MOD)%MOD;
		printf("%lld\n", ans);
		
	}
	return 0;
}
35

Nice !! Editorialist’s code is good!!

36

Can someone pls help me, I did this am getting tle, not WA.
Here is the link to my solution: CodeChef: Practical coding for everyone

37

Wow…Awesome concept…
Be focused during reading editorial
thanks a lot.

38

were you able to code this approach without runtime error ? i was doing the same but got WA ,if you have please share the code

39

Can Someone please explain what is happening in line 21 in this code:
https://www.codechef.com/viewsolution/29056109

42

Xd

43

Whats wrong in this solution??

#include<bits/stdc++.h>
using namespace std;

const int M = 1e9+7;
int L,R;

void solve(){
cin>>L>>R;
int result = L;
int sum = 0;
for( int i = 0 ; i<R-L+1 ; i++){
if(i == 0){
sum += result%M;
}

	if(i>0){
     result = result&(L+i);
     sum+= result%M;
	}
}

cout<<sum<<'\n';

}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int T;
cin>>T;
while(T–) solve();

return 0;

}

44

Can anybody tell me the test case where my code show wrong answer.
It is showing wrong answer , please help
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
int main()
{

     lli t;
     cin>>t;
     lli mod=1000000007;

     while(t--)
{
     lli l,r,c,d;
     cin>>l>>r;
     c=log2(l);
     d=pow(2,c+1)-1;
     d=(d-l+1)%mod;
     lli q=(r-l+1)%mod;
     if(q<d)
    d=q;
      lli e=d;
     lli k=0,f,s;
   for(lli i=log2(l);i>=0;i--)
   {
       if(l & (1<<i))
       {
                
             k=(k+(e*(1<<i)%mod)%mod)%mod;
             l=(l-(1<<i)%mod)%mod;
             s=log2(l);
             e=pow(2,s+1)-l;
             e=e%mod;
             if(e>d) e=d;
       }
       
   }
   cout<<k<<endl;
}

}

46

Hey @raja1999
Why do we have to do min (K-L, R-L+1)
Please explain
I didn’t get this part

47

Thank you so much .