Hard Cut
Contest: Codeforces Round 792 (Div. 1 + Div. 2)
Difficulty rating: 3400
Tags: constructive algorithms, dfs and similar, divide and conquer, math

You are given a binary string $$$s$$$. You have to cut it into any number of non-intersecting substrings, so that the sum of binary integers denoted by these substrings is a power of 2. Each element of $$$s$$$ should be in exactly one substring.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). Description of the test cases follows.

Each test case contains a binary string $$$s$$$ ($$$1 \le |s| \le 10^6$$$).

It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case output the answer to the problem as follows:

- If the answer does not exist, output $$$-1$$$.
- If the answer exists, firstly output an integer $$$k$$$ — the number of substrings in the answer. After that output $$$k$$$ non-intersecting substrings, for $$$i$$$-th substring output two integers $$$l_i, r_i$$$ ($$$1 \le l_i, r_i \le |s|$$$) — the description of $$$i$$$-th substring.

If there are multiple valid solutions, you can output any of them.

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

Note:
In the first test case it is impossible to cut the string into substrings, so that the sum is a power of 2.

In the second test case such cut is valid:

- $$$011_2 = 3_{10}$$$,
- $$$0_2 = 0_{10}$$$,
- $$$1_2 = 1_{10}$$$.

Example input:
4
00000
01101
0111011001011
000111100111110

Example output:
-1

3
1 3
4 4
5 5

8
1 2
3 3
4 4
5 6
7 7
8 10
11 12
13 13

5
1 5
6 7
8 11
12 14
15 15

Editorial:
Let's say that there are $$$k$$$ ones in the given string.
We will build the answer for all $$$k > 0$$$. $$$k = 0$$$ is the only case when the answer does not exist.
$$$k = 1$$$, $$$k = 2$$$, $$$k = 4$$$ — cut into single digits.
$$$k = 3$$$ — described later.
Let's consider $$$k = 5$$$:
If all ones are in a row, then we should cut them into $$$1111_2 + 1_2 = 16_{10}$$$.
Else there will be either $$$101_2$$$ or $$$100_2$$$ and the other part of the string may be cut into single digits so the sum will be $$$8_{10}$$$.
Now let's consider $$$k > 5$$$ (here we will also consider $$$k = 3$$$):
Let's describe the function $$$solve(l, r, k, n)$$$ for cutting the susbtring from $$$l$$$ to $$$r$$$ with $$$k$$$ ones to get the sum $$$n$$$.
• Let's use the "divide and conquer" technique: we have a string with $$$k$$$ ones and we want to get the sum $$$n = 2^{\left \lceil \log_2(k)\right \rceil}$$$, and for big enough $$$k$$$ we can just cut the whole string into two substrings with almost equal number of ones, run the algorithm for them and get the sum $$$2^{\left \lceil \log_2(\left \lfloor k/2 \right \rfloor)\right \rceil} + 2^{\left \lceil \log_2(\left \lceil k/2 \right \rceil)\right \rceil} = 2^{\left \lceil \log_2(k)\right \rceil} = n$$$. Now let's show how to make such cut for all strings that have from $$$6$$$ to $$$11$$$ ones and after that for all $$$k \ge 12$$$ we will be able to run the method decribed above.
• $$$k = n$$$Just cut into single digits.
• $$$k < n \le \left \lfloor \frac{3k}{2} \right \rfloor$$$Let's consider the first two ones. If they are consequent then we will cut them into a single substring. It costs us only two ones but it increases the sum by $$$3$$$. If these two ones are not consequent then we will cut out the segments $$$10_2$$$ and $$$1_2$$$. This way we spend two ones again and the sum increases by $$$3$$$ as well. Also it is always possible to cut off a single digit so it is easy to see that we can get any sum $$$n$$$ from $$$k$$$ to $$$\left \lfloor \frac{3k}{2} \right \rfloor$$$. This way we got the answer for $$$k = 6, 7, 8, 11$$$. Now we only need to show how to make the cut for $$$k = 9, 10$$$.
• $$$k = 9$$$Let's consider a substring of length $$$3$$$ that starts in the leftmost one, there are $$$4$$$ possible cases: $$$t = 100$$$, then we need to use $$$k' = 8$$$ ones to get the sum $$$n' = 16_{10} - 100_2 = 12$$$, which we know how to do. $$$t = 101$$$, then we need to use $$$k' = 7$$$ ones to get the sum $$$n' = 11$$$, we will show it in the end. $$$t = 110$$$, then we need to use $$$k'= 7$$$ ones to get the sum $$$n' = 10$$$, which we know how to do. $$$t = 111$$$, then we need to use $$$k' = 6$$$ ones to get the sum $$$n' = 9$$$, which we know how to do.
• $$$t = 100$$$, then we need to use $$$k' = 8$$$ ones to get the sum $$$n' = 16_{10} - 100_2 = 12$$$, which we know how to do.
• $$$t = 101$$$, then we need to use $$$k' = 7$$$ ones to get the sum $$$n' = 11$$$, we will show it in the end.
• $$$t = 110$$$, then we need to use $$$k'= 7$$$ ones to get the sum $$$n' = 10$$$, which we know how to do.
• $$$t = 111$$$, then we need to use $$$k' = 6$$$ ones to get the sum $$$n' = 9$$$, which we know how to do.
• $$$k = 10$$$To do that let's cut a substring with $$$k_1 = 4$$$ ones from the left and get the sum $$$n_1 = 8$$$ and a remaining substring with $$$k_2 = 6$$$ ones and get the sum $$$n_2$$$. We already know how to get the second sum so now there is only $$$k_1 = 4$$$ and $$$n_1 = 8$$$ left.
• Let's consider the last two cases for full solution:$$$k = 4,\, n = 8$$$:Let's do the same thing as we did for $$$k = 9$$$, cut off a substring of length $$$3$$$ that starts from the leftmost one. Then we have two substrings and for both of them we know how to cut them properly.$$$k = 7,\, n = 11$$$:Let's cut off the first four ones and use the previous technique we will get the sum $$$8$$$. The remaining three ones we will use to get the sum $$$3$$$.
This shows how to cut the string for any $$$k > 0$$$.