CHANDF - EDITORIAL

But i coded in java :confused: @redoc_007 all the test cases mentioned above got passed still am getting WA and TLE idk why :confused:

CodeChef: Practical coding for everyone , here is my solution link @harshil21 @redoc_007 :confused:

Use a random test case generator as mentioned in the code. Create your own…idk java.

2 Likes

will try thanks.

Nice question which had my week time in 10 days of long challenge and also really nice logic. :wink:

1 Like

@harshil21

Why is it failing in subtask-2

Link

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

@akshitm16
my code link.
https://www.codechef.com/viewsolution/33326934

@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?