Hi,
I have made a video discussing the solution for the problem Chef and Bitwise Product under May long challenge 2020. I hope it helps you understand the solution.
If you have any doubts regarding the video and this problem, please do post them here.
Happy coding!
3 Likes
Can you please explain, why the time complexity is logR?
I’m facing problem in understanding what is the significance of curr in your code. If possible can you share photo by dry running your code on paper.
say i am at bit position i from left. curr will simply store the R value considering only bits till position i-1 form left.
1 Like
@vedhant brother have i done that what u have explained in vdo
my code does not pass subtask 3
I cant understand where is the bug
adeek
May 18, 2020, 6:50am
8
it gives WA in all test cases??
#include<stdio.h>
#include<stdlib.h>
#define ll long long int
int compare(const void * a, const void * b)
{
return ( (int )a - (int )b ); }
void solve(ll t)
{
ll x,y,z,l,r,curr=0,p,a[64]={0},i;
int k=0,eq=1;
scanf("%lld%lld%lld%lld",&x,&y,&l,&r);
for(i=62;i>=0;i–)
{
p=(1LL<<i);
if((l&p)==(r&p)&&eq)
{
curr+=r&p;k++;
continue;
}
if(eq)
eq=0;
if(r&p)
{
k++;
a[k]=curr+p-1;
}
curr+=r&p;
}
a[k+1]=r;a[k+2]=l;
qsort(a,64, sizeof(ll), compare);
ll ans=a[63];
for(i=63;i>=0;i–)
{ if(a[i]==0)
break;
else if((x&a[i])*(y&a[i])>(x&ans)*(y&ans))
{ans=a[i];}
}
for(i=62;i>=0;i–)
{
p=(1LL<<i);
if((ans&p)==0)
continue;
if((x&p)==0 && (y&p)==0 && (ans-p)>=l)
ans=ans-p;
}
printf("%lld\n",ans);
}
int main()
{
int t;
scanf("%d",&t);
while(t–)
{
solve(t);
}
}
https://www.codechef.com/viewsolution/33275613
i am getting correct solution of the example test cases, but when submitted its showing tle can u tell how to get rid of it
plz make a video on explaining your code
1 Like
yeah please explain the code as well!!
please make a video!!