¿Cuántas operaciones para invertir todos los corchetes en una subcadena de una cadena de corchetes se necesitan para que la cadena sea "correcta"?

Question

Llamo a una cadena de corchetes 'correcta' si cada corchete de apertura tiene un corchete de cierre correspondiente en algún lugar después y cada corchete de cierre tiene un corchete de apertura correspondiente en algún lugar antes.Por ejemplo

(())()((()()))

es una cadena correcta y

)()()(

es una cadena incorrecta.

Una operación consiste en tomar una subsecuencia contigua de la cadena de entrada y "voltear" cada paréntesis en esa subsecuencia.

Dada una cadena arbitraria de corchetes (de longitud uniforme), la tarea es encontrar el número más pequeño de operaciones necesarias para cambiarla a una cadena de corchetes "correcta".

Otra forma de ver este problema es tener una cadena de +1 y -1, y tratar de encontrar el menor número de operaciones (de multiplicar cada número en un intervalo por -1) necesarias para hacer que cada prefijo de esta cadena no sea negativo. y cada sufijo no positivo.

Answer 1

El DP sugirió en los comentarios de Yuval Filmus in De hecho, funciona: Podemos resolver el problema en $ \ mathcal {o} (n ^ {2}) $ por Dp

Primera nota de que podemos asumir que los intervalos no se les permite superponerse. Tome los dos intervalos superpuestos $ [a, b) $ y $ [C, D) $ . Wlog $ A \ leq C $ . Luego podemos reemplazar los dos intervalos con los intervalos $ [a, c) $ y $ [\ min (b, d ), \ max (b, d)) $ que no se superponen, tienen una longitud total más corta y cubra exactamente los mismos elementos.

Reemplace los soportes de apertura con $ 1 $ , paréntesis de cierre con $ - 1 $ . Ahora, el problema corresponde a la aplicación del número mínimo de operaciones "Multiplicar el intervalo por $ - 1 $ " de modo que cada prefijo tiene suma no negativa, y la suma sobre toda la matriz es cero.

Construimos una solución a la izquierda a derecha. En cada posición, podemos iniciar un intervalo, o terminar un intervalo activo.

Let $ DP [M] [S] [0] $ Denote el número mínimo de intervalos que debemos usar de manera que cada suma de prefijo en el primer $ M $ Elements no es adivinado, la suma del primer $ m $ elementos es $ s $ , y no tenemos un intervalo activo. De manera similar, $ DP [M] [S] [1] $ es el mismo valor donde tenemos un intervalo activo.

Si el $ m $ th value es $ 1 $ , para $ 0 \ \ leq s \ leq m $ establecimos

• $ dp [m] [s] [s] [0]= DP [M-1] [S-1] [0] $
• $ dp [m] [s] [1]= DP [M-1] [S + 1] [1] $

de lo contrario establecimos

• $ dp [m] [s] [0]= DP [M-1] [S + 1] [0] $
• $ dp [m] [s] [1]= DP [M-1] [S-1] [1] $ .

Luego terminamos y iniciamos intervalos, configuración

• $ dp [m] [s] [0]=min (dp [m] [s] [s] [0], DP [S] [S] [S] [1]) $
• $ dp [m] [s] [s] [1]=min (DP [M] [S] [1], DP [S] [S] [S] [S] [0] + 1) $

El caso base es $ dp [0] [0] [0]= 0 $ , $ dp [0 ] [0] [1]= 1 $ .

Hay $ \ mathcal {o} (n ^ {2}) $ Estados, y hacemos $ \ Mathcal {O} (1) $ Trabajo Para calcular cada uno de ellos, por lo tanto, el algoritmo se ejecuta en $ \ mathcal {o} (n ^ {2}) $ . El DP se puede implementar para usar $ \ mathcal {o} (n) $ memoria solo almacenando los valores de $ dp $ para la actual $ m $ .

Aquí hay una implementación de C ++ del algoritmo.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string str;
    cin >> str;
    int n = str.size();

    vector<int> dp0 = {0}, dp1 = {1};
    for (int m = 1; m <= n; ++m) {
        vector<int> nxt0(m + 1, n + 1), nxt1(m + 1, n + 1);
        for (int i = 0; i < m; ++i) {
            if (str[m-1] == '(') {
                nxt0[i+1] = dp0[i];
                if (i > 0) nxt1[i-1] = dp1[i];
            } else {
                nxt1[i+1] = dp1[i]);
                if (i > 0) nxt0[i-1] = dp0[i];
            }
        }
        dp0 = nxt0;
        dp1 = nxt1;
        for (int i = 0; i <= m; ++i) dp1[i] = min(dp1[i], dp0[i] + 1); // Start interval
        for (int i = 0; i <= m; ++i) dp0[i] = min(dp0[i], dp1[i]); // Stop interval
    }
    cout << dp0[0] << '\n';
}

Answer 2

¡Buena pregunta!

Aquí está el problema en términos más populares.

Paréntesis equilibrados

Una cadena de paréntesis está equilibrada si podemos cambiarla a una cadena vacía eliminando las subcadenas "()" repetidamente.Por ejemplo, la cadena vacía "()" y "(())()((()()))" están equilibradas, pero ninguna de "())" y ")()()(" está equilibrada.

Está claro que una cadena balanceada debe comenzar con "(" y terminar con ")".También debe tener una longitud uniforme.

el problema de las operaciones mínimas para equilibrar una cuerda

Dejar s ser una cadena no vacía de paréntesis de longitud n.La única operación que podemos realizar es invertir cada paréntesis en una subcadena, es decir, cambiar cada "(" a ")" y cada ")" a "(" para algunos caracteres contiguos en la cadena.El problema es cómo encontrar el menor número de operaciones que hagan s equilibrado.

un enfoque por programación dinámica

¿Cuáles son los subproblemas apropiados?Ellos son dp[i][j] para 0 <= i < j < n, dónde dp[i][j] es el número mínimo de operaciones que equilibran la subcadena entre índice i e índice j inclusivo.El número mínimo deseado de operaciones que equilibren s es dp[0][n-1].

Dado que cualquier cadena de longitud impar no puede equilibrarse, de ahora en adelante restringiremos nuestra atención a cadenas de longitud par.

los casos base dp[i][i+1] es 0 si la subcadena entre i y i+1 está equilibrado, es decir, "()".De lo contrario es 1.

la relación de recurrenciaUsaré Java para definir la relación de recurrencia.

void dp(int i, int j) {
    assert 0 <=i && i + 2 < j && j <= L;

    int min = dp[i + 1][j - 1];
    if (s.charAt(i) == ')' && s.charAt(i + 1) == '(') min++;
    if (s.charAt(j) == '(' && s.charAt(j - 1) == ')') min++;

    for (int k = i + 1; k < j - 1; k+=2) {
        if (a[k] == 1 && a[k + 1] == -1) {
            if (min > dp[i][k] + dp[k + 1][j] - 1) {
                min = dp[i][k] + dp[k + 1][j] - 1;
            }
        } else {
            if (min > dp[i][k] + dp[k + 1][j]) {
                min = dp[i][k] + dp[k + 1][j];
            }
        }
    }

    dp[i][j] = min;
}

La relación de recurrencia proviene de la siguiente propiedad bien conocida de las cuerdas balanceadas.Una cadena no vacía está balanceada si y solo si es la concatenación de dos cadenas balanceadas o "(" seguida de una cadena balanceada seguida de ")".

La tramitación ante el for bucle, que establece min ser dp[i + 1][j - 1] más 0, 1 o 2, proviene del hecho de que "(" seguido de una cadena balanceada seguida de ")" debe ser una cadena balanceada.

El procesamiento en el for bucle, que intenta reducirse min a dp[i][k] + dp[k + 1][j] menos 0 o 1 para algunos k eso es entre i y j, proviene del hecho de que la concatenación de dos cadenas balanceadas debe ser una cadena balanceada.

La complejidad temporal de este enfoque es $O(n^3)$.La complejidad espacial es $O(n^2)$.

Longitud de las cuerdas "más desequilibradas"

La longitud más pequeña de una cadena que no puede equilibrarse con menos de 2 operaciones es 4.Por ejemplo, ")((("

La longitud más pequeña de una cadena que no puede equilibrarse con menos de 3 operaciones es 10.Por ejemplo, ")(((((())("

La longitud más pequeña de una cadena que no puede equilibrarse con menos de 4 operaciones es 22.Por ejemplo, ")(())))(((((((((((())(".

Pregunta:¿Cuál es la longitud más pequeña de una cadena que necesita al menos 5 operaciones?Según he calculado, debe ser mayor que 28.Sin embargo, mi cálculo no es suficiente para determinar el valor real.¿Qué tan rápido podemos calcular estas longitudes más pequeñas?