Try the cases near the limits as discussed above and hopefully you’ll find your mistake.
Tried everything mentioned.
I am surprised. Your code is passing every test case as tested by random test case generator. I’ve tested your code for many cases. It passes everything.
1 Like
Why is the output of 2 3 0 1
0 and not 1?
Hello @harshil21
My code is giving correct output for all the random generated tests. But still it’s failing for subtask 3.
I have gone through all the edge cases from comments and it is passing them as well.
Please help me to debug what is wrong with it.
Thanks in advance.
https://www.codechef.com/viewsolution/33318862
Some of the test cases on which your code is failing.
Click
19738 22349 20351 21371
FAILED YOUR ANS 20319 CORRECT ANS 20351
4714 9548 32751 50826
FAILED YOUR ANS 32750 CORRECT ANS 32751
10748 2320 12285 17443
FAILED YOUR ANS 12284 CORRECT ANS 12285
15460 28224 11893 13146
FAILED YOUR ANS 11892 CORRECT ANS 11893
Your code is very close as it passes many of the test cases.
You can use this to check the cases on which your code is failing-
Click
//
// Created by Mohit sharma on 21/05/20
// https://www.codechef.com/MAY20B/problems/CHANDF
#include <bits/stdc++.h>
// #include<vector>
// #include<set>
// #include<queue>
// #include<map>
// #include<algorithm>
// #include<cmath>
// #include<cstring>
// #include<stack>
// #include<limits.h>
// #include <stdlib.h>
using namespace std;
#define FAST_INPUT_OUTPUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
// Write your code below
#define ll long long int
#define ALL_ONE -1
ll checkInR(ll x, ll y, ll r, int starting_binary_index) {
ll optimum_z = x | y;
ll local_z;
ll cur_optimum_z = 0;
ll current_max_value = 0;
for(int i=starting_binary_index; i >= 0; i--) {
if((r&(1LL<<i))>>i) {
local_z = ALL_ONE;
local_z = local_z << i + 1;
local_z = r & local_z;
local_z = local_z | (optimum_z & ((1LL<<i)-1));
if(((x & local_z) * (y & local_z)) > current_max_value) {
current_max_value = ((x & local_z) * (y & local_z));
cur_optimum_z = local_z;
}
}
}
if((x&r)*(y&r) > current_max_value) cur_optimum_z = r;
return cur_optimum_z;
}
ll checkInL(ll x, ll y, ll l, int starting_binary_index) {
ll optimum_z = x | y;
ll local_z;
ll cur_optimum_z = l;
ll current_max_value = (x & cur_optimum_z) * (y & cur_optimum_z);
int local_k = 63;
for(int i = local_k; i >= 0; i--) {
if((l&(1LL<<i))>>i) {
local_k = i;
break;
}
}
if(local_k > starting_binary_index) local_k = starting_binary_index;
ll mask;
for(int i=local_k-1; i >= 0; i--) {
if(!((l&(1LL<<i))>>i)) {
local_z = ALL_ONE;
local_z = local_z << i;
local_z = l & local_z;
mask = ((1LL<<(i+1))-1);
local_z = local_z | (optimum_z & mask);
if(((x & local_z) * (y & local_z)) >= current_max_value) {
current_max_value = ((x & local_z) * (y & local_z));
cur_optimum_z = local_z;
}
}
}
return cur_optimum_z;
}
ll task3(ll x, ll y, ll l, ll r) {
if((x|y) >= l && (x|y) <= r){
return x|y;
}
ll k = 63;
for(ll i = 63; i >= 0; i--) {
if(((r&(1LL<<i))>>i)^((l&(1LL<<i))>>i)) {
k = i;
break;
}
}
ll fromL = checkInL(x,y,l,k);
ll fromR = checkInR(x,y,r,k);
ll result;
if((x&fromL)*(y&fromL) >= (x&fromR)*(y&fromR)) {
result = fromL;
}else result = fromR;
return result;
}
ll brute_force(ll x, ll y, ll l, ll r) {
ll ans = 0;
ll z = 0;
for(ll i = l; i <= r; i++) {
if((x&i)*(y&i)>ans) {
ans = (x&i)*(y&i);
z = i;
}
}
return z;
}
void solve() {
int t;
ll x, y, l, r;
ll cmp;
cin >> t;
int cnt = 0;
srand(time(0));
while(t--) {
//cout << "#" << cnt++ << " -> ";
// cin >> x >> y >> l >> r;
x=rand()%int(pow(10,12));
y=rand()%int(pow(10,12));
l=rand()%int(pow(10,12));
int diff=rand()%int(pow(10,8));
int ans;
r=l+diff;
if(x==0 || y==0 || r == 0) {
ans=0;
// cout << 0 << endl;
// //assert(brute_force(x,y,l,r)==0);
// continue;
}
else if(l ==0 && r >= 2*max(x,y)) {
ans=x|y;
// cout << (x|y) << endl;
// //assert(brute_force(x,y,l,r) == (x|y));
// continue;
}
else if(r <= l) {
ans=l;
// cout << l << endl;
// continue;
}
else if(l == 0) {
ans= checkInR(x, y, r, 63);
// //assert(brute_force(x,y,l,r) == checkInR(x, y, r, 63));
// continue;
}
else{ans=task3(x, y, l, r);}
int ans1=brute_force(x,y,l,r);
if(ans1!=ans){
cout<<x<<" "<<y<<" "<<l<<" "<<r<<endl;
cout<<"FAILED"<<" "<<"YOUR ANS"<<" "<<ans<<" "<<"CORRECT ANS"<<" "<<ans1<<endl;
cout<<endl;}
// else{cout<<"test passed"<<" "<<"ANS"<<" "<<ans<<endl;}
//
//cout << "expected: " << brute_force(x,y,l,r) << " actual: " << task3(x, y, l, r) << endl;
//assert(brute_force(x,y,l,r) == task3(x, y, l, r));
}
}
// END Code
int main() {
FAST_INPUT_OUTPUT;
solve();
return 0;
}
Make sure you input t as large value (~10,000) as it passes many test cases.
2 Likes
Thank you so much for your quick response.
Hello Akshit,
I have updated the code and tested with t > 800000 and x,y,l,r > 100000. It is passing all the test cases. but still getting wrong answers on submit.
Can you review it again please?
Kudos to you for replying so many days after. Good work
1 Like
@mohitsvnit093
You are doing a very silly mistake. Actually, you are messing with edge cases. Want to know why your code passes every test case and doesn’t gives you the AC verdict? Reason- Your Brute Force is wrong. I want you to correct that yourself.
P.S. You can ask me again if you are unable to do.
1 Like
Hello Akshit,
ll func(ll x, ll y, ll z) {
return ((x&z)*(y&z));
}
ll brute_force(ll x, ll y, ll l, ll r) {
ll ans = -1;
ll z = 0;
ll tans;
for(ll i = l; i <= r; i++) {
tans = func(x,y,i);
if(ans < tans) {
ans = tans;
z = i;
}
}
return z;
}
my brute force method is the same as the brute force of solution code.
I am really not able to find what is the issue here.
Do you really think it is same???
Read it line by line.
difference is of starting ans value.
So according to brute of solution code, if maximum of F(X,Y,Z) = 0 then our expected z would be in range of [L,R] i.e L;
But for my brute force code, that would 0.
Is this where my code is failing?
Consider the test case-
0 4567 11 456
You have got your answer.
Since you’ve already figured out where your code was failing, here is link to corrected submission-
https://www.codechef.com/viewsolution/33330282
I have made two changes -Line 145 and 164 (I didn’t correct brute force as it was not required anymore).
1 Like
Thank you akshit.
My assumption for the case where X/Y = 0 was wrong. In that case the answer would be L and Not 0.
That was really very silly mistake.
1 Like
@harshil21 can you plz explain me this test case…
1
9 21 2 4
As i understand your editorial i get answer 2 but the original ans is 3.
I follow steps u mentioned in subtask 3 but i got answer 2 so i couldn’t figure it out where i go wrong.So plz explain this can according to your explaination…
Thanks in Advance!!
It is simple.
See X|Y = 11101 and Now taking the prefix of R(100) and turning it’s maximum significant bit off, making it -> 000 and brute forcing different bits of L(10) (Here taking 1 st bit of L) and then appending the last bit from X|Y.
Therefore Z = 011.
Great Editorial. But How can we use binary search in this question? I thought of this approach but could not understand how will we reduce the answer range?
1 Like