PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: nakul_155
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
None
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.
EXPLANATION:
If S contains no occurrences of 1, the answer is trivially 0; so we now assume that S contains at least one occurrence of 1.
Let the leftmost and rightmost occurrences of 1 be at indices L and R.
We definitely need to toggle these two switches; which means that starting from K, we must follow (at least) one of these patterns:
- K \to \ldots \to L \to \ldots \to R
- K \to \ldots \to R \to \ldots \to L
That is, from the starting position we need to hit either L or R for the first time, and then we still need to move all the way across for the other one.
Let’s consider only the K \to \ldots \to L \to \ldots \to R case for now.
Suppose we move straight from K to L, and then from L to R without any detours.
This will flip all switches from K to L (except L), and then all switches from L to R (except R).
We can also freely flip R in the end by moving to R-1.
Let T denote the binary string representing the current state of the switches, after reaching R-1.
Call an index i good if S_i = T_i, and bad otherwise.
Let the bad indices be i_1, i_2, \ldots from left to right.
Note that every bad index is one that we must have passed through in our K \to L \to R \to R-1 path.
To fix a bad index, we need to leave it one more time (or rather, an odd number more of times.)
However, while doing this we need to ensure that the existing good indices are left an even number of additional times, to preserve their values.
In particular, note that if we have two bad indices x and y, the path x \to y \to x will toggle x and y once each, and everything between them twice each - meaning it will turn x and y into good indices while not affecting the state of anything else.
This is a useful step which we’ll use to compute the answer, because in a sense, these fix-2-position cycles are the only “detours” available to us from the base path at all!
More precisely, any sequence of moves can be broken up into the base path and several such cyclic detours; since if we ever leave the main path then we have to return to where we left to continue it.
Suppose there are an even number of bad indices: i_1, i_2, \ldots, i_{2m}.
Then, it can be seen that the best way to fix them all is to pair them up as (i_1, i_2), (i_3, i_4), \ldots, (i_{2m-1}, i_{2m}); and then use the cycle construction from above, i.e. insert the detour cycles
- i_1 \to i_2 \to i_1
- i_3 \to i_4 \to i_3
\vdots - i_{2m-1} \to i_{2m} \to i_{2m-1}
into the existing K \to L \to R \to R-1 path.
This has a cost of 2\cdot (i_2 - i_1) + 2\cdot (i_4 - i_3) + \ldots which is the best we can do.
Adding this to the base cost of the K \to L \to R \to R-1 path gives the entire cost.
On the other hand, suppose there are an odd number of bad indices i_1, \ldots, i_{2m+1}.
It’s now not possible to pair everything up nicely.
So, we need to spend a move making another index bad.
One way to look at this is that after inserting several cyclic detours into our path, we’ll have ended up at index R-1 with exactly one previous index being bad.
So, in a sense, the only option we have at all is to flip the state of index R-1.
This will put us back into the even case, which we know how to solve: the bad indices can just be paired up.
The above discussion was for the path K \to L \to R.
For the K \to R \to L path, a similar analysis holds; in fact, to solve the second case you can simply reverse the input string, mirror K across the center, and then run the solution for K \to L \to R on it - no extra work (or code) required!
The final answer is the minimum cost across both cases.
Since each case runs in linear time, this is linear overall.
TIME COMPLEXITY:
\mathcal{O}(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());
void Solve()
{
int n, k; cin >> n >> k;
k--;
string t; cin >> t;
int ans = INF;
for (int it = 0; it < 2; it++){
reverse(t.begin(), t.end());
k = n - 1 - k;
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){
cout << 0 << "\n";
return;
}
if (r == 0){
continue;
}
int res = abs(k - l) + 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(k, l);
f(l, r + 1);
int cnt = 0;
for (int i = 0; i < n; i++){
cnt += tt[i] == '1';
}
if (cnt % 2 == 1){
res += 1;
tt[r - 1] ^= '0' ^ '1';
}
vector <int> pos;
for (int i = 0; i < n; i++){
if (tt[i] == '1'){
pos.push_back(i);
}
}
assert(pos.size() % 2 == 0);
for (int i = 0; i < pos.size(); i += 2){
res += 2 * (pos[i + 1] - pos[i]);
}
ans = min(ans, res);
}
cout << ans << "\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;
}