Codeforces Round 779 (Div. 2) |
---|
Finished |
The cuteness of a binary string is the number of $$$\texttt{1}$$$s divided by the length of the string. For example, the cuteness of $$$\texttt{01101}$$$ is $$$\frac{3}{5}$$$.
Juju has a binary string $$$s$$$ of length $$$n$$$. She wants to choose some non-intersecting subsegments of $$$s$$$ such that their concatenation has length $$$m$$$ and it has the same cuteness as the string $$$s$$$.
More specifically, she wants to find two arrays $$$l$$$ and $$$r$$$ of equal length $$$k$$$ such that $$$1 \leq l_1 \leq r_1 < l_2 \leq r_2 < \ldots < l_k \leq r_k \leq n$$$, and also:
Juju does not like splitting the string into many parts, so she also wants to minimize the value of $$$k$$$. Find the minimum value of $$$k$$$ such that there exist $$$l$$$ and $$$r$$$ that satisfy the constraints above or determine that it is impossible to find such $$$l$$$ and $$$r$$$ for any $$$k$$$.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq m \leq n \leq 2 \cdot 10^5$$$).
The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, if there is no valid pair of $$$l$$$ and $$$r$$$, print $$$-1$$$.
Otherwise, print $$$k + 1$$$ lines.
In the first line, print a number $$$k$$$ ($$$1 \leq k \leq m$$$) — the minimum number of subsegments required.
Then print $$$k$$$ lines, the $$$i$$$-th should contain $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$) — the range of the $$$i$$$-th subsegment. Note that you should output the subsegments such that the inequality $$$l_1 \leq r_1 < l_2 \leq r_2 < \ldots < l_k \leq r_k$$$ is true.
44 200118 6110000114 301015 511111
1 2 3 2 2 3 5 8 -1 1 1 5
In the first example, the cuteness of $$$\texttt{0011}$$$ is the same as the cuteness of $$$\texttt{01}$$$.
In the second example, the cuteness of $$$\texttt{11000011}$$$ is $$$\frac{1}{2}$$$ and there is no subsegment of size $$$6$$$ with the same cuteness. So we must use $$$2$$$ disjoint subsegments $$$\texttt{10}$$$ and $$$\texttt{0011}$$$.
In the third example, there are $$$8$$$ ways to split the string such that $$$\sum\limits_{i=1}^k (r_i - l_i + 1) = 3$$$ but none of them has the same cuteness as $$$\texttt{0101}$$$.
In the last example, we don't have to split the string.
Name |
---|