But i coded in java @redoc_007 all the test cases mentioned above got passed still am getting WA and TLE idk why
Use a random test case generator as mentioned in the code. Create your own…idk java.
will try thanks.
Nice question which had my week time in 10 days of long challenge and also really nice logic.
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.
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.
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
@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.
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?