Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
The final sorted string is completely forced: if there are zeroes, it must be , with the first positions equal to 0.
Only two kinds of positions can be wrong: a 1 inside the first positions, and a 0 after the first positions. These counts are always equal.
Call that count . You definitely need at least operations, because one operation can put at most one missing 0 into the left part. No magic triple-shift can teleport two zeroes into the prefix; physics is annoying like that.
Now show operations are enough. Pick one wrong 1 in the left part and one wrong 0 in the right part. Use any third index as filler, then rotate the triple so that the 0 moves into the wrong left position.
So the answer is just the number of 1s in the prefix of length equal to the total number of 0s. Count zeroes, scan that prefix, print the count.
The sorted version of a binary string has no choices.
If the string contains zeroes, then after sorting it must look like:
So the only question is: how many characters are sitting on the wrong side of the boundary after position ?
The Key Count
Look at the first positions. Every 1 there is wrong, because that whole prefix should be zeroes.
Let
Since the total number of zeroes is fixed, every wrong 1 in the left part corresponds to exactly one wrong 0 in the right part. So there are also zeroes after position that need to move left.
Now we prove the answer is exactly .
Why At Least Operations Are Needed
Each operation cyclically shifts the values on three chosen indices. In one operation, a specific chosen left-side position can receive a 0, but you cannot fix two missing zeroes in the left prefix at once.
Why? The left prefix is missing exactly zeroes. A single cyclic shift only moves one value into any particular selected position, and among the selected positions inside the wrong prefix, only one incoming value can be the useful right-side 0 you are bringing over. So each operation can reduce the number of wrong 1s in the prefix by at most .
Therefore, the answer is at least .
Why Operations Are Enough
Take any wrong 1 in the first positions and any wrong 0 after position .
We want to move that 0 into the wrong left position. The operation requires three distinct indices, but the third index can just be filler. Since , such an index exists.
Depending on the order of the three indices, choose either a left cyclic shift or a right cyclic shift so the 0 lands in the chosen wrong prefix position. That fixes one wrong left position. The filler might change, but the total mismatch count in the prefix drops by exactly .
Repeat this for every wrong 1 in the prefix. After operations, the prefix has all zeroes, so the suffix automatically has all ones. Sorted. Done.
Algorithm
For each test case:
1s appear among the first characters.That count is the minimum number of operations.
Complexity: per test case, which is tiny here. The constraints are basically asleep.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n >> s;
int zeros = 0;
for (char c : s) zeros += (c == '0');
int ans = 0;
for (int i = 0; i < zeros; i++) {
ans += (s[i] == '1');
}
cout << ans << '\n';
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n >> s;
int zeros = 0;
for (char c : s) zeros += (c == '0');
int ans = 0;
for (int i = 0; i < zeros; i++) {
ans += (s[i] == '1');
}
cout << ans << '\n';
}
}