PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: nakul_155
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Segment trees
PROBLEM:
There’s a binary string of length N.
You start at position K, and can perform the following move:
- Flip the character at the current position, then move to an adjacent position.
From a state of all zeros, find the minimum number of moves needed to reach S.
Find the answer for each K = 1, 2, \ldots, N.
EXPLANATION:
From the easy version, we know that the solution to a fixed starting position is as follows:
- Let L, R be the leftmost/rightmost positions containing 1.
- The optimal path is then either K \to L \to R or K \to R \to L with some cyclic detours along the way.
- The detours are computed by finding the unsatisfied indices created by the initial path and then pairing them up to fix them.
Note that L and R are constants independent of the starting position.
Let’s work with just the K \to L \to R path for now, and try to compute its value for all K.
We can then do the same thing with the alternate path, and then take the best of both for each index.
Suppose we compute the set of bad indices for some starting position K.
Then, for starting position K+1, observe that the set of bad indices doesn’t actually change much at all - in fact, only one index will change from bad to good (or vice versa), depending on whether K lies between L and R or outside it.
However, this one change does mess up index pairing quite a bit.
Luckily, we can still maintain the requisite information in a segment tree.
For each index, store a flag denoting whether it’s currently a bad index or not.
Each node of the segment tree will then store the cost of pairing bad indices in its range from left to right, under two different cases:
- The leftmost bad index is not matched, or
- The leftmost bad index is matched
For each case, also store the matching state of the rightmost bad index in the segment.
When merging two adjacent nodes, you can use the left/right information of the two states to merge them.
Each move of the form K \to K+1 corresponds to a point update, which the segtree can handle easily enough.
Note that if there are an odd number of bad indices, you’ll have to toggle the state of R-1, but that’s just another point update anyway.
This allows for computing the answer for all K = 1, 2, \ldots, N in order from left to right in \mathcal{O}(N\log N) time.
Then, simply reverse the string and run the same algorithm to find the answers for the K \to R \to L type paths, and take the best of both for each index.
TIME COMPLEXITY:
\mathcal{O}(N \log N) per testcase.
CODE:
Tester'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());
const int N = 2e5 + 69;
struct node{
// when you enter with 0 parity, what is final {parity, sum}
// when you enter with 1 parity, what is final {parity, sum}
pair <int, int> res[2];
};
node merge(node a, node b){
node c;
c.res[0].first = b.res[a.res[0].first].first;
c.res[0].second = a.res[0].second + b.res[a.res[0].first].second;
c.res[1].first = b.res[a.res[1].first].first;
c.res[1].second = a.res[1].second + b.res[a.res[1].first].second;
return c;
}
node seg[4 * N];
void build(int l, int r, int pos, string &t){
if (l == r){
if (t[l] == '1'){
seg[pos].res[0] = make_pair(1, -2 * l);
seg[pos].res[1] = make_pair(0, +2 * l);
} else {
seg[pos].res[0] = make_pair(0, 0);
seg[pos].res[1] = make_pair(1, 0);
}
return;
}
int mid = (l + r) / 2;
build(l, mid, pos * 2, t);
build(mid + 1, r, pos * 2 + 1, t);
seg[pos] = merge(seg[pos * 2], seg[pos * 2 + 1]);
}
void upd(int l, int r, int pos, int qp, string &t){
if (l == r){
if (t[qp] == '1'){
seg[pos].res[0] = make_pair(1, -2 * l);
seg[pos].res[1] = make_pair(0, +2 * l);
} else {
seg[pos].res[0] = make_pair(0, 0);
seg[pos].res[1] = make_pair(1, 0);
}
return;
}
int mid = (l + r) / 2;
if (qp <= mid) upd(l, mid, pos * 2, qp, t);
else upd(mid + 1, r, pos * 2 + 1, qp, t);
seg[pos] = merge(seg[pos * 2], seg[pos * 2 + 1]);
}
void Solve()
{
int n; cin >> n;
string t; cin >> t;
vector <int> ans(n, INF);
for (int it = 0; it < 2; it++){
reverse(t.begin(), t.end());
reverse(ans.begin(), ans.end());
int l = -1, r = -1;
for (int i = 0; i < n; i++){
if (t[i] == '1'){
l = i;
if (r == -1) r = i;
}
}
swap(l, r);
if (l == -1){
for (int i = 0; i < n; i++){
ans[i] = 0;
}
continue;
}
if (r == 0){
continue;
}
int res = abs(l - r) + 1;
auto tt = t;
auto f = [&](int s, int e){
if (s < e){
for (int i = s; i < e; i++){
tt[i] ^= '0' ^ '1';
}
} else {
for (int i = s; i > e; i--){
tt[i] ^= '0' ^ '1';
}
}
};
f(l, r + 1);
int cnt = 0;
for (int i = 0; i < n; i++){
cnt += tt[i] == '1';
}
auto go = [&](){
// k -> l needs to be accounted for
for (int k = l; k >= 0; k--){
if (k < l){
tt[k] ^= '0' ^ '1';
upd(0, n - 1, 1, k, tt);
cnt += 1;
}
if (cnt % 2 == 0){
int ss = seg[1].res[0].second;
ans[k] = min(ans[k], res + ss + abs(k - l));
}
}
for (int k = 0; k < l; k++){
tt[k] ^= '0' ^ '1';
upd(0, n - 1, 1, k, tt);
cnt += 1;
}
for (int k = l + 1; k < n; k++){
tt[k] ^= '0' ^ '1';
upd(0, n - 1, 1, k, tt);
cnt += 1;
if (cnt % 2 == 0){
int ss = seg[1].res[0].second;
ans[k] = min(ans[k], res + ss + abs(k - l));
}
}
for (int k = l + 1; k < n; k++){
tt[k] ^= '0' ^ '1';
upd(0, n - 1, 1, k, tt);
cnt += 1;
}
};
build(0, n - 1, 1, tt);
go();
tt[r - 1] ^= '0' ^ '1';
res += 1;
cnt += 1;
build(0, n - 1, 1, tt);
go();
}
for (int i = 0; i < n; i++){
cout << ans[i] << " \n"[i + 1 == 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;
}