Problem Link: SINGLEOP1 Problem - CodeChef
I tried this problem, and it doesn’t work properly. I referenced solution of this problem but I’m not able to understand it well.
It would be kind if anyone can help me out of this. Thanks!
Below is the link of the solution of code.
[Solution: 86159821 - CodeChef]
(CodeChef: Practical coding for everyone)
I observerd the sample cases and saw that the answer is simply the number of ones from left to right before the first 0. Ex., given string: 101, counting 1s from the left and stopping at the first 0 gives an answer of 1 (which is consistent with the test output). This strategy works for other cases too.
In code:
#include <iostream>
using namespace std;
void solve() {
int n; cin >> n;
string s; cin >> s;
int ans = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '1') ans++;
else break;
}
cout << ans << '\n';
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
If this helps you, consider marking this as a solution, if not, send a reply and I’ll try to explain more!
Thank you for your response @gapprog!
I understand the trick you talked about but how do you find it?
For example,
X = 100001 (33)
If I want to maximize X using Xor operation, I’d prefer binary string P- 011110 (30)
X = X ^ P
Where, P = floor ( x / (2^y) ) = 30 and we have to find y as per problem.
We will get y = 1 from accepted solution but above expression will result in 16.
I hope I’m able to explain my problem and let me know if I went somewhere wrong.
Rather than going through a theoretical approach, I’m going to explain my thoughts through cases.
Ok so first let’s go backwards. Imagine we didn’t construct a string P. Instead, we went with the answer. We see then that in the case X = 33, X \oplus \lfloor\frac{X}{2^y}\rfloor = 33 \oplus\lfloor\frac{33}{2^y}\rfloor. If we experiment with y = 1, we get the answer of 49. If we then increase y, we can see that the corresponding value goes down. In your case if we say P = 30, then 33\oplus30 yields 63, which is indeed the max. If we solve for y in \lfloor\frac{X}{2^y}\rfloor (ignoring the floor function), we get \frac{X}{2^y} = max \Rightarrow 2^y = \frac{X}{max} \Rightarrow \log_2 \frac{X}{max} = y. Now if we set max = 30, then we get \log_2 \frac{33}{30} = 0.1375.... Setting aside any more math, we can see that the range of y from the problem is 1 \le y \le |S|. Therefore 30 for sure cannot work. I think you can see that the perfect opposite to a number will not yield the correct answer all the time. I believe this is because the location of the first 0 is important when dealing with this problem in particular since its not a straight up xor, but rather the xor after the operation defined in the problem. If you find any better reasoning (I’ll try to look myself), feel free to post it here and in your successful submission!
I’m satisfied and have considered your solution, but I think it will get TLE due to lots of calculations.
I went through various solutions and observed that:
P is actually X >> y therefore we can get value of P only by right shifting X for y times and I think that’s the only way to get maximum possible value of X.
If we estimate value of P, like I did, it is not guaranteed that the value can be obtained by performing right shift operation/s.
And I think the trick of counting 1’s before first appeared 0 is based for these reasons.
I’m glad to have your opinions on it. Thank you.
Yes I did the calculation to show you why your case doesn’t work, however I agree that will TLE. And as you said, shifting X y times is the only way to get the maximum possible value. Since we care about the number of shifts, I think its easy to see then that the number of 1s before the first 0 is what we care about. Thanks for the insight!