|
|
Problema C - Apagando Letras |
Tipo de problema: Programação Dinâmica
Autor do Problema: Pedro Ribeiro (DCC/FCUP)
O Problema
Dadas duas palavras, a tua tarefa é determinar qual a melhor
pontuação possível de obter numa sequência de deletes que
transforma a primeira na segunda palavra. A pontuação de cada
delete é igual à soma das distâncias entre a letra apagada e as
duas letras adjacentes.
Restrições
São garantidos os seguintes limites em todos os casos de teste que
irão ser colocados ao programa:
| 1 ≤ T2 < T1 ≤ 500 | Tamanho das palavras |
Solução Base:
A solução mais simples a considerar requer que pensemos em como
funciona o problema. A ideia é ir retirando letras à primeira
palavra até chegar à segunda. Usando uma função recursiva que
recebe dois parâmetros: uma string e um número. A string
representa a palavra que temos neste momento e o número a
pontuação que obtivemos para chegar a essa string. Agora basta
eliminar cada letra dessa string individualmente, contar a nova
pontuação e fazer uma chamada recursiva com esses novos
valores. Quando a string que temos for igual à segunda palavra
temos uma solução parcial, ou seja, temos de encontrar o máximo
destas
Esta seria uma solução fatorial que daria aproximadamente 40 pontos.
Solução Especial:
Para este passo intermédio vamos considerar os casos onde o
tamanho da segunda palavra é 1. Neste caso apenas nos temos de
preocupar em descobrir a melhor maneira de eliminar tudo até
cada letra igual à letra da segunda palavra e depois dessa
letra. Para isto vamos recorrer a uma solução com Programação
Dinâmica. Para isto vamos considerar uma
matriz remDP[i][j] que representa a melhor maneira de
remover todos os caracteres entre i e j
exclusivé. Para calcular este valor, basta reparar
que remDP[i][j] = max(remDP[i][k] + remDP[k][j] + cost(i, k,
j)), com k a variar entre i e j,
exclusivé. O valor da função custo é de considerar que retiramos
a letra na posição k que tem à sua esquerda a letra na
posição i e à sua direita a letra na
posição j. Reparem que estamos a assumir que os índicies
da palavra começam em 1, pois queremos as soluções que apagam
também o primeiro caracter.
Para perceber porque é que isto funciona basta imaginar o problema ao contrário, a ideia é inserir letras e não remover, que é equivalente. Assim, no cálculo da matriz consideramos todos os índices k intermédios e inserimos essa letra, depois é só adicionar a inserção para cada uma das metades restantes da palavra. É importante a ordem pela qual se constroí a matriz (se for feito de uma maneira Bottom-Up), porque é preciso construir primeiro os remDP[i][j] onde j - i = 1, depois = 2 e por aí fora.
Esta seria uma solução O(N ^ 3) que daria aproximadamente 70 pontos (se para os casos onde T2 é maior que 1 usarmos a solução base).
Solução Ótima:
Para finalmente resolvermos o problema é preciso extender a
solução anterior. Considerando que temos a
matriz remDP[i][j] construida, vamos fazer uma segunda
matriz de Programação Dinâmica que aproveita estes valores. A
ideia é construir uma matriz matDP[i][j] que representa a
melhor solução para a palavra 1 até ao caracter i e da
palavra 2 até ao caracter j. A recorrência é simples,
temos dois casos: se o caracter i da palavra 1 for igual
ao j da palavra 2, então podemos considerar todas as
letras k desde i - 1 a 0 e procurar uma letra que
seja igual ao caracter a seguir a j (que é j - 1)
e remove todas as letras nesse intervalo, a solução para este
caso é asssim: max(remDP[k][i] + matDP[k][j - 1])
[atenção aos limites nas matrizes, o objetivo não é eliminar o
caracter i, é mantê-lo]. Caso os caracteres forem
diferentes (notem que também é preciso testar estas soluções
para o caso em que os caracteres são iguais, pois só porque são
iguais não significam que fazem parte da solução), a recorrência
é semelhante, mas torna-se apenas encontrar o próximo caracter
na palavra 1 que seja igual ao caracter de índice j na
palavra 2 e remover todos os caracteres desde esse caracter
até i (inclusivé), logo fica: max(remDP[k][i + 1] +
mDP[k][j]) [reparem que aqui já temos i + 1 na
primeira matriz, pois queremos discartar o caracter i].
É apenas preciso testar atenção aos casos extremos, como o j = 0, mas fora isso a solução é simplesmente mat[T1][T2].
Esta seria uma solução O(N ^ 3) que daria aproximadamente 100 pontos.
Ligações interessantes: