CHANDF - EDITORIAL

Work on these cases

2
184040 21318 0 19964
1056424 41420 0 5807

Answers:

19438
5612

2 Likes

thank you so much sir, it helped:)

Provide a proper link to the solution.

Can someone point out the error in my code?
I have tried to split the problem into intervals and then selecting the answer and adding offset to it.
Sol link: CodeChef: Practical coding for everyone

Thanks in advance

@harshil21 pls help my code is giving wrong answer

CodeChef: Practical coding for everyone

Is there any common platform for queries asked during live contest?
I thought comments section below the question is the only place to post the queries.
Please let me know if this is the case.

Go through all the cases given by me in the comments above.

Work on the cases given above in comments.

As far as I know, comments are always moderated during the live contest.
Also, CodeChef has such nice forum ā€œdiscussā€ where your queries can be resolved by admins.
These platforms are apt to resolve any kind of queries.

Can I get some help? I tried a bunch of stuff but I canā€™t figure out how to avoid TLE in subtask 2 and 3
This is my code:

    Reader in = new Reader();
    int t = in.nextInt();
    for (int i = 0; i < t; i++)
      {
       long x = in.nextLong();
       long y = in.nextLong();
       long l = in.nextLong();
       long r = in.nextLong();
       long ans = x|y;
       if (x==0 || y==0 || l==r)
       {
           ans=l;
       }
       if (ans<l || ans>r)
       {
           long max=0l;
           for (long j = l; j <=r ; j++)
           {
               if ((x&j)*(y&j)>max)
               {
                   max = (x&j)*(y&j);
                   ans=j;
               }
           }
           
       }
       System.out.println(ans);
      }

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