Let us reverse \(S\) beforehand. We will call strings in the form 101010... good.

Let us take out from \(S\) its longest good subsequence. Obviously, the length of this subsequence is the upper limit of the greatest integer initially written on the blackboard. Let us generalize this fact.

Consider repeating the operation above. That is, we will keep taking out from \(S\) its longest good subsequence and then erasing its elements from \(S\) until \(S\) becomes empty. For example, if \(S=\)1110001101, we will take out the following: 10101, 101, and 10.

Let \(l_1 \geq l_2 \geq \cdots \geq l_n\) be the lengths of the subsequences taken out in this way. Then, let \(x_1 \geq x_2 \geq \cdots \geq x_m\) be the integers initially written on the blackboard. We can first see that it is necessary that \(\sum l_i = \sum x_i\). Also, for every \(i\) (\(1 \leq i \leq m\)), both of the following need to hold:

• \(\sum_{j=1}^{i} \lceil l_j/2 \rceil \geq \sum_{j=1}^{i} \lceil x_j/2 \rceil\) (Restriction of the number of 1 in the first \(i\) elements)
• \(\sum_{j=1}^{i} \lfloor l_j/2 \rfloor \geq \sum_{j=1}^{i} \lfloor x_j/2 \rfloor\) (Restriction of the number of 0 in the first \(i\) elements)

This can be shown as follows. Consider the following problem: take out \(i\) distinct good subsequences from \(S\) so that the number of 0 (or 1) contained in those subsequences is maximized. We can see that the optimal strategy here is the greedy one stated above - taking out the longest good subsequences one by one. Thus, the necessary condition above is shown.

It turns out that this necessary condition is also sufficient (proof will be given later), which enables us to use DP to solve the problem. Let us decide the values in \(x\) in descending order. We can use the following as the state in DP: (length of sequence, last element, \(\sum \lceil x_i/2 \rceil\), \(\sum \lfloor x_i/2 \rfloor\)). Since we only need to consider \(O(|S|\log|S|)\) combinations for (length of sequence, last element), there are \(O(|S|^3\log |S|)\) states. We can compute the transition faster with prefix sums, which makes the total required time \(O(|S|^3\log |S|)\).

We will now show that the necessary condition above is sufficient. First, let us show the following lemma:

Lemma: Let \(a\) and \(b (|a| \leq |b|)\) be two good strings, possibly empty. For every string \(w\) resulting from merging \(a\) and \(b\) (like in merge sort), \(w\) can be decomposed into two good strings \(c\) and \(d\) such that:

• \(|a| \leq |c| \leq |d| \leq |b|\)
• The total numbers of 0 and 1 are kept the same, that is, \(\lceil |a|/2 \rceil + \lceil |b|/2 \rceil = \lceil |c|/2 \rceil + \lceil |d|/2 \rceil\) and \(\lfloor |a|/2 \rfloor + \lfloor |b|/2 \rfloor = \lfloor |c|/2 \rfloor + \lfloor |d|/2 \rfloor\) hold.

For example, if \(a=\)10 and \(b=\)10101, \(w\) can be 1010110 or 1101001 or something else, but in any case, it can be decomposed into \(c=\)101 and \(d=\)1010.

This can be shown as follows. Let us take out from \(w\) its longest good subsequence and call that subsequence \(p\). Also, let us erase \(p\) from \(w\) and call what remains \(q\). Then, \(q\) is a good string (otherwise, it would contradict the premise of \(w\) being decomposable into two good strings). Obviously, \(|b| \leq |p|\). Here, if we assume that \(p\) is taken out from \(w\) in the greedy strategy stated above, and observe the way the elements corresponding to \(p\) and \(q\) line up in \(w\), we can show that \(c\) and \(d\) can be obtained by rearranging these elements properly. (Details omitted, but it is just case analysis.)

Now, we just need to convert \(l \rightarrow x\) by repeatedly applying this lemma. Obviously, \(n \leq m\), so we assume \(n=m\) by appending \(0\)s at the end of \(l\).

Below, we will show a procedure to convert \(l\) to \(x\). During the procedure, the following always holds for every \(i\): \(\sum_{j=1}^{i} \lceil l_j/2 \rceil \geq \sum_{j=1}^{i} \lceil x_j/2 \rceil\) and \(\sum_{j=1}^{i} \lfloor l_j/2 \rfloor \geq \sum_{j=1}^{i} \lfloor x_j/2 \rfloor\). Note that, however, \(l\) may cease to be monotonically non-increasing in the middle of the procedure.

• Find \(i\) such that \(l_i < x_i\). If there is no such \(i\), \(l=x\).
• If there exists \(j\) such that \(j<i,l_j \geq x_j+2\): Since \(l_i < x_i \leq x_j \leq l_j - 2\), apply the lemma and replace \(l_j,l_i\) with \(l_j-2,l_i+2\), respectively.
• If there is no such \(j\): There always exists \(j\) such that \(j<i, l_j = x_j+1, l_j \neq l_i \mod 2\). Otherwise, the number of 0 or 1 in the first \(i\) elements in \(l\) would be strictly smaller than that in \(x\), which would contradict the premise. Since \(l_i < x_i \leq x_j \leq l_j - 1\), apply the lemma and replace \(l_j,l_i\) with \(l_j-1,l_i+1\), respectively.

Obviously, this procedure halts in a finite number of steps. Thus, the necessity is shown.