Deformed Balance

Research note: I used the official Codeforces statement at https://codeforces.com/problemset/problem/2206/M and the official ICPC APAC problem analysis PDF at https://apac26.icpc.tw/assets/championship/2026/problemset-analysis.pdf. The official analysis gives the state-machine direction; the details below fill in the missing algebra.

Write L for ( and R for ). A string $W$ has a deformed balance exactly when this scan succeeds:

• Start at $(x,y)=(0,0)$.
• $x$ is the usual parenthesis depth.
• $y$ is the depth of the hidden bracket sequence created by the deformed grammar.
• Both $x$ and $y$ must stay nonnegative.
• At the end, we need $(x,y)=(1,0)$, because $W+R$ must be a usual balanced string.

The transitions are:

$$R: (x,y) \to (x-1,y)$$

and

$$L: \begin{cases} (x,y) \to (x+1,y+1), & x+y \equiv 0 \pmod 2,\\ (x,y) \to (x+1,y-1), & x+y \equiv 1 \pmod 2. \end{cases}$$

Why parity? Reading R flips the direction of the hidden brackets, while reading L keeps it. So $x+y \bmod 2$ is the current direction. That is the entire grammar compressed into two integers. Nice, for once.

Now suppose some prefix $X$ leaves us at $(x_0,y_0)$ with parity $p=(x_0+y_0)\bmod 2$. When we scan the fixed string $S$:

$$x' = x_0 + a,$$

where

$$a = \#L - \#R.$$

The change in $y$ depends only on the starting parity $p$. Let that change be $b_p$:

$$y' = y_0 + b_p.$$

During the scan of $S$, we also need both coordinates to never go negative. Therefore $x_0$ and $y_0$ only need to satisfy lower bounds:

$$x_0 \ge A, \qquad y_0 \ge B_p.$$

We compute $A$ from the minimum usual prefix balance of $S$.

For $y$, scan $S$ once assuming starting parity $0$. Let $v$ be the current hidden-depth change, and let $\min v$, $\max v$ be its minimum and maximum over prefixes. Starting parity $1$ just flips all signs, so:

$$b_0=v, \quad B_0=-\min v,$$ $$b_1=-v, \quad B_1=\max v.$$

Clamp the bounds at $0$.

Next, we need the shortest suffix from a state $(x,y)$ to $(1,0)$. Count how many future Ls are read in even parity; call that number $e$. A lower-bound calculation gives:

$$|Y| = x+2y+4e-1.$$

Usually we can make $e=0$, giving

$$|Y| = x+2y-1.$$

The only time $e=0$ is impossible is when $x=0$ and $y$ is even: we cannot read R, and the next L is forced to be an even-parity L. Then $e=1$, so

$$|Y| = 3+2y.$$

Now handle the prefix. For a prefix $X$, let $f$ be the number of Ls read when $x+y$ is even. Check the effect of every transition on

$$|X|+x+2y.$$

An even-parity L increases it by $4$. An odd-parity L and an R increase it by $0$. Therefore:

$$|X|+x+2y = 4f.$$

So for a non-exceptional suffix, total added length is

$$4f + a + 2b_p - 1.$$

If the state after $X+S$ is $(0,\text{even})$, add $4$.

All that remains is finding the minimum feasible $f$ for each starting parity.

For parity $1$, one R is optimal, so it is enough to consider

$$X=L^fRL^g.$$

This reaches

$$(x,y)=(f+g-1, f-g), \qquad 0 \le g \le f.$$

We need $x\ge A$ and $y\ge B_1$, so such a $g$ exists iff

$$f\ge B_1, \qquad 2f\ge A+B_1+1.$$

Also $f\ge 1$. Thus

$$f_1=\max\left(1, B_1, \left\lceil\frac{A+B_1+1}{2}\right\rceil\right).$$

For parity $0$, either use no R:

$$X=L^f \Rightarrow (x,y)=(f,f),$$

requiring

$$f\ge \max(A,B_0),$$

or use two Rs:

$$X=L^fRL^gR \Rightarrow (x,y)=(f+g-2, f-g).$$

This is feasible iff

$$f\ge B_0, \qquad 2f\ge A+B_0+2, \qquad f\ge 1.$$

So

$$f_0=\min\left(\max(A,B_0),\ \max\left(1,B_0,\left\lceil\frac{A+B_0+2}{2}\right\rceil\right)\right).$$

More Rs cannot improve the minimum $f$: for the same number of even-parity Ls, extra Rs only reduce $x+y$, making lower bounds harder to satisfy. That is the key false assumption to kill: complicated prefixes look scarier, not better.

For each parity, we test $f$ and $f+1$. Testing $f+1$ cleanly handles the exceptional suffix case, because increasing $f$ costs exactly $4$, the same as the exception penalty.

The implementation directly checks whether the feasible interval of $g$ contains a non-exceptional state. If the interval has more than one value, it definitely does, since $x+a=0$ can hold for at most one $g$.

Complexity is $O(n)$ per test case, and $O(1)$ extra memory besides the input string. With total $n\le 10^6$, this is comfortably fine.