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
This might help…You just have to enter number of test cases
#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;
}
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
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??
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.
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
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
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
Can you clarify the need of using double in Java to solve it?