FLIP2KHD - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Medium

PREREQUISITES:

BFS, sets

PROBLEM:

You’re given a binary string A. You can repeatedly perform the following operation:

  • Choose 2K positions, of which K must contain 0 and K must contain 1.
  • Then flip the characters at all these positions between 0 and 1.

Find the lexicographically minimum string that it’s possible to reach.
Also find the minimum number of operations needed to reach this lexicographic minimum.

EXPLANATION:

To recap the easy version, the lexicographic minimum is obtained as follows:

  • Let c_0, c_1 denote the number of zeros and ones in A.
  • If c_0 \lt K or c_1 \lt K, the answer is A itself.
  • If 2K = N, the answer is the minimum of A and \bar{A}, where \bar{A} denotes the string obtained by flipping every character of A.
  • If 2K \lt N, the answer is c_0 zeros followed by c_1 ones; equivalently the string obtained by sorting A.

Note that for the first two cases, computing the minimum number of operations needed is trivial: either the string is unchanged and the answer is 0, or every character needs to be flipped and the answer is 1.

Thus we only need to focus on the number of operations in the third case.

We deal purely with the case where \min(c_0, c_1) \ge K and 2K \lt N.

Call an index 1 \le i \le c_0 wrong if A_i = 1.
Essentially, a wrong index is one that needs to contain a 0 in the end, but currently contains a 1.

Let D denote the number of wrong indices.
Then, it can be observed that the minimum number of moves depends only on D, and not on the actual configuration of the string!
More precisely, all strings with D wrong indices have the same answer.

This isn’t too hard to prove: observe that if you permute the elements among the first c_0 positions, then simply applying that permutation to any operation performed will still result in a valid operation; the same applies to permuting elements among the last c_1 positions.

This fact allows us to build up a solution.

Define f(x) to be the minimum number of moves needed to reach a string with x wrong indices.
The base case is, of course, f(D) = 0.

If we have x wrong indices, let’s try to see how one operation can change that.
With a bit of analysis, it can be seen that:

  • The minimum number of wrong positions attainable after a single move is
    |x-K|
  • The maximum number of wrong positions attainable after a single move is
    x+K - \max(0, K+x-c_1) - \max(0, K+x-c_0)

And then every count in between these is also attainable.
These values can be obtained by trying to minimize/maximize the number of wrong positions.
For example, to minimize the number of wrong positions, you would try to choose as many 1’s from the first c_0 positions as possible, while also choosing as many 0’s from the last c_1 positions as possible.

Thus, if the bounds are denoted L_x and R_x, for each L_x \le y \le R_x the value of f(y) is bounded by f(x) + 1.

This can be thought of as “moving” from x to y for a cost of 1, with our goal being to move to 0 as quickly as possible.

We can hence simulate a BFS, while storing unvisited states in a set.
This allows us to repeatedly find the next unvisited state in a range [L, R] in \mathcal{O}(\log N) time, thus giving a solution in \mathcal{O}(N\log N) overall.

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, k; cin >> n >> k;
        string s; cin >> s;

        int zero = ranges::count(s, '0');
        if (min(zero, n-zero) < k) {
            cout << s << '\n' << 0 << '\n';
            continue;
        }
        if (n == 2*k) {
            int ans = 0;
            if (s[0] == '1') {
                for (auto &c : s) c ^= 1;
                ans = 1;
            }
            cout << s << '\n' << ans << '\n';
            continue;
        }

        int bad = 0;
        for (int i = 0; i < zero; ++i) bad += s[i] == '1';

        set<int> active;
        for (int i = 0; i < zero+1; ++i) active.insert(i);
        queue<int> qu;
        vector dist(zero+1, INT_MAX);
        dist[bad] = 0;
        qu.push(bad);
        active.erase(bad);

        while (!qu.empty()) {
            int u = qu.front();
            qu.pop();

            int lo = abs(u-k);
            int hi = u+k - max(0, u+k-zero) - max(0, u+k-n+zero);

            auto it = active.lower_bound(lo);
            while (it != end(active) and *it <= hi) {
                dist[*it] = 1 + dist[u];
                qu.push(*it);
                it = active.erase(it);
            }
        }

        cout << string(zero, '0') + string(n-zero, '1') << '\n';
        cout << dist[0] << '\n';
    }
}