Can be solved in O(bits) complexity.
1. Find the point X in the range [L...R] s.t. F is maximum at X. (There can be multiple values X)
2. Try to reduce X maximum possible inside range [L....R]. Keeping the value of F constant
Complexity: O(bits)
Link: CodeChef: Practical coding for everyone
Got my mistake. Thanks.
made the required changes, but still solution not accepted
Please tell me what’s wrong with this one??
#include<bits/stdc++.h>
using namespace std;
int msbPos(long long int n)
{
int msb_p = -1;
while (n)
{
n = n>>1;
msb_p++;
}
return msb_p;
}
main(){
long long int t;
cin>>t;
while(t–){
int i;
long long int l,r,x,y;
cin>>x>>y>>l>>r;
if(x==0 || y==0){
cout<<0<<endl;
}
else{
string a =bitset<1000>(x).to_string();
string b= bitset<1000>(y).to_string();
int u=0,sum=0;
int w=msbPos®;
for(i=999;i>=999-w;i–){
if(a[i]==‘1’ || b[i]==‘1’){
sum+=pow(2,999-i);
if(sum>r){
break;
}
u=sum;
}
}
cout<<u<<endl;
}
}
}
Please provide a proper link to the solution
This is vague.
Find some corner cases by comparing with brute force solution.
Even try generating random test cases to find such cases.
i have tried a lot of cases, matched them with brute force also
Try cases like these.
1
1079300 15684 0 17230
Answer -> 15684
Your answer -> 16708
I think your logic is not complete.
You could through the editorial once and give it a try again.
seems like changing from unsigned long long to long long sometimes fetches AC so for future questions, is there any way to predict this behavior ?
In code ans = X|Y
Why i am getting WA for sub-tasks 2 ??
@harshil21
Can anyone please check my solution? I am targetting only the first 2 subtasks, 1st subtask is correct and 2nd is wrong.
I have tried each and every test case mentioned above by HARSHIL sir.
Please suggest
https://www.codechef.com/viewsolution/33037995
Use __int128 in cases wherever you have doubts regarding overflow cases.
Send link to your solution.
Try the above case where I have given X = Y = 10^{11}.
It is mentioned above.
@harshil21 Plz review my code.I have got 40 points for this but cannot understand what test case may go wrong for this:
Try
2
7216784 5118850 23889 26008
475288 411705 32322 32875
Answers expected:
24466
32441
Yes the code gives these expected answers as stated by you.
for test case 1: 32000
for test case 2: 26324