CHANDF - EDITORIAL

Try

1
491060 16508 0 27138

Your answer -> 26748

, while expected -> 27136

Try the same case mentioned above.

Yeah, this strategy helped me a lot too because with pen and paper it’s too hard to come up with the exact answer. Many times I got the function maximized but the value of z was no minimum. :slight_smile:

2 Likes

Thanks for share

Try this

1
1301051 21648 0 22895

where expected answer -> 22715

1 Like

Thanks for the editorial.
But is there a typo in the example of Subtask 3 that when i = 5, we turn on L[5] and append bits of X|Y, Z should be 001011 instead of 001111? (Because we should keep bits before i unchanged.)

1 Like

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

3 Likes

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.

1 Like

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

CodeChef: Practical coding for everyone.
This is the link to my solution.

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.