Consider the test case-
0 4567 11 456
You have got your answer.
Since you’ve already figured out where your code was failing, here is link to corrected submission-
https://www.codechef.com/viewsolution/33330282
I have made two changes -Line 145 and 164 (I didn’t correct brute force as it was not required anymore).
1 Like
Thank you akshit.
My assumption for the case where X/Y = 0 was wrong. In that case the answer would be L and Not 0.
That was really very silly mistake.
1 Like
@harshil21 can you plz explain me this test case…
1
9 21 2 4
As i understand your editorial i get answer 2 but the original ans is 3.
I follow steps u mentioned in subtask 3 but i got answer 2 so i couldn’t figure it out where i go wrong.So plz explain this can according to your explaination…
Thanks in Advance!!
It is simple.
See X|Y = 11101 and Now taking the prefix of R(100) and turning it’s maximum significant bit off, making it -> 000 and brute forcing different bits of L(10) (Here taking 1 st bit of L) and then appending the last bit from X|Y.
Therefore Z = 011.
Great Editorial. But How can we use binary search in this question? I thought of this approach but could not understand how will we reduce the answer range?
1 Like
@indresh584
your code will surely fail on subtask 3 because of this-
this
ans=(x|y);
if(ans<=r)
{
cout<<ans<<"\n";
continue;
}
Since this is a very trivial mistake, I am assuming you’re writing code only to make subtask 2 work. So, here are some test cases (of subtask 2 type) on which your code would fail.
Cases
28 64 0 26
FAILED YOUR ANS 15 CORRECT ANS 0
33 85 0 14
FAILED YOUR ANS 7 CORRECT ANS 5
32 76 0 95
FAILED YOUR ANS 63 CORRECT ANS 44
9 44 0 24
FAILED YOUR ANS 15 CORRECT ANS 13
8 4 0 9
FAILED YOUR ANS 7 CORRECT ANS 0
I’ve kept ranges of x, y, l, r quite small so you can easily debug.
Edit - I’ve realized the output which is code is giving makes F(x,y,z) optimum (maximized) but z is not the minimum one.
1 Like
Can someone please see my code, I am getting TLE even though I am iterating over 40 bits. I tried generating random numbers and testing, its working fine and I also matched answers using brute force. I can’t figure out what’s wrong. I also tried edge cases like l==r l=0 and all test cases I could find in the comments section but everything seems fine. CodeChef: Practical coding for everyone
@codeverything
Your point that answer of every test case is matching is invalid as you aren’t getting WA…your code’s output might be correct but it is giving TLE…You’re getting TLE for subtask 1 as well for which you shouldn’t as subtask 1 can be solved in O(1)…I’d advise you to review your code once again.
@akshitm16 Thanks for replying. Actually I didn’t provide a separate implementation for the first sub task(I mean I have done that previously and it was passing for subtask 1 but rest were getting TLE) and the thing I can’t figure out is if I am iterating in worst case O(n^2) for 1 <= n <= 40 how is it getting TLE.
I’ve attached some codes with binary search and the basic approach for binary search is mentioned in the above discussion.
You can see if it helps.
Generally, PyPy is a lot faster than Python. Submitting the same code in PyPy3 gets AC.
Link to Submission
So, always submit in PyPy3.
ok I will do so from now on, thanks a lot.
No, you are not following the editorial, you have to traverse bits.
1 Like
@mohit 3999
My code is giving worng ans for CANDF
pls help
https://www.codechef.com/viewsolution/33365503
1079300 15684 0 17230
1301051 21648 0 22895
227040 37014 0 2
279758 17142 0 2713
These are the cases where your code fails and you can see the editorial for more reference.
Can you please tell if we can solve it using digit dp by building Z from most significant bit to least? I was solving but getting wrong answer.