Seqüência de caracteres binária satisfazer várias restrições

Question

Estou tentando resolver este problema, mas sem sucesso.

Problema:Você é dado uma string binária onde alguns dos bits são substituídos por ?.Você também terá vários intervalos [$l_i$, $r_i$] ($l_i < r_i$).Encontrar uma seqüência de caracteres binária S com ? substituído por 0 ou 1, tal que, em cada intervalo [a,$l$, $r$], s[$l..r$] inclui 0 e 1.

Exemplo:

Dada a seqüência de caracteres 00?11 e o intervalo [2, 3], a seqüência de caracteres 00111 satisfaz os requisitos, como S[2..3]=01 incluem tanto 0 e 1.

No entanto, a seqüência de caracteres 00?11 e os intervalos [2, 3] e [3, 4] não pode ser resolvido, como o ? teria que ser 0 e 1.

Os limites são |S|,Q<=1e5

Eu tentei usar gananciosos, mas ele está dando resposta errada para este caso: 0??0, [1, 3], [2, 3] e [3, 4], como o algoritmo ganancioso iria tentar 0??0 -> 01?0 -> 0100 -> falhar, ainda existe uma solução (0010).

Eu tentei remover completamente a sobreposição de intervalos (como em [1, 3] e [2, 3]), mas há outros casos em que achei que não.O que seria uma solução correta?

Obrigado.

Answer 1

Existem 4 tipos de intervalos:

1. Intervalos contendo $0$ e $1$ (e.g. 00?11?).Tais intervalos são já satisfeitas, e nós simplesmente ignorá-los.

2. Intervalos, o que não pode ser satisfeita:qualquer um comprimento de 1 (e.g. 0, ?), ou conter apenas 0's ou 1's (e.g. 000, 111).Se um intervalo de existir, o relatório "não há soluções".

3. Intervalos que consistem apenas 0 ou apenas 1 e ter um único ? (e.g. 00?0, 1?).Para tais intervalos, nós sabemos o que ? deve ser, de modo que acabamos de criar ?, que , satisfazendo o intervalo, e ignorar o intervalo, a partir de agora.

4. Intervalos, o que tem mais do que um ?.Vamos falar sobre elas mais tarde.

A primeira fase do algoritmo, é livrar-se dos Tipos 1, 2, 3.Observe que, quando nos satisfazer um intervalo do Tipo 3, outros intervalos, pode alterar o seu Tipo.

while (true) {
    Remove all intervals of Type 1
    Check that there are no intervals of Type 2
    if (there exists an interval of Type 3) {
        Satisfy and remove this interval
    } else {
        break
    }
}

Como resultado, apenas os intervalos do Tipo 4 permanecem.Cada intervalo tem dois ?.Em particular, que abrange os dois consecutivos restante ?'s.Portanto, é suficiente para atribuir aos restantes ?'s valores 0, 1, 0, 1, 0, 1, ..., da esquerda para a direita.

---

Agora, o algoritmo eficiente para a primeira fase.Nós processamos todos os intervalos em ordem crescente de suas extremidades direita.Mantemos um conjunto de intervalos de $T_4$ (inicialmente vazia) de actualmente encontrou Tipo 4 intervalos, classificados por sua extremidade esquerda.

Para cada novo intervalo, dependendo do tipo, vamos fazer o seguinte:

• Tipo 1:Ignorá-la

• Tipo 2:Retornar "não há soluções"

• Tipo 4:Adicionar um intervalo em $T_4$.

• Tipo 3:Satisfazê-la.Agora podemos olhar para a direita intervalo $I$ no $T_4$ (i.é.com o maior ponta esquerda).Se ele mudou o seu tipo de removê-lo a partir de $T_4$ e processá-lo novamente (i.e.verifique seu tipo e aplicar a ação correspondente, a partir desta lista).Caso contrário, não faça nada:desde $I$ não modificar o seu tipo, outros intervalos $T_4$ também não alterar o seu tipo.

  De fato, deixar $I'$ ser outro intervalo de $T_4$.Se $I \subseteq eu'$, estamos bem (se $I$ tem dois ?, e , em seguida, $I'$, que contém $I$, também os tem).Deixe $i$ ser a posição dos fixo ?.Se $i > direito de(I')$, então nós estamos bem.Caso contrário, temos $i \le direito de(I') < direito de(I)$.Mas observe que não há nenhuma ? entre $direito de(I')$ e $direito de(I)$:caso contrário, o processado atualmente intervalo de não ser do Tipo 3, uma vez que ele tem pelo menos dois ?'s.Portanto, $I \cap I'$ tem, pelo menos, dois ?'s e, portanto, $I'$ muito.

Durante o processamento do Tipo 3, encontramos mais à direita do intervalo de $I$ no $T_4$ até $T_4$ está vazio ou $I$ não alterar o seu tipo.Simplificando, podemos remover intervalos de $S$ enquanto há intervalos, o que alterar o seu tipo.