Hints: Shrink-Reverse

The string is read as a binary number with the leftmost character as the most significant bit. Among two strings of the same length, which one is smaller as an integer?

Try to state the rule in terms of lexicographic order on 0 < 1.

Answer to Hint 1: For equal length, the smaller integer is the lexicographically smaller string (because the first position where they differ is the highest bit).

So you want the lexicographically smallest string you can obtain (padding with leading zeros is allowed only as part of the current string; after operations the length may change).

Ignore SHRINK-REVERSE for a moment. A SWAP lets you move any bit to any position. With only swaps and a fixed multiset of 0s and 1s, what arrangement minimizes the value?

Where should all the 0s sit relative to the 1s?

Answer to Hint 3: You can permute the bits arbitrarily, so the minimum is all 0s first, then all 1s (any other arrangement has a 1 to the left of some 0, which increases the value).

If there are $c$ ones, that optimal shape is $n-c$ zeros followed by $c$ ones.

Still swaps-only: you have a budget of at most $k$ swaps. You cannot necessarily reach the fully sorted string $0^{n-c}1^c$ if $k$ is small.

A useful greedy: repeatedly move a 1 to the right using a swap with a 0, using as many operations as you have. One standard way is: scan left to right; whenever you see a 1, swap it with the rightmost 0 you can still reach within your remaining budget (as in the model solution’s first loop).

Why does pushing 1s to the right help minimize the binary value?

Answer to Hint 5: Bits on the left contribute larger powers of two. Moving a 1 right trades a 1 out of a high bit for a 0 in that position, which strictly decreases the integer (as long as you swap with a 0 to the right).

So the swap-only phase is: spend swaps to push ones rightward until you run out or everything is already as far right as possible.

Now add SHRINK-REVERSE: delete all leading zeros, then reverse the whole string.

After deleting leading zeros, the first character is 1 (unless the string becomes empty — the statement guarantees at least one 1 in the input, and you should track how that interacts with your reasoning). Reversing then changes which positions are 0/1 in a non-local way.

For the overall solution, it turns out you only need to consider at most one SHRINK-REVERSE in combination with your swap budget (and an optional reverse of the entire string first as a modeling trick for “which orientation of $s$ you shrink-reverse”). The model program checks a constant number of cases: enough swap-only greedy, then work(k-2) on the original $s$, then reverse(s) and work(k-1).

Don’t worry about proving the full classification here; focus on what work(k) is trying to compute: the best string achievable if the shrink-reverse–type step has already been aligned with that case, using the remaining swap budget $k$ inside work.

Inside work(k), let $c$ be the number of 1s in the current string $s$ (fixed for that call). You have $k$ swaps left to manipulate $s$ before you “read off” the result.

Let $$\text{need} = \max(1,; c - k).$$

Interpretation: each swap can pair with moving a 1 across a 0, but a short intuitive bound is: you cannot gather the ones into an arbitrarily tight block if you have too few swaps; $\text{need}$ is the minimum number of ones that must appear inside any contiguous window of a certain length in the final construction this branch is optimizing for.

Next hint makes $\text{need}$ concrete via positions of ones.

Let $p_0 < p_1 < \cdots < p_{c-1}$ be the indices of 1s in $s$.

For any integer $m \ge 1$, the shortest contiguous segment of $s$ that contains $m$ ones has length $$\min_{j = m-1}^{c-1} \bigl(p_j - p_{j-(m-1)} + 1\bigr).$$

Set $m = \text{need}$ and call this minimum len.

• If len \le c, the model solution replaces the candidate with the global sorted string $0^{n-c}1^c$ (the swaps-only optimum for that multiset). Intuition: the ones are not “too spread out” for that branch to still reach the fully sorted arrangement under the budget.

• If len > c, you cannot reach $0^{n-c}1^c$ with that branch’s budget; the best you can do is tied to a contiguous substring of $s$ of length exactly len that contains at least $\text{need}$ ones, chosen to be lexicographically smallest among such substrings.

So you must find the lexicographically smallest binary string among all contiguous substrings of $s$ of length len that contain at least $\text{need}$ ones.

Let $\text{pref}[i]$ be the prefix sum of 1s. A substring $s[i..i+\text{len}-1]$ qualifies iff $$\text{pref}[i+\text{len}] - \text{pref}[i] \ge \text{need}.$$

Among all qualifying $i$, you want the smallest substring in lex order. For two substrings of the same length, lex order equals comparing the suffixes $s[i..]$ only up to length len, i.e. compare $s[i..i+\text{len}-1]$ as strings.

Key idea: Sort starting indices $i$ by the suffix $s[i..]$ (standard suffix order). The first index $i$ in that order that satisfies the prefix-sum test gives the lexicographically smallest qualifying length-len substring.

That is exactly why the model solution iterates i in suffix-array order and returns on the first hit.

Naive suffix array (no doubling, no Kasai — fine for reasoning / small $n$):

• For each start position $i \in {0,\dots,n-1}$, you have a suffix $s[i..n-1]$.

• Compare two suffixes $i$ and $j$ by scanning $t = 0,1,2,\dots$ until $i+t$ or $j+t$ is out of range or $s[i+t] \ne s[j+t]$; then the smaller character wins (or the shorter suffix if one ends).

• Build an array idx = [0,1,...,n-1] and sort idx with that comparator. This is $O(n^2 \log n)$ time in the worst case for binary strings (each compare $O(n)$).

That sorted idx is a perfectly valid suffix array for the qualitative algorithm “iterate $i$ in suffix order”. The model’s SuffixArray class is the same order, computed in $O(n \log n)$ or $O(n)$ instead.

You do not need the LCP array for this problem’s loop unless you optimize further; the model builds lc but the decision “first valid $i$ in SA order” uses only sa.

After you take ans = s.substr(i, len) for the chosen i, the model runs a second loop over ans (right to left) that spends any remaining swap budget exactly as written in model_sol.cpp, then sets ans = std::string(n - len, '0') + ans and does t = std::min(t, ans).

When you implement or debug, keep this post-processing identical to the reference; the ideas you need to internalize for the problem are need, len, and suffix order for picking i. Finer points of why the outer main splits into work(k-2) / reversed work(k-1) pair best with a full editorial proof.

Putting the outer main together: Start from the swap-only greedy result in t (Hints 5–6). Then consider the few discrete cases implemented in the model: work(k-2) on the original $s$, and reverse(s) plus work(k-1). Take the lexicographically smallest t across those branches.

Why compare with std::min on strings? For the same final length $n$, lex order matches integer order; the construction keeps a fixed length $n$ for the final binary string before converting to the answer modulo $10^9+7$.

Modulo $10^9+7$: Interpret the final binary string t as an integer: value $= \sum_i t_i \cdot 2^{n-1-i}$. Compute it with modular arithmetic (the model uses MInt).

The statement reminds you: minimize the true integer, not the remainder; but if the lexicographically smallest length-$n$ string is unique among feasible outcomes, that string is the true minimum, and its remainder is what you print.