CHANDF - EDITORIAL

editorial
, , , , ,
81

Yes, I’ve shared to links to solutions of people who have used modified binary search to solve this question.

1 Like
82

I tried to solve the 2nd subtask, but don’t know what went wrong .
please provide me the test case where it is failing.

https://www.codechef.com/viewsolution/32911904

83

MIND-BLOWING … I was testing my solution during contest via comparison with brute force approaches to verify. While searching for alternative ways I printed the (X&MASK)*(Y&MASK) for all L<=MASK<=R, found an interesting pattern of several contigous subarrays with increasing numbers. I started towards working my way through finding each increasing subarray’s starting point in range L and R based on X and Y and failed miserably. Just thought wouldn’t it be nice to solve this via binary search and after a lot of effort I gave up thinking it was a crap idea and then here it is, that idea being made possible. It is an excellent problem, please keep on contributing such problems @harshil21 If possible please update the editorial with binary search approach too.

6 Likes
84

i am trying to solve subtask2 .
But it is giving WA . Can somebody help me??
https://www.codechef.com/viewsolution/33027313

85

good problem and good editorial as well

1 Like
86

Try

1
491060 16508 0 27138

Your answer -> 26748

, while expected -> 27136

87

Try the same case mentioned above.

88

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
89

Thanks for share

91

Try this

1
1301051 21648 0 22895

where expected answer -> 22715

1 Like
92

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
93

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
94

Got my mistake. Thanks.

95

made the required changes, but still solution not accepted

96

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;
}
}
}

97

Please provide a proper link to the solution
This is vague.

98

Find some corner cases by comparing with brute force solution.
Even try generating random test cases to find such cases.

1 Like
99

i have tried a lot of cases, matched them with brute force also

100

Try cases like these.

1
1079300 15684 0 17230
Answer -> 15684
Your answer -> 16708

101

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