Make Good

Core idea

Use a parity invariant. Positions are 1-indexed. Define

$D = \#\texttt{(}\text{ on odd positions} - \#\texttt{(}\text{ on even positions}$.

Every operation flips two adjacent equal brackets. Adjacent positions have opposite parity. If we flip (( into )), we remove one opening bracket from an odd position and one from an even position. If we flip )) into ((, we add one opening bracket to each side. Either way, the difference $D$ stays unchanged.

This is stronger than just saying the number of ( keeps the same parity. That weaker invariant misses dumb cases like )(: it has one opening bracket, but it is obviously stuck and not regular. The parity split is the part that actually matters.

Which $D$ values can a regular sequence have?

Let $n=2m$. If $n$ is odd, stop immediately: no regular bracket sequence has odd length.

Now look at any regular bracket sequence of length $2m$:

• position $1$ must be (, and it is odd;
• position $2m$ must be ), and it is even;
• total number of opening brackets is exactly $m$.

Let $q$ be the number of opening brackets on even positions. Then the number of opening brackets on odd positions is $m-q$, so

$D = (m-q)-q = m-2q$.

Also, the last position is even and must be ), so not all $m$ even positions can be opening brackets. Therefore

$0 \le q \le m-1$.

So a target exists only if

$q = \frac{m-D}{2}$

is an integer and $0 \le q \le m-1$.

Why this is sufficient

The invariant is not just necessary; it fully characterizes reachability for what we need.

Here is the key local trick. On any length-3 block whose two ends differ, two operations can swap those ends while leaving the middle character alone:

(() -> ))) -> )((

()) -> ((( -> ))(

The other two cases are symmetric. This means we can swap neighboring positions inside the odd-position subsequence, and also inside the even-position subsequence. Adjacent swaps let us permute each parity however we want.

After that, suppose two strings have the same $D$. If one has too many opening brackets on odd positions, it has the same excess on even positions too, because the difference is fixed. We can permute positions so an odd ( and an even ( become adjacent, then flip (( to )). Similarly, if we need more opens, put two adjacent ) together and flip them to ((.

So any string with invariant $D$ can reach any other string with the same $D$. We do not need to print the operations, thankfully, because that would be extra nonsense.

Constructing the answer

Once $q=(m-D)/2$ is valid, build this sequence:

( + $q$ copies of () + ) + $(m-q-1)$ copies of ()

Example with $m=4, q=2$:

(()())()

This is always regular:

• the first ( opens an outer layer;
• the $q$ internal () pairs never break balance;
• the following ) closes the outer layer;
• the remaining suffix is just independent () pairs.

It has exactly $q$ opening brackets on even positions, so its invariant is exactly $m-2q=D$. Since it has the same invariant as the input, it is reachable.

Algorithm

For each test case:

1. If $n$ is odd, print -1.
2. Compute $D$ from the input string.
3. Let $m=n/2$ and $q=(m-D)/2$.
4. If $q$ is not an integer or not in $[0,m-1]$, print -1.
5. Otherwise print (, then $q$ copies of (), then ), then $m-q-1$ copies of ().

Complexity: $O(n)$ per test case, and $O(1)$ extra memory besides the output string.