Palindrome Flipping

The clean way to do this is to avoid fighting $s$ and $t$ directly.

Instead, solve this smaller problem:

Given any binary string $x$ of length $n$, turn it into $0^n$ using at most $n$ valid operations.

Then the original problem is basically dead.

If we can reduce $s$ to $0^n$, and we can reduce $t$ to $0^n$, then:

1. apply the operations for $s \to 0^n$;
2. apply the operations for $t \to 0^n$ in reverse order.

Why does reversing work? Because an operation flips a palindrome substring. The complement of a palindrome is still a palindrome, so the same operation is valid backwards too. Nice little symmetry; no dark magic required.

That gives at most $n+n=2n$ operations.

Reducing one string to all zeroes

Suppose the current string has two equal adjacent characters at positions $p$ and $p+1$.

Then we have an all-equal block:

$$[L,R]=[p,p+1].$$

The key invariant is:

The whole block $[L,R]$ consists of one repeated bit value.

That means $x_{L..R}$ is definitely a palindrome, so flipping the whole block is always a valid operation.

Now grow this block until it covers the entire string.

To grow to the right, look at $x_{R+1}$:

• If $x_{R+1}=value$, just set $R\leftarrow R+1$.
• If $x_{R+1}\ne value$, flip the current block $[L,R]$. Since the block was all equal, after flipping it becomes all the opposite bit, which now equals $x_{R+1}$. Then set $R\leftarrow R+1$.

Same exact thing works to the left:

• If $x_{L-1}=value$, just set $L\leftarrow L-1$.
• If $x_{L-1}\ne value$, flip the current block first, then expand left.

Each expansion adds one new character to the block and uses at most one operation. Starting from length $2$, we need exactly $n-2$ expansions. After the block covers the whole string, the string is either $0^n$ or $1^n$. If it is $1^n$, flip the whole string once.

So if we already had an equal adjacent pair, the number of operations is at most

$$(n-2)+1=n-1.$$

What if the string is alternating?

If there is no equal adjacent pair, the string is strictly alternating.

Since $n\ge 4$, the first three characters are either 010 or 101, both palindromes. Flip positions $1..3$.

Example:

• 0101... becomes 1011..., so positions $3$ and $4$ are equal.
• 1010... becomes 0100..., same deal.

Now we have an equal adjacent pair at positions $3$ and $4$, so we run the block-growing method.

This costs one extra operation, so the total is at most

$$1+(n-2)+1=n.$$

Putting it together

For each test case:

1. Generate operations reducing s to all zeroes.
2. Generate operations reducing t to all zeroes.
3. Output the first list, then the reverse of the second list.

There is no impossible case for the given constraints. The problem statement allows printing -1, but here it’s basically a decoy button.

The implementation directly simulates flips because $n\le 100$, so keeping the string accurate is simple and hard to screw up.

Complexity per test case is $O(n^2)$ from naive substring flips, easily fine.