One-Use Switch

Let $M=N-1$, and let $T_i$ be the time when switch $i$ is operated. Record only the relative order of adjacent switches:

$$\varepsilon_i= \begin{cases} \uparrow,&T_i<T_{i+1},\\ \downarrow,&T_i>T_{i+1}. \end{cases}$$

Two complete orders with the same sign sequence differ only by swaps of disjoint switches, so they have the same result and cost. Conversely, orienting the edges of a path never creates a directed cycle, so every sign sequence is realizable.

Add virtual signs $\varepsilon_0=\downarrow$ and $\varepsilon_M=\uparrow$. For switch $i$, define

$$p_i=\max\{j<i:\varepsilon_j=\downarrow\},\qquad q_i=\min\{j\geq i:\varepsilon_j=\uparrow\}.$$

The two original cards seen by switch $i$ started at positions $p_i+1$ and $q_i+1$. Thus this switch costs money exactly when .

While deciding signs from left to right, an open descending run shares one future right card: the card immediately to the right of the next upward sign. Its exact position is unnecessary; only its color $0$ or $1$ matters.

Maintain four DP values:

• $U_c$: no descending run is open, and the next switch's left original card has color $c$.
• $D_z$: a descending run is open, assuming its common future right card has color $$.

At switch $i$, let $a=S_i$ and $b=S_{i+1}$. Choosing an upward sign sends to with cost , and sends to with cost . Choosing a downward sign sends to each with cost , and sends to itself with cost .

Initialize $U_{S_1}=0$. At the last real switch, allow only the upward transition to implement the virtual final sign. The answer is $\min(U_0,U_1)$. The time complexity is and the extra memory excluding the input string is .

Solution written by GPT5