Juju and Binary String (Codeforces 1658F)
Tags: Greedy, brute force

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:  $$$\sum\limits_{i=1}^k (r_i - l_i + 1) = m$$$;  The cuteness of $$$s[l_1,r_1]+s[l_2,r_2]+\ldots+s[l_k,r_k]$$$ is equal to the cuteness of $$$s$$$, where $$$s[x, y]$$$ denotes the subsegment $$$s_x s_{x+1} \ldots s_y$$$, and $$$+$$$ denotes string concatenation. 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$$$.

Input: 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$$$.

Output: 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.

Note: 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.

Sample Inputs:
4
4 2
0011
8 6
11000011
4 3
0101
5 5
11111

Sample Outputs:
1
2 3
2
2 3
5 8
-1
1
1 5

Solution (Python):
import sys
from calendar import c
import math
t = int(input())
for _ in range(0, t):
    (n, m) = [int(i) for i in input().split()]
    s = input()
    p = [0 for i in range(n + 1)]
    for i in range(0, n):
        p[i + 1] = p[i] + (s[i] == '1')
    k = p[n]
    c = k * m
    if c % n != 0:
        print('-1')
        continue
    c /= n
    sol = -1
    for i in range(0, n - m + 1):
        if p[i + m] - p[i] == c:
            sol = i
            break
    if sol != -1:
        print(1)
        print('{} {}'.format(sol + 1, sol + m))
        continue
    for i in range(0, m + 1):
        if p[i + (n - m)] - p[i] == k - c:
            sol = i
    if sol != -1:
        print(2)
        print('{} {}'.format(1, sol))
        print('{} {}'.format(sol + 1 + n - m, n))

Solution (Python):
from calendar import c
import sys
import math
T = int(input())
for _ in range(T):
    (n, m) = [int(i) for i in input().split()]
    s = input()
    pref = [0 for i in range(n + 1)]
    for i in range(n):
        pref[i + 1] = pref[i] + (s[i] == '1')
    k = pref[n]
    c = k * m
    if c % n != 0:
        print('-1')
        continue
    c /= n
    res = -1
    for i in range(n - m + 1):
        if pref[i + m] - pref[i] == c:
            res = i
            break
    if res != -1:
        print(1)
        print('{} {}'.format(res + 1, res + m))
        continue
    for i in range(m + 1):
        if pref[i + (n - m)] - pref[i] == k - c:
            res = i
    if res != -1:
        print(2)
        print('{} {}'.format(1, res))
        print('{} {}'.format(res + 1 + n - m, n))

Solution (Python):
from calendar import c
import sys
import math
T = int(input())
for _ in range(T):
    (n, m) = [int(i) for i in input().split()]
    s = input()
    pref = [0 for i in range(n + 1)]
    for i in range(n):
        pref[i + 1] = pref[i] + (s[i] == '1')
    k = pref[n]
    c = k * m
    if c % n != 0:
        print('-1')
        continue
    c /= n
    res = -1
    for i in range(n - m + 1):
        if pref[i + m] - pref[i] == c:
            res = i
            break
    if res != -1:
        print(1)
        print('{} {}'.format(res + 1, res + m))
        continue
    for i in range(m + 1):
        if pref[i + (n - m)] - pref[i] == k - c:
            res = i
    if res != -1:
        print(2)
        print('{} {}'.format(1, res))
        print('{} {}'.format(res + 1 + n - m, n))