Qingshan Loves Strings 2 (Codeforces 1889A)
Tags: Greedy, constructive algorithms

Qingshan has a string $$$s$$$ which only contains $$$\texttt{0}$$$ and $$$\texttt{1}$$$.A string $$$a$$$ of length $$$k$$$ is good if and only if  $$$a_i \ne a_{k-i+1}$$$ for all $$$i=1,2,\ldots,k$$$. For Div. 2 contestants, note that this condition is different from the condition in problem B.For example, $$$\texttt{10}$$$, $$$\texttt{1010}$$$, $$$\texttt{111000}$$$ are good, while $$$\texttt{11}$$$, $$$\texttt{101}$$$, $$$\texttt{001}$$$, $$$\texttt{001100}$$$ are not good.Qingshan wants to make $$$s$$$ good. To do this, she can do the following operation at most $$$300$$$ times (possibly, zero):   insert $$$\texttt{01}$$$ to any position of $$$s$$$ (getting a new $$$s$$$). Please tell Qingshan if it is possible to make $$$s$$$ good. If it is possible, print a sequence of operations that makes $$$s$$$ good.

Input: The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 100$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n\le 100$$$) — the length of string $$$s$$$, respectively.The second line of each test case contains a string $$$s$$$ with length $$$n$$$.It is guaranteed that $$$s$$$ only consists of $$$\texttt{0}$$$ and $$$\texttt{1}$$$.

Output: For each test case, if it impossible to make $$$s$$$ good, output $$$-1$$$.Otherwise, output $$$p$$$ ($$$0 \le p \le 300$$$) — the number of operations, in the first line.Then, output $$$p$$$ integers in the second line. The $$$i$$$-th integer should be an index $$$x_i$$$ ($$$0 \le x_i \le n+2i-2$$$) — the position where you want to insert $$$\texttt{01}$$$ in the current $$$s$$$. If $$$x_i=0$$$, you insert $$$\texttt{01}$$$ at the beginning of $$$s$$$. Otherwise, you insert $$$\texttt{01}$$$ immediately after the $$$x_i$$$-th character of $$$s$$$.We can show that under the constraints in this problem, if an answer exists, there is always an answer that requires at most $$$300$$$ operations.

Note: In the first test case, you can do zero operations and get $$$s=\texttt{01}$$$, which is good.Another valid solution is to do one operation: (the inserted $$$\texttt{01}$$$ is underlined)  $$$\texttt{0}\underline{\texttt{01}}\texttt{1}$$$ and get $$$s = \texttt{0011}$$$, which is good.In the second and the third test case, it is impossible to make $$$s$$$ good.In the fourth test case, you can do two operations:  $$$\texttt{001110}\underline{\texttt{01}}$$$  $$$\texttt{0011100}\underline{\texttt{01}}\texttt{1}$$$ and get $$$s = \texttt{0011100011}$$$, which is good.

Sample Inputs:
6
2
01
3
000
4
1111
6
001110
10
0111001100
3
001

Sample Outputs:
0

-1
-1
2
6 7
1
10
-1

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input()))
    if n % 2 or a.count(0) != n // 2:
        print(-1)
        continue
    (l, r) = (0, n - 1)
    ans = []
    while l < r:
        if a[l] != a[r]:
            l += 1
            r -= 1
        elif a[l] == 0:
            r += 1
            a.insert(r, 0)
            a.insert(r + 1, 1)
            l += 1
            ans.append(r)
        else:
            a.insert(l, 1)
            a.insert(l, 0)
            l += 1
            r += 1
            ans.append(l - 1)
    print(len(ans))
    print(*ans)

Solution (Python):
import sys
from collections import *
data = []
t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    if s.count('1') != s.count('0'):
        print(-1)
        continue
    i = 0
    j = n - 1
    ans = []
    ''
    q = deque((c for c in s))
    i = 0
    j = n - 1
    while i <= j:
        if q[0] != q[-1]:
            i += 1
            j -= 1
            q.pop()
            q.popleft()
        elif q[0] == '0':
            q.append('0')
            q.popleft()
            ans.append(j + 1)
            j += 2
            i += 1
            j -= 1
        else:
            q.appendleft('1')
            q.pop()
            ans.append(i)
            j += 2
            i += 1
            j -= 1
    print(len(ans))
    print(' '.join(map(str, ans)))

Solution (Python):
from collections import Counter
t = int(input())
for _ in range(t):
    n = int(input())
    arr = list(input())
    cnt = Counter(arr)
    arr = [''] + arr
    if n % 2 == 1 or cnt['0'] != n / 2:
        print('-1')
        continue
    ans = []
    (i, j) = (1, n)
    while i < j:
        if arr[i] != arr[j]:
            i += 1
            j -= 1
            continue
        if arr[i] == '1':
            arr.insert(i, '0')
            arr.insert(i + 1, '1')
            ans.append(str(i - 1))
        else:
            arr.insert(j + 1, '0')
            arr.insert(j + 2, '1')
            ans.append(str(j))
        j = j + 2
    print(len(ans))
    print(' '.join(ans))