Quantas operações de inversão de todos os colchetes em uma substring de uma string de colchetes são necessárias para tornar a string 'correta'?

Question

Eu chamo uma sequência de colchetes de 'correta' se cada colchete de abertura tiver um colchete de fechamento correspondente em algum lugar depois dele e cada colchete de fechamento tiver um colchete de abertura correspondente em algum lugar antes dele.Por exemplo

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

é uma string correta e

)()()(

é uma string incorreta.

Uma operação consiste em pegar uma subsequência contígua da string de entrada e 'inverter' todos os colchetes dessa subsequência.

Dada uma sequência arbitrária de colchetes (de comprimento par), a tarefa é encontrar o menor número dessas operações necessárias para alterá-la para uma sequência de colchetes 'correta'.

Outra maneira de analisar esse problema é ter uma sequência de +1s e -1s e tentar encontrar o menor número de operações (de multiplicação de cada número em um intervalo por -1) necessárias para tornar cada prefixo dessa sequência não negativo. e todo sufixo não positivo.

Answer 1

O DP sugerido nos comentários de Yuval Filmus realmente funciona:podemos resolver o problema em $\mathcal{O}(n^{2})$ por DP.

Primeiramente, observe que podemos assumir que os intervalos não podem se sobrepor.Tome quaisquer dois intervalos sobrepostos $[a,b)$ e $[c,d)$.WLOG $a \leq c$.Então podemos substituir os dois intervalos pelos intervalos $[a,c)$ e $[\min(b, d), \max(b, d))$ que não se sobrepõem, têm comprimento total menor e cobrem exatamente os mesmos elementos.

Substitua os colchetes de abertura por $1$, fechando os colchetes com $-1$.Agora o problema corresponde a aplicar o número mínimo de operações "multiplicar intervalo por $-1$" tal que cada prefixo tenha uma soma não negativa e a soma de todo o array seja zero.

Construímos uma solução da esquerda para a direita.Em cada posição podemos iniciar um intervalo ou encerrar um intervalo ativo.

Deixar $DP[m][s][0]$ denotam o número mínimo de intervalos que precisamos usar para que cada soma de prefixo no primeiro $m$ elementos é não negativo, a soma dos primeiros $m$ elementos é $s$, e não temos um intervalo ativo.De forma similar $DP[m][s][1]$ é o mesmo valor onde temos um intervalo ativo.

Se o $m$o valor é $1$, para $0 \leq s \leq m$ montamos

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

Caso contrário, definimos

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

Então terminamos e iniciamos os intervalos, definindo

• $DP[m][s][0] = \min(DP[m][s][0], DP[m][s][1])$
• $DP[m][s][1] = \min(DP[m][s][1], DP[m][s][0] + 1)$

O caso base é $DP[0][0][0] = 0$, $DP[0][0][1] = 1$.

Há $\mathcal{O}(n^{2})$ estados, e nós fazemos $\mathcal{O}(1)$ trabalho para calcular cada um deles, portanto o algoritmo é executado em $\mathcal{O}(n^{2})$.O DP pode ser implementado para usar $\mathcal{O}(n)$ memória armazenando apenas os valores de $DP$ para o atual $m$.

Aqui está uma implementação C++ do 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

Boa pergunta!

Aqui está o problema em termos mais populares.

Parênteses Balanceados

Uma sequência de parênteses é balanceada se pudermos alterá-la para uma sequência vazia removendo as substrings "()" repetidamente.Por exemplo, string vazia, "()" e "(())()((()()))" são balanceadas, mas nenhuma de "())" e ")()()(" é balanceada.

É claro que uma string balanceada deve começar com "(" e terminar com ")".Deve ter comprimento uniforme também.

o problema das operações mínimas para equilibrar uma string

Deixar s ser uma sequência não vazia de parênteses de comprimento n.A única operação que podemos realizar é inverter todos os parênteses em uma substring, ou seja, alterar cada "(" para ")" e cada ")" para "(" para alguns caracteres contíguos na string.O problema é como encontrar o menor número de operações que fazem s equilibrado.

uma abordagem por programação dinâmica

Quais são os subproblemas apropriados?Eles são dp[i][j] para 0 <= i < j < n, onde dp[i][j] é o número mínimo de operações que equilibram a substring entre o índice i e índice j inclusivo.O número mínimo desejado de operações que equilibram s é dp[0][n-1].

Como qualquer corda de comprimento ímpar não pode ser balanceada, restringiremos nossa atenção às cordas de comprimento par de agora em diante.

os casos básicos dp[i][i+1] é 0 se a substring entre i e i+1 é balanceado, ou seja, "()".Caso contrário, é 1.

a relação de recorrênciaUsarei Java para definir a relação de recorrência.

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;
}

A relação de recorrência vem da seguinte propriedade bem conhecida de strings balanceadas.Uma string não vazia é balanceada se e somente se for a concatenação de duas strings balanceadas ou "(" seguida por uma string balanceada seguida de ")".

O processamento antes do for loop, que define min ser dp[i + 1][j - 1] mais 0, 1 ou 2, vem do fato de que "(" seguido por uma string balanceada seguida de ")" deve ser uma string balanceada.

O processamento no for loop, que tenta encolher min para dp[i][k] + dp[k + 1][j] menos 0 ou 1 para alguns k isso é entre i e j, vem do fato de que a concatenação de duas strings balanceadas deve ser uma string balanceada.

A complexidade temporal desta abordagem é $O(n^3)$.A complexidade do espaço é $O(n^2)$.

Comprimento das strings "mais desequilibradas"

O menor comprimento de uma string que não pode ser balanceada por menos de 2 operações é 4.Por exemplo, ")((("

O menor comprimento de uma string que não pode ser balanceada por menos de 3 operações é 10.Por exemplo, ")(((((())("

O menor comprimento de uma string que não pode ser balanceada por menos de 4 operações é 22.Por exemplo, ")(())))(((((((((((())(".

Pergunta:Qual é o menor comprimento de uma string que precisa de pelo menos 5 operações?Como calculei, deve ser maior que 28.No entanto, meu cálculo não é suficiente para determinar o valor real.Quão rápido podemos calcular esses menores comprimentos?