CHANDF - EDITORIAL

Your code’s complexity is O(L-R)… You need the complexity to be in log.

can anybody explain me the need of finding all possible prefix of R?

It means that we brute force all possible prefix to check we configuration will give us the minimal Z which maximizes F(X,Y,Z).

I can’t find why my solution for subtask 2 isn’t working. I went through the editorial to search for test cases and my code is working for each of them.

Test Cases:
10
0 7 0 7
7 0 0 7
7 7 0 0
318458 58156 0 28842
794296 28206 0 26
227040 37014 0 2
1079300 15684 0 17230
1301051 21648 0 22895
491060 16508 0 27138
1133953 63182 0 595

Output:
0
0
0
28840
24
0
15684
22715
27136
463

Link to my submission: CodeChef: Practical coding for everyone

Your outputs are incorrect.
Expected output:

0
0
0
28842
26
0
15684
22715
27136
463

1 Like

This might help…You just have to enter number of test cases :wink:

#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;
}

2 Likes

Thanks for your response, I took care of that, and now my outputs are matching the expected outputs, YET I AM GETTING WA.

Test Cases:
10
0 7 0 7
7 0 0 7
7 7 0 0
318458 58156 0 28842
794296 28206 0 26
227040 37014 0 2
1079300 15684 0 17230
1301051 21648 0 22895
491060 16508 0 27138
1133953 63182 0 595

Outputs:
0
0
0
28842
26
0
15684
22715
27136
463

Link to my updated submission(attempt for subtask-2) : https://www.codechef.com/viewsolution/33111386

1 Like

I am using std::string of c++ to store the binary form, it ends up as TLE, is it because I am doing too many string operations ? my code

And also some people are using bitsets?Is that better than string for this purpose?

Could you explain it? @meet2mky??
How Binary Search is working??..especially this right shift (L+R) >>1??

Can anyone explain 1st solution ?@harshil21

Somewhat, the solution used modified binary search with initial L = 0 and R = 111\dotsc (39 1's), and then it starts searching for the optimal solution. The overall complexity of this approach is O(log(R - L)).
I could not explain to you the detailed solution because even I didn’t have a clue about it. :sweat_smile:

1 Like

can anyone explain why is tle coming.
solution link

I think your code has infinite loop when L and R are same. (Line 28 in your code).

In Subtask3, where M=k if we set z[k]=0 and rest bits as x|y then z<=L also. Then what is the need of brute-forcing all the possible longest common prefixes of z and L

Can you suggest a case for which my code fails in subtask 2 alone ?
CodeChef: Practical coding for everyone my submission link

Iam getting all this testcase correct but still subtask 2 failed for me :confused:
CodeChef: Practical coding for everyone solution link

Y code passed this case too , still am getting a WA for one of the case in subtask 2 :confused:
CodeChef: Practical coding for everyone here is my solution , please help .

HOW TO HANDLE THIS IN JAVA .!!! if DOUBLE used am not able to perform the BINARY OPERATORS :confused:

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