PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Sorting, binary search/two pointers
PROBLEM:
You’re given a binary string with some of its elements yet undefined (represented by ?).
It’s guaranteed that the first and last characters are defined.
For each K \in [0, N], solve the following problem:
- Consider replacing all occurrences of ? with either 0 or 1 to form a proper binary string that has exactly K ones.
Find the minimum possible number of blocks in the resulting string.
EXPLANATION:
Observe that the number of blocks in a binary string is also equal to the number of indices i such that S_i \neq S_{i+1}, plus one.
This is because, if you look over the string from left to right, you start out with the first block and whenever there’s a different character from the previous one, a new block begins.
So, minimizing the number of blocks is equivalent to minimizing the number of adjacent unequal characters in the string (which is perhaps a bit easier to think about).
Let’s now attempt to solve the problem for a fixed value of K.
First off, if K is smaller than the number of ones already in the string, or larger than the number of ones plus the number of undefined elements, clearly it’s impossible to even obtain K ones so the answer is -1.
We thus only solve for K that are actually possible.
Consider a block of undefined elements, bordered by defined elements.
There are four possibilities: the left border can be 0 or 1, and the right border can be 0 or 1.
We consider each case separately.
Case 1: 0??\ldots ??0
Here, if we’re able to replace every ? with a 0, no new blocks will be created.
Otherwise, there’s at least one occurrence of 1, and at least two new blocks will be created: since we’ll have to switch from 0 to 1 at some point, and then back to 0 eventually by the time we reach the right border.
It’s not hard to see that we can always ensure that no more than two blocks are created by the replacement: for example just place the replacements in sorted order, with all zeros before all ones.
So, such a block of undefined elements will add either 0 or 2 to the answer, depending on what we do with it.
Case 2: 1??\ldots ??1
This case is clearly the exact same as the previous one, just with the roles of 0 and 1 swapped.
So, it contributes either 0 or 2 to the answer, depending on whether we fill the block entirely with ones, or have at least one 0 in there.
Case 3: 0??\ldots ??1
Now the endpoints are different, and we see that the contribution to the answer is at least 1 since we’ll switch from a 0 to a 1 at some point.
Just as before, it can be kept down to exactly 1 by placing elements in sorted order.
So, such a block will always contribute 1.
Case 4: 1??\ldots ??0
Exact same as case 3, the contribution is always going to be 1 - though we’ll need to place elements in reverse-sorted order this time to ensure a contribution of 1.
Now that we’ve analyzed all four cases, it’s not too hard to see how to minimize the answer.
First, we should try to satisfy as many of the 0?\ldots ?0 and 1?\ldots ?1 blocks as we can, by filling them with zeros and ones respectively. This is because doing so will make them contribute 0 to the answer rather than 2.
Since only the number of satisfied blocks matters, this of course should be done greedily: satisfy blocks in increasing order of their length.
That will leave some unsatisfied blocks, as well as the blocks with differing borders.
The latter will always contribute 1 to the answer as we’ve seen, so knowing their count is enough.
The former, since they’re unsatisfied, will contribute 2 each to the answer: so again knowing their count is enough.
This gives us a way to solve the problem for a single K in linear time:
- Create a list of blocks of the form 0?\ldots ?0, sorted by length.
Then, fill all the ? in these blocks with 0's, as long as the total number of zeros doesn’t exceed N-K.
Suppose x of these blocks are not able to be satisfied. - Similarly, create a sorted (by length) list of blocks of the form 1?\ldots ?1, and fill them with 1's as long as the total number of ones doesn’t exceed K.
Suppose y of these blocks are not satisfied. - Let the number of blocks of the form 0?\ldots ?1 or 1?\ldots ?0 be z.
- The answer is then 1 + 2\cdot (x+y) + z.
This solves the problem for a fixed K in \mathcal{O}(N\log N), so we need to figure out how to optimize it to solving for all K.
Note that if we know the values of x, y, z above, the final answer is also known to us.
z is a constant independent of K, so it can be computed once and stored.
Let’s now look at computing the value of x.
First, the sorted list of lengths of 0?\ldots ?0 blocks is independent of K, so this can be computed once and stored.
Once this list is known, we’re really only interested in how many blocks can be satisfied while ensuring that the total number of zeros doesn’t exceed N-K.
In other words, we’re interested in the largest prefix sum of the list which, when added to the existing number of zeros, doesn’t exceed N-K.
This can be found easily in \mathcal{O}(\log N) by just binary searching on the prefix sum array, so we’re done!
You can also use a two-pointer approach rather than binary search, if you so wish.
Computing the value of y can be done the exact same way, so this completes the problem.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n; cin >> n;
string s; cin >> s;
int ans = 1;
for (int i = 0; i + 1 < n; i++){
if (s[i] != s[i + 1] && s[i] != '?' && s[i + 1] != '?'){
ans++;
}
}
vector <int> b0, b1;
int sum = 0;
int s0 = 0, s1 = 0;
for (int l = 0; l < n; l++){
if (s[l] == '?'){
int r = l;
while (r + 1 < n && s[r + 1] == '?'){
r++;
}
int c = (s[l - 1] - '0') + (s[r + 1] - '0');
if (c == 0){
s0 += r - l + 1;
b0.push_back(r - l + 1);
} else if (c == 2){
s1 += r - l + 1;
b1.push_back(r - l + 1);
} else {
ans += 1;
sum += r - l + 1;
}
l = r;
}
}
sort(b0.begin(), b0.end(), greater<int>());
sort(b1.begin(), b1.end(), greater<int>());
int one = 0;
int qq = 0;
int zero = 0;
for (auto x : s){
one += x == '1';
qq += x == '?';
zero += x == '0';
}
vector <int> f(n + 1), g(n + 1);
int curr = 0;
for (auto x : b0){
for (int i = curr + 1; i <= curr + x; i++){
f[i] = f[curr] + 1;
}
curr += x;
}
curr = 0;
for (auto x : b1){
for (int i = curr + 1; i <= curr + x; i++){
g[i] = g[curr] + 1;
}
curr += x;
}
for (int k = 0; k <= n; k++){
if (!(one <= k && k <= one + qq)){
cout << -1 << " \n"[k == n];
continue;
}
int res = ans;
int a = k - one;
int b = n - k - zero;
if (a > s1 + sum){
res += 2 * f[a - s1 - sum];
} else if (b > s0 + sum){
res += 2 * g[b - s0 - sum];
}
cout << res << " \n"[k == n];
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
s = input()
ones, free = s.count('1'), s.count('?')
always, zero, one = 1, [0], [0]
p = 0
for i in range(1, n):
if s[i] == '?': continue
if s[i] != s[p]: always += 1
else:
if s[i] == '0': zero.append(i - p - 1)
else: one.append(i - p - 1)
p = i
zero.sort()
one.sort()
p, q = len(zero) - 1, 0
sz, so = sum(zero), 0
ans = [-1]*(n+1)
for k in range(n+1):
if k < ones: continue
if k > ones + free: break
# k - ones occurrences of 1
while q < len(one):
if so + one[q] <= k - ones:
so += one[q]
q += 1
else: break
# free - (k - ones) occurrences of 0
while sz > free - k + ones:
sz -= zero[p]
p -= 1
ans[k] = always + 2*(len(one) - p + len(zero) - q - 1)
print(*ans)
'''
1...0 or 0...1 - doesn't change answer
0...0 - ans += 0 if all zeros, else ans += 2
1...1 - ans += 0 if all ones, else ans += 2
'''