CHANDF - EDITORIAL

Test data is generated randomly between the given constraints.
But I could see into it if you could provide me a link of the solution.

1 Like

Why can’t you guys put readable codes here in the editorials? With so many defines and functions, the code becomes very messy.

1 Like

@harshil21 CodeChef: Practical coding for everyone
Please look into my code
I had tried all the testcases memtioned here.All are giving correct aswers.But i am not getting AC.
Please give other test cases where i am failing

Thank you for an active invitation to help me with my code. Basically, I had just tried a brute force approach after optimising the low and high values aptly to some binary numbers of the form 2^n-1, assuming that minimum Z for maximum value of given equation will be within this range.

Though it worked for smaller custom inputs and the sample inputs that were given with the question, it was not even able to get any partial marking from the submission result.

In case you’d like to see the code, here’s the link to my bruteforce approach.
https://www.codechef.com/viewsolution/32482373

Try

1
154112 33236 0 462

The answer should be 0.

You can not loop from L to R as T ranges upto 10^5 and L,R \le 10^{12}.
You have to find a approach which solves the question through binary bits of the number.
Read the editorial.

1 Like

I’ve tried to put up a very commented solution so it is very comprehensive for a reader.
The functions simplify the process.

i am still getting wrong answer somebody please tell where i am wrong

Yes, now it’s working. Didn’t know about 1LL. Thank You @harshil21

1 Like

@harshil21 WA on CodeChef: Practical coding for everyone
if possible please share the missing case

Just missing these cases…

2
9601481 9048973 8455 11968
2369383 11351335 17317 26860

Answers:

9165
26471

1 Like

https://www.codechef.com/viewsolution/33077448
Can anybody please tell me what’s wrong here. It’s still showing TLE

@chal_nikal1 or the first subtask the answer is x|y when both x , y are non zero. if any one or both are zero then the function gives 0 for all z. for subtask 2 answer can’t be x|y always just because it may not be between l and r.

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

can anybody tell why its going giving WA.
i have tried all the test cases in comments it is giving right answer.

Can Someone Tell Why My Code Is Showing Wrong Answer

#include <bits/stdc++.h>
using namespace std;
long long int binaryToDecimal(vector v)
{
long long int decimal = 0 ;

for(long long int i = 0 ; i < 62 ; i++)
decimal = decimal * 2 + v[i];
return decimal;
}
vector decToBinary(long long int n)
{
// array to store binary number
vector binaryNum(62);
// counter for binary array
long long int i = 61;
while (n > 0) {

    // storing remainder in binary array 
    binaryNum[i] = n % 2; 
    n = n / 2; 
    i--; 
} 

return binaryNum;
// printing binary array in reverse order
}
vector<vector> possivalues(vector l,vector r,vector x1,vector y1)
{
vector::iterator it1;
vector::iterator it2;
vector<vector> z;
vector t;
int i;
for(i=0;i<62;i++)
{
if(l[i]==r[i])
t.push_back(l[i]);
else
break;
}
while(i<62){

    if(r[i]==0)
    {
        t.push_back(0);
        if(i==61)
        z.push_back(t);
    }
    else
    {
        t.push_back(0);
        for(int j=i+1;j<62;j++)
        t.push_back(x1[j]|y1[j]);
        z.push_back(t);
        it1=t.begin()+i;
        it2=t.end();
        t.erase(it1,it2);
        t.push_back(1);
        
    }
    i++;
}

return z;

}
int main() {
int test;
cin>>test;
for(int t=0;t<test;t++)
{
vector<vector> z;
long long int x,y,l,r;
cin>>x>>y>>l>>r;
vector l1=decToBinary(l);
vector r1=decToBinary®;
vector x1=decToBinary(x);
vector y1=decToBinary(y);
z=possivalues(l1,r1,x1,y1);
int max=INT_MIN;
int min_no=INT_MAX;
for(int i=0;i<z.size();i++)
{
int a=binaryToDecimal(z[i]);
int d=(x&a)*(y&a);
if(d>max)
{
min_no=a;
max=d;
}
if(d==max&&a<min_no)
{
min_no=a;
}
}
cout<<min_no<<endl;
}
return 0;
}

In case of subtask 2 , why do we need to find all the LCPs wont the minimum is fine?
https://www.codechef.com/viewsolution/33068071
That’s how i did and it shows WA .
Approach : I found the first ‘1’ from left of R and made that corresspoding bit in Z as 0 and after that bits the rest of the bits are calculated as Z[i] = X[i]|Y[i].

@harshil21 May be a small correction is to be made here

I believe the ones which are in bold should be 001101 and 001011

1 Like

@atharshceh I was frustrated by the same idea :grin:. consider this case(numbers in their binary form)
x=00000111
y=01000000
R=01001000 and is simply zero
now if you make the first set bit off in R tyen value of function becomes zero because its the only bit that’s also set in y. hope you get it now!

2 Likes

@harshil21
sir, my code is giving all expected outputs, also for the cases that you have given in your replies for this editorial. But, when submitting both subtask-2 & 3 are giving wrong answers.
Can you please provide a test case where it is going wrong
my code: https://www.codechef.com/viewsolution/32969054

No, maybe you misinterpreted the 1’s in bold.
They are the bits which are “set” after making our Z \le R to try and make(Z \ge L).
The 1’s you’ve highlighted are the bits of X | Y which are just appended at the end.
I hope I cleared it up.