CHANDF - EDITORIAL

[harshil21]

Can you clarify the need of using double in Java to solve it?

[redoc_007]

@harshil21 code link : CodeChef: Practical coding for everyone

checked all the cases mentioned in the thread working fine for all
Please share the missing case

[harshil21]

Just work on these, you’re very close.

3
19377283 19368100 30890 31436
23962289 7250321 22993 23560
11014 21047686 21058127 21061591

Answers:

30895
23473
21060486

[atharshceh]

When i brute force all the bits , the value of product is exceeding 2^64 thus resulting in a long overflow, that’s y am able to pass subtask 1 and 2 but getting WA and TLE for subtask 3 alone . @harshil21

Here is my solution link
https://www.codechef.com/viewsolution/33177144

[redoc_007]

handled those cases still missing something
code link : CodeChef: Practical coding for everyone

[harshil21]

2
2369383 11351335 17317 26860
20186496 20195266 20218112 20226640

Now, try generating some random cases on your own and check with the brute force solution to check for answers.

[harshil21]

No, your code is missing some other cases, the error is not of overflow.
Try generating random cases and compare with brute force solution.

[atharshceh]

Yes @harshil21, i found that mistake and rectified ,now all the testcases mentioned in the above comments are getting passed still am getting a WA and TLE in subtask 3

Here is my solution link ,
CodeChef: Practical coding for everyone @harshil21

[atharshceh]

Even these cases are passed …

[atharshceh]

Same here @redoc_007 u got it now ?

[redoc_007]

use this CHANDF - EDITORIAL - #208 by akshitm16

[atharshceh]

@akshitm16

#include <bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--)
	{
	    unsigned long int x,y,l,r,x2,y2, ans,max=0;
	    x=rand()%int(pow(10,12));
	    y=rand()%int(pow(10,12));
	    l=rand()%int(pow(10,10));
	    int diff=rand()%int(pow(10,4));
	    r=l+diff;
	    // cin>>x>>y>>l>>r;
	    // BRUTE FORCE
	    int m1=-1;
	    int ans1;
	    for(long long int i=l;i<=r;i++){
	    	if(m1<((i&y)*(i&x))){
	    		m1=(i&y)*(i&x);
	    		ans1=i;
	    		
	    	}
	    }
	    // BRUTE FORCE ENDS


	    // YOUR LOGIC
	    x2=x;
	    y2=y;
	    if(x==0 || y==0)
	    {
	        cout<<0<<"\n";
	        ans=0;
	        continue;
	    }
	    ans=(x|y);
	    if(ans<=r)
	    {
	        cout<<ans<<"\n";
	        continue;
	    }
	    bitset<62>z(ans);
	    bitset<62>zb(ans);
	    bitset<62>rb(r);
	    int lcp=0, i;
        //cout<<z2<<' '<<z;
	    for(i=61; i>=0; --i)
	    {
	        if(rb[i]==1)
	            break;
	        z.reset(i);
	    }
	    ans=z.to_ulong();
	    //cout<<i<<' ';
	    for(;i>=0;--i)
	    {
	        if(! rb.test(i))
	        {
	            z.reset(i);
	            continue;
	        }
	        int flag=z.test(i);
	        z.reset(i);
	        int multiplier=(1<<i);
	        --multiplier;
	        zb=z;
	        x2 = x & multiplier;
	        y2 = y & multiplier;
	        unsigned long int z2 = x2 | y2;
	        bitset<62>z2b(z2);
	        for(int j=i-1; j>=0; --j)
	        {
	            zb[j]=z2b[j];
	        }
	        unsigned long int z3=zb.to_ulong();
	        //cout<<zb<< "i="<<i<<"\n";
	        if((x&z3)*(y&z3)>max)
	        {
	            max= (x&z3)*(y&z3);
	            ans=z3;
	        }
	        //cout<<"i="<<i<<' '<<z3<<"\n";
	        //bitset<62>mul(multiplier);
	        if (flag)
	            z.set(i);
	    }

	    if(max==0)
	        {ans=max;}
	    // YOUR LOGIC ENDS
	    //ans1 is by brute force and ans is by your logic
	    cout<<endl;
	    cout<<x<<" "<<y<<" "<<l<<" "<<r<<endl;
	    if(ans1!=ans){cout<<"FAILED"<<" "<<"YOUR ANS"<<" "<<ans<<" "<<"CORRECT ANS"<<" "<<ans1<<endl;}
	    else{cout<<"test passed"<<" "<<"ANS"<<" "<<ans<<endl;}
	    cout<<endl;
	   
	}
	return 0;
}

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

[atharshceh]

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

[akshitm16]

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

[atharshceh]

will try thanks.

[anon42829743]

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

[nafees87]

@harshil21

Why is it failing in subtask-2

Link

[harshil21]

Try the cases near the limits as discussed above and hopefully you’ll find your mistake.

[nafees87]

Tried everything mentioned.

[akshitm16]

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.