Problema B - Eventos em Cadeia

O Problema

Dado uma cadeia de DNA de tamanho $N$ com os caráteres 'A', 'T' ou '?' calcular o número máximo de sub-sequências 'AT' quando substituimos os '?' por 'A' ou 'T'.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Os casos de teste deste problema estão organizados em 6 grupos com restrições adicionais diferentes:

Solução Base

A forma mais simples de resolver este problema é calcular todas as possíveis cadeias, ou seja, substituir cada '?' por um 'A' e 'T' e calcular o número de sub-sequências 'AT' para cada. Vamos focar-nos na tarefa de calcular o número de sub-sequências 'AT' dada uma cadeia completa (ou seja, sem '?').

Se se recordarem da história das ONI, recentemente houve um problema de qualificação onde o que nos era pedido era exatamente o mesmo de calcular o número de sub-sequências 'AT' dada uma cadeia completa (embora neste problema figurassem carateres diferentes). Para o fazer eficientemente, só precisamos de percorrer a cadeia do início até ao fim e sempre que estivermos num caráter 'T', somamos o número de carateres 'A' que já apareceram até à posição atual. Para sabermos o número de carateres 'A' que já apareceram até à posição atual, basta guardar esse valor numa variável que incrementamos sempre que vemos um 'A'. O código seguinte faz exatamente o pretendido:

int numero_subsequencias(string cadeia) {
  int numero_as = 0; // o contador de 'A's
  int numero_subsequencias = 0; // a resposta

  for (int i = 0; i < int(cadeia.length()); i++) {
    if (cadeia[i] == 'A') // se encontrarmos um 'A' incrementamos o contador
      numero_as++;
    else if (cadeia[i] == 'T') // se encontrarmos um 'T' aumentamos a resposta
      numero_subsequencias += numero_as;
  }

  return numero_subsequencias;
}

Tendo isto, vamos ver como calcular todas as cadeias possíveis. O que queremos fazer é um código recursivo que para cada posição com um '?' tenta colocar um 'A' e um 'T'. Depois de gerarmos uma cadeia completa, basta usarmos a função que vimos acima para saber quantas sub-sequências contém e no fim escolhemos o maior valor que encontrámos. O código seguinte faz exatamente o pretendido:

int valor_maximo = 0;

void calcular_cadeias(string cadeia, int posicao) {
  if (posicao == int(cadeia.length())) { // se ja preenchemos uma cadeia
    valor_maximo = max(valor_maximo, numero_subsequencias(cadedeia));
  }

  if (cadeia[posicao] != '?') // se a posicao atual nao e um '?'
    cacular_cadeias(cadeia, posicao + 1); // continuar sem modificar a cadeia
  else { // se a posicao atual e um '?'
    string cadeia1 = cadeia;
    string cadeia2 = cadeia;
    cadeia1[posicao] = 'A'; // substituir por 'A'
    cadeia2[posicao] = 'T'; // substituir por 'T'
    calcular_cadeias(cadeia1, posicao + 1);
    calcular_cadeias(cadeia1, posicao + 1);
  }
}

int main() {
  // Ler input
  
  calcular_cadeias(cadeia_input, 0);
  
  // Imprimir resposta (a variavel valor_maximo)
  
  return 0;
}

Infelizmente esta solução é muito lenta. Para simplificar a notação, vamos dar um nome ao número de '?' na cadeia original, vamos usar a variável $P$ para esta quantidade. Calcular o número de sub-sequências (o primeiro código) é feito em tempo $O(N)$, mas o número máximo de sub-sequências que podemos gerar pode chegar a $O(2^P)$ (há duas possibilidades por '?'), ou seja, a complexidade desta solução é $O(N \cdot 2^P)$, o que seria suficiente para 30 pontos.

Solução para apenas '?'

Se a cadeia apenas contém '?' então podemos observar que a resposta terá o formato 'A...AT...T', isto é, não há nenhum 'T' antes de um 'A'. É fácil de ver que isto se verifica: se uma cadeia não tem este formato, então há um par 'TA' algures na cadeia, ou seja, a cadeia tem o formato '...TA...'. Se trocarmos o 'A' pelo 'T' e vice versa (ou seja, 'TA' -> 'AT') então o número de sub-sequências 'AT' aumenta em uma unidade. Logo, sempre que uma cadeia tem o formato '...TA...' podemos aumentar o número de sub-sequências 'AT', ou seja, a cadeia ótima não pode ser deste formato.

Com esta observação, podemos calcular a solução para o caso em que apenas há '?' da seguinte forma: vamos considerar as cadeias 'T...T', 'AT...T', 'AAT...T', ou seja, todas as cadeias que respeitam a condição que vimos no parágrafo anterior. Para cada uma podemos usar a função de calcular o número de subsequências que escrevemos na solução anterior, mas isto faria o nosso algoritmo $O(N^2)$, visto que há $N$ cadeias e calcular o número de sub-sequências para cada requer $O(N)$ tempo. Podemos observar que se a nossa cadeia tem $a$ carateres 'A' no início e $t$ carateres 'T' no fim (no formato pretendido) então o número de subsequências é $a \times t$: cada um dos $t$ 'T's pode formar um par com cada um dos $a$ 'A's. Assim, podemos calcular o número de sub-sequências para cada cadeia em tempo $O(1)$ ao manter o número de 'A's e 'T's e aplicar a fórmula. Isto é ilustrado no código seguinte:

int main() {
  // Ler input (vamos assumir que apenas contém '?')
  
  int valor_maximo = 0;
  int a = 0; // comecamos pela string 'T...T'
  int t = int(cadeia_input.length());
  for (int i = 0; i < int(cadeia_input.length()); i++) {
    valor_maximo = max(valor_maximo, a * t); // atualizamos o maximo
    a++; // adicionamos um 'A'
    t--;
  }
  
  // Imprimir resposta (a variavel valor_maximo)
  
  return 0;
}

Como vimos esta solução funciona em tempo $O(N)$, mas só resolve os casos em que só há '?'. Se combinarmos esta solução com a anterior (ou seja, usamos esta quando só há '?' na cadeia original e a outra nos restantes casos) será suficiente para 50 pontos.

Solução alternativa para apenas '?'

Se repararem bem, a resposta para o caso em que temos apenas '?' é sempre $\lfloor N / 2 \rfloor * \lceil N / 2 \rceil$, o que corresponde há cadeia 'A...AT...T', que contém metade 'A's e metade 'T's (caso não seja divisível por dois, tanto faz o caráter que colocamos a mais). Não é difícil ver porquê que isto se verifica, por isso deixamo-lo como um pequeno exercício.

Solução Ótima

Para resolver o casos geral temos de voltar a fazer uma observação sobre a estrutura das cadeias ótimas. Se repararem bem, a observação que fizemos sobre o formato da cadeia ótima também se aplica ao caso em que não temos só '?'. Vamos ver um exemplo, se a nossa cadeia original for 'T?A?TA?A', nunca vale a pena substiuir o primeiro '?' por 'T' e o segundo por 'A', pela mesma razão que se os trocarmos aumentamos o número de sub-sequências em pelo menos uma unidade. Isto aplica-se a qualquer par de '?'s, ou seja, vamos sempre substituir os '?' primeiro por um conjunto de 'A's e depois por um conjunto de 'T's. Para o exemplo dado a solução seria 'TAAATATA', onde substituimos os primeiros dois '?' por 'A' e o restante por 'T' (notem que 'TAATTATA' tem o mesmo número de sub-sequências e por isso também seria uma solução).

Sendo assim a solução vai ser muito idêntica à anterior, mas infelizmente a nossa fórmula para o número de subsequências já não funciona da mesma forma. O número de sub-sequências pode ser dividido em dois termos que são somados: número de sub-sequências que apenas usam 'A' e 'T' originais (ou seja, que não foram substituidos por '?'); número de sub-sequências que usam pelo menos um caráter substituido. Notem que o primeiro termo é igual para todas as cadeias, por isso podemos calculá-lo inicialmente em $O(N)$ (usando, por exemplo, a função que obtivemos na primeira solução, mas ignorando os '?'). Agora resta-nos contar o restante.

Para o fazer vamos gerar cada cadeia uma a uma, começando pela cadeia que onde substituimos todos os '?'s por 'A's. O objetivo desta solução será substuir cada 'A' por 'T', um a um do fim para o início da cadeia, atualizando a contagem de sub-sequências após cada mudança. Começamos por contar o número de sub-sequências para a cadeia inicial (onde substituimos todos os '?'s por 'A's), o que é fácil em $O(N)$ usando o método que já vimos várias vezes. Agora quando trocamos o último 'A' por um 'T' temos de subtrair a contribuição que o 'A' tinha para o número de sub-sequências e adicionar a contribuição do 'T'. A contribuição do 'A' é igual ao número de 'T's desde a posição que estamos a trocar até ao fim da cadeia. A contribuição do 'T' é igual ao número de 'A's desde a posição que estamos a trocar até ao início da cadeia. Se percorremos a cadeia do fim para o início, podemos manter duas variáveis: uma com a contagem de 'T's do fim até onde estamos e uma com a contagem de 'A's do início até onde estamos. Quando vemos um 'T' incrementamos a primeira e quando vemos um 'A' decrementamos a segunda. Quando chegamos a uma posição onde havia um '?' atualizamos a contagem de sub-sequências usando a fórmula referida e assim obtemos a contagem de sub-sequências para todas as cadeias no formato da observação que fizemos no início.

Concluímos que a complexidade desta solução é $O(N)$, o que seria suficiente para os 100 pontos.