PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Binary search
PROBLEM:
You have a binary string S.
You can:
- Choose i such that S_i \ne S_{i+1}
- Keep either the prefix till i or the suffix from i+1, and discard the other part.
- The part that’s kept must contain both 0’s and 1’s.
This operation can be performed however many times you like.
Let f(S) denote the lexicographically smallest string that’s attainable.
You can flip at most one substring of S to obtain a new string S'.
Find the lexicographically maximum possible value of f(S').
EXPLANATION:
To recap the computation of f(S):
- If no operation can be performed on S, then f(S) = S.
This is the case if and only if S has \le 2 blocks, where a block is a maximal substring of a single character. - Otherwise, the answer is a (sub)string of the form 0\ldots 0 1\ldots 1, where the number of zeros is maximized and then the number of ones is minimized (but the number of ones must be positive.)
Our aim now is to flip a substring of S to maximize f(S') for the resulting string S'.
We’ll use S' to denote the string obtained after the flip, while S will always denote the original string.
Our aim being to lexicographically maximize f(S'), clearly we should try to make it start with 1 if possible.
However, note that this is only really possible if f(S') = S', since in the other case f(S') will always start with a 0.
Now, making f(S') = S' happen means S' must not have any moves available to it.
This is possible if and only if S' has at most two blocks.
It can be verified that if it’s at all possible to make S' of this form, then the optimal way to do it is to choose the leftmost block of zeros in S and flip it.
If doing this results in a string with \le 2 blocks then it’s the answer, otherwise we need to analyze further.
We’re now in the case where f(S') looks like some zeros followed by some ones.
The zeros will be the largest block of zeros present in the string (excluding the suffix block, if that’s zeros.)
First, we make a couple of observations about which substrings can possibly be optimal to flip.
The main ones are:
- It’s always optimal to flip some contiguous set of blocks, i.e. we’ll never need to partially flip a block.
- Among the contiguous set of blocks that we do flip, it’s optimal for the first and last blocks to both contain zeros.
Proof
Suppose the left endpoint of the range we choose lies in the middle of a block.
Then,
- If this block contains zeros, it’s better to extend the left endpoint further left to fully convert this block to ones - which doesn’t make the answer worse.
- If the block contains ones, it’s instead better to shrink the left endpoint to the right, and just not flip anything in this block at all - again, it can be verified that the answer doesn’t become worse.
The same applies to the right endpoint - it can be either extended or shrunk to cover/exclude the block without making the answer worse.
Finally, this same reasoning also tells us why it’s not optimal to start/end with a block of ones - because we could just not flip it and shrink the range, without making the answer worse.
Our first goal should simply be to minimize the maximum zero block.
This is fairly easy to do using binary search.
Suppose we fix a value M, and we want all blocks of zeros to have length \le M.
Then,
- If all zero-blocks already have length \le M, nothing needs to be done.
- Otherwise, consider the leftmost and rightmost zero-blocks that have length \gt M.
Both these blocks surely need to be flipped, since we noted that it’s enough to work with only flipping full blocks. - Since these two blocks need to be flipped, of course everything between them also needs to be flipped.
Given that we currently care only about minimizing the maximum zero-block, it’s hence optimal to just flip all blocks between (and including) the extreme blocks with length \gt M, and nothing else.
Then we just check if the resulting string has all zero-blocks having length \le M.
This gives a fairly straightforward \mathcal{O}(N) check for a fixed M, and this predicate is clearly monotone so we can apply binary search to find the smallest M that’s valid in \mathcal{O}(N\log N) overall.
Once the optimal M is known, we look at the ones.
f(S') will first choose a zero-block of length M, and then pick the smallest one-block immediately succeeding such a length M block.
Our goal is now to make this “smallest one-block” as large as possible.
This can also be turned into a binary-searchable check.
Let’s fix a value Y, and try to see if we can flip in such a way that every zero-block of length M is immediately followed by a one-block of length at least Y.
Just as before, if we’re able to perform this check quickly, we can binary search to find the optimal Y.
All that remains is to find an appropriate linear-time check.
Here’s one way.
Let’s call a block of zeros “bad” if one of the following holds:
- The block has length \gt M, or
- The block has length exactly M, and is followed by a block of ones with length \lt Y.
Note that if there are no bad blocks in the string then nothing needs to be done - every length M zero-block is already followed by a one-block of length \ge Y.
So, we assume that there’s at least one bad block.
Now, look at the leftmost bad block.
We need to make it not bad. There are two options for this:
- Flip the block itself to make it consist of ones.
Note that doing this means that the range of blocks we flip must include this block - and in particular must start at or before it. - If we don’t flip it, then flip the next zero-block to its right, to extend the one-block after it.
This option is only viable if the bad block has length M but fewer than Y ones after it.
If we choose the first option, observe that there’s no point in flipping anything to the left of the leftmost bad block; since nothing there needs to be fixed anyway.
So, in that case it’s optimal for the left endpoint of the range we flip to just be exactly this leftmost bad block.
In the second option, of course the only choice is the next zero-block to the right.
Thus, there are only two viable left endpoints for the range.
Similar reasoning shows that there’s only one viable right endpoint for the range: the rightmost “bad” block.
Thus, we have (at most) two candidate ranges to check.
For each range we can simply simulate the flip and see if the resulting string satisfies the condition (maximum zero-block length is M, and all M length zero-blocks have at least Y ones after them).
This is easy in linear time.
Since this gives us a linear-time check, we can now use binary search to obtain an algorithm that’s \mathcal{O}(N\log N) overall - so we’re done!
TIME COMPLEXITY:
\mathcal{O}(N \log N) per testcase.
CODE:
Editorialist's code (C++)
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
string s; cin >> s;
vector<array<int, 2>> blocks;
int cur = s[0], ct = 0;
for (auto c : s) {
if (c == cur) ++ct;
else {
blocks.push_back({cur - '0', ct});
cur = c;
ct = 1;
}
}
blocks.push_back({cur - '0', ct});
if (size(blocks) <= 3 or (size(blocks) == 4 and s[0] == '1')) {
int flip = 0;
for (auto c : s) {
if (c == '0') {
flip = max(flip, 1);
if (flip == 1) cout << 1;
else cout << 0;
}
else {
cout << 1;
if (flip == 1) flip = 2;
}
}
cout << '\n';
continue;
}
// minimize max zero block
auto check1 = [&] (int m) {
int l = -1, r = -1;
for (int i = 0; i+1 < size(blocks); ++i) {
if (blocks[i][0] == 1) continue;
if (blocks[i][1] > m) {
r = i;
if (l == -1) l = i;
}
}
if (l == -1) return true;
for (int i = l+1; i < r; i += 2) {
if (blocks[i][1] > m) return false;
}
return true;
};
int lo = 0, hi = n;
while (lo < hi) {
int mid = (lo + hi)/2;
if (check1(mid)) hi = mid;
else lo = mid+1;
}
int M = lo;
// maximize after-M one block
auto check2 = [&] (int y) {
int l = -1, r = -1, l2 = -1;
for (int i = 0; i+1 < size(blocks); ++i) {
if (blocks[i][0] == 1) continue;
if (blocks[i][1] > M) {
r = i;
if (l == -1) l = i;
}
if (blocks[i][1] == M and blocks[i+1][1] < y) {
r = i;
if (l == -1) l = i, l2 = i+2;
}
}
if (l == -1) return true;
auto flip = [&] (int L, int R) {
vector<array<int, 2>> newblock;
for (int i = 0; i < size(blocks); ++i) {
auto [ch, ct] = blocks[i];
if (i >= L and i <= R) ch ^= 1;
if (!newblock.empty() and newblock.back()[0] == ch) newblock.back()[1] += ct;
else newblock.push_back({ch, ct});
}
for (int i = 0; i+1 < size(newblock); ++i) {
if (newblock[i][0] == 1) continue;
if (newblock[i][1] > M) return false;
if (newblock[i][1] == M and newblock[i+1][1] < y) return false;
}
return true;
};
bool good = flip(l, r);
if (l2 != -1 and l2 <= r) good |= flip(l2, r);
return good;
};
lo = 0, hi = n;
while (lo < hi) {
int mid = (lo + hi + 1)/2;
if (check2(mid)) lo = mid;
else hi = mid-1;
}
cout << string(M, '0') + string(lo, '1') << '\n';
}
}