CHANDF - Chef and Bitwise Product Video Solution | Long Challenge 2020

editorial
1

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
2

Getting WA on task 3
https://www.codechef.com/viewsolution/33051865

3

Can you please explain, why the time complexity is logR?

4

May long challenge 2020*

1 Like
5

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.

6

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
7

@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

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

}

}

9

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

10

plz make a video on explaining your code

1 Like
11

yeah please explain the code as well!!
please make a video!!