PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: nskybytskyi
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Prefix sums, sliding window maximum
PROBLEM:
You have a binary string of length N.
At most once, you can choose one of its substrings of length \leq K and flip all the characters within it (0 \leftrightarrow 1).
Maximize the value of the minimum of zeros and ones present in S.
EXPLANATION:
Suppose there are x zeros and y ones in S.
We want to maximize \min(x, y).
Suppose we perform the flip operation on some substring [L, R]. Let’s see how x and y change.
If there are x_2 zeros and y_2 ones within this subarray,
- The new number of zeros in the entire string is x - x_2 + y_2 (every 0 here will disappear, and every 1 will turn into a 0 instead).
- The new number of ones is y - y_2 + x_2.
- Notice that these values are x - (x_2 - y_2) and y + (x_2 - y_2), respectively.
In particular, notice that the difference between x_2 and y_2 is what really matters here, the actual values of x_2 and y_2 don’t matter as much.
With this in mind, let’s look at the difference between ones and zeros: namely, x-y.
Since we’re trying to maximize \min(x, y), and x+y is a constant (equal to N), we can equivalently just make x-y as close to 0 as possible.
Our flip operation, on a substring with difference x_2 - y_2 changes (x-y) to (x-y) - 2\cdot (x_2 - y_2).
So, we’re looking for a substring of length \leq K with (x_2 - y_2) as close to \frac{x-y}{2} as possible.
Let P_i denote the number of ones minus the number of zeros among only the first i characters of S.
Note that the difference of the subarray [L, R] is now given by simply P_R - P_{L-1}.
Let’s fix the right endpoint R of the chosen subarray, and see if we can find a suitable left endpoint L.
To do that, observe that it’s enough to find only the minimum and maximum values of P_{L-1} in the allowed range (recall that we only allow subarrays of length \leq K).
Why?
This observation follows from the so-called “discrete continuity”.
Observe that adjacent prefix sums differ by exactly 1.
So, if we’re at a prefix sum of x, and we take a few steps to the right to end up with some prefix sum of y, we definitely must visit every value between them - after all, the value changes by exactly 1 each time.
So, if we know the minimum and maximum prefix sums, we also implicitly know every prefix sum available to us (without directly finding them all) - it’ll just be every value between the minimum and maximum!
Now, all we really want to do is compute the minimum (and maximum) of the array P in each ‘window’ of size K.
This is the classical sliding window maximum/minimum problem, and can be solved in several ways:
- \mathcal{O}(N\log N) time by using a data structure like a priority queue/(multi)set to store all current elements and quickly insert/add new ones.
- \mathcal{O}(N) time using a deque or two stacks: see here for a tutorial.
- It’s overkill, but you can also use a fast range minimum query structure (like a segment tree or sparse table) to achieve \mathcal{O}(N\log N) runtime as well.
To finish: let m_1 be the minimum and m_2 be the maximum prefix sums in this range.
- If x-y - 2\cdot (P_R - m_1) \gt 0, the closest you can get to 0 is choosing m_1.
- If x-y - 2\cdot (P_R - m_2) \lt 0, similarly the closest you can get is choosing m_2.
- Otherwise, by discrete continuity as stated above, there will definitely exist some prefix sum that allows us to get as close to 0 as possible (i.e, either 0 or 1, depending on parity).
TIME COMPLEXITY:
\mathcal{O}(N) or \mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #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, k; cin >> n >> k;
string s; cin >> s;
vector<int> pref(n+1);
for (int i = 0; i < n; ++i) {
pref[i+1] = pref[i];
pref[i+1] += s[i] == '1';
pref[i+1] -= s[i] == '0';
}
int mnb = pref[n], mxb = pref[n];
multiset<int> st;
st.insert(0);
for (int i = 1; i <= n; ++i) {
if (i > k) st.erase(st.find(pref[i-k-1]));
int mn = *st.begin(), mx = *st.rbegin();
mnb = min(mnb, pref[n] - 2*(pref[i] - mn));
mxb = max(mxb, pref[n] - 2*(pref[i] - mx));
st.insert(pref[i]);
}
int best = 0;
if (mnb > 0) best = mnb;
else if (mxb < 0) best = -mxb;
else best = n%2;
cout << (n - best) / 2 << '\n';
}
}
Tester's code (C++)
// Use this submission in the editorial, it has useful comments
#include <bits/stdc++.h>
using namespace std;
// Maximizing the number of ones corresponds to
int max_diff(int n, int k, const string& s) {
// After taking prefix sums we are looking for max ps[r] - ps[l]
// For a fixed r this difference is maximized when ps[l] is minimized
vector<int> ps(n + 1);
for (int i = 0; i < n; ++i) {
ps[i + 1] = ps[i] + (s[i] == '1') - (s[i] == '0');
}
// Monotonic queue solves sliding window minimum in amortized constant time
int mx = 0;
deque<int> mono = {0};
for (int r = 1; r <= n; ++r) {
// Element is too old and falls out of the sliding window
if (mono.front() < r - k) {
mono.pop_front();
}
// Maintain the queue sorted in ascending order
while (!mono.empty() && ps[r] <= ps[mono.back()]) {
mono.pop_back();
}
// Empty queue means that ps[r] is the smallest
// Hence ps[r] - ps[l] < 0 and we cannot make a profitable operation
if (!mono.empty()) {
mx = max(mx, ps[r] - ps[mono[0]]);
}
mono.push_back(r);
}
return mx;
}
int solve(int n, int k, const string& s) {
// Let's solve a simpler problem first:
// given the same string and operation, maximize the number of ones
// Maximizing zeros reduces to maximizing ones after we flip each character
// (in our mind, without doing the operation from the statement)
int zero = count(s.cbegin(), s.cend(), '0');
const auto ones = n - zero;
string t(n, '0');
for (int i = 0; i < n; ++i) {
if (s[i] == '0') {
t[i] = '1';
}
}
// Our problem splits into two such problems:
// - if we had fewer ones then we want to maximize their number
// - if we had more ones then we want to maximize zeros instead
const auto upper_bound = (
ones < zero
? (max_diff(n, k, t) + ones)
: (max_diff(n, k, s) + zero)
);
// The statement above is a white lie. In truth, we don't want to go over n/2
// Fortunately, all values in-between the initial value and the upper bound
// are reachable due to "discrete continuity":
// by shrinking the optimal substring one letter at a time
// we change the number of ones by at most one, so we can't "jump over" a value
return min(n / 2, upper_bound);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t; cin >> t; while (t--) {
int n, k;
string s;
cin >> n >> k >> s;
cout << solve(n, k, s) << '\n';
}
}