Shrink-Reverse
Contest: Educational Codeforces Round 162 (Rated for Div. 2)
Difficulty rating: 2800
Tags: binary search, brute force, greedy, hashing, implementation, string suffix structures, strings

You are given a binary string $$$s$$$ of length $$$n$$$ (a string consisting of $$$n$$$ characters, and each character is either 0 or 1).

Let's look at $$$s$$$ as at a binary representation of some integer, and name that integer as the value of string $$$s$$$. For example, the value of 000 is $$$0$$$, the value of 01101 is $$$13$$$, "100000" is $$$32$$$ and so on.

You can perform at most $$$k$$$ operations on $$$s$$$. Each operation should have one of the two following types:

- SWAP: choose two indices $$$i < j$$$ in $$$s$$$ and swap $$$s_i$$$ with $$$s_j$$$;
- SHRINK-REVERSE: delete all leading zeroes from $$$s$$$ and reverse $$$s$$$.

What is the minimum value of $$$s$$$ you can achieve by performing at most $$$k$$$ operations on $$$s$$$?

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 5 \cdot 10^5$$$; $$$1 \le k \le n$$$) — the length of the string $$$s$$$ and the maximum number of operations.

The second line contains the string $$$s$$$ of length $$$n$$$ consisting of characters 0 and/or 1.

Additional constraint on the input: $$$s$$$ contains at least one 1.

Output format:
Print a single integer — the minimum value of $$$s$$$ you can achieve using no more than $$$k$$$ operations. Since the answer may be too large, print it modulo $$$10^{9} + 7$$$.

Note that you need to minimize the original value, not the remainder.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first example, one of the optimal strategies is the following:

1. 10010010 $$$\xrightarrow{\texttt{SWAP}}$$$ 00010110;
2. 00010110 $$$\xrightarrow{\texttt{SWAP}}$$$ 00000111.

In the second example, one of the optimal strategies is the following:

1. 01101000 $$$\xrightarrow{\texttt{SHRINK}}$$$ 1101000 $$$\xrightarrow{\texttt{REVERSE}}$$$ 0001011;
2. 0001011 $$$\xrightarrow{\texttt{SWAP}}$$$ 0000111.

Example input:
8 2
10010010

Example output:
7

Example input:
8 2
01101000

Example output:
7

Editorial:
In order to solve a task, let's observe and prove several facts:
Fact 0: Suppose, you have two strings $$$s_1$$$ and $$$s_2$$$ without leading zeroes. Value of $$$s_1$$$ is lower than value of $$$s_2$$$ if either $$$|s_1| < |s_2|$$$ or $$$|s_1| = |s_2|$$$ and $$$s_1 < s_2$$$ lexicographically.
Fact 1: There is a strategy, where you, firstly, perform all swaps, and only after that perform reverses. Proof: let's take some optimal strategy and split all its operations in blocks by reverse operation. Let's look at the last block of swaps: if there is no reverse before it — we found strategy. Otherwise, we can "push" all swaps from this block into the previous block (of course, with fixed indices), since all positions that exist at the current moment, existed earlier. Answer won't increase after this "push". So we can transform any optimal strategy into one we need.
Fact 2: There is no need to make more than $$$2$$$ reverses. Since, we, firstly, swap and then reverse — making $$$3$$$ reverses is equivalent to making $$$1$$$ reverse. Analogically, making $$$4$$$ reverses is equivalent to making $$$2$$$ reverses.
Fact 3: There is no need to make more than $$$1$$$ reverse. If, after the first reverse, we grouped all $$$1$$$-s into one segment, then the second reverse won't change anything. Otherwise, instead of the second reverse, we could make one more swap and "group $$$1$$$-s tighter" thus lowering the value of $$$s$$$.
Fact 4: Suppose, you have two binary strings $$$s_1$$$ and $$$s_2$$$ with equal length, equal number of $$$1$$$-s, and you'll replace last $$$k - 1$$$ zeroes in both of them thus getting strings $$$s'_1$$$ and $$$s'_2$$$. If $$$s_1 \le s_2$$$ then $$$s'_1 \le s'_2$$$ (lexicographically). Proof: if $$$s_1 = s_2$$$ then $$$s'_1 = s'_2$$$. Otherwise, there is the first position $$$p$$$ where $$$s_1[p] = 0$$$ and $$$s_2[p] = 1$$$. After replacing last $$$k - 1$$$ zeroes with ones, if $$$s_1[p]$$$ was replaced, then $$$s'_1 = s'_2$$$. Otherwise, $$$s'_1 < s'_2$$$ since $$$s'_1[p] = 0$$$ and $$$s'_2[p] = 1$$$.
Using facts above, we can finally solve the problem. Let's check $$$2$$$ cases: $$$0$$$ reverses or $$$1$$$ reverse.
$$$0$$$ reverses: it's optimal to be greedy. Let's take the leftmost $$$1$$$ and swap it with the rightmost $$$0$$$ as many times as we can.
$$$1$$$ reverse: leading zeroes will be deleted; trailing zeroes will become leading, so they won't affect the value of the resulting string. That's why the answer will depend only on positions of leftmost and rightmost $$$1$$$-s.
For convenience, let's reverse $$$s$$$. Then, let's iterate over all possible positions $$$i$$$ of now leftmost one. For each left position, let's find the minimum possible position $$$u$$$ of the rightmost one. Minimizing $$$u$$$ will minimize the value of the answer, so it's optimal.
There are two conditions that should be satisfied:
1. the interval $$$[i, u)$$$ should be long enough to contain all $$$1$$$-s from the whole string $$$s$$$;
2. the number of $$$1$$$-s outside the interval should be at most $$$k - 1$$$.
Last step is to choose the minimum interval among all of them. Due to fact 0, we should, firstly, choose the shortest interval. Then (due to fact 4) it's enough to choose the lexicographically smallest one among them.
In order to compare two intervals of reversed string $$$s$$$ it's enough to use their "class" values from Suffix Array built on reversed $$$s$$$.
The complexity is $$$O(n \log{n})$$$ or $$$O(n \log^2{n})$$$ for building Suffix Array + $$$O(n)$$$ for checking each case and comparing answers from both cases.