Problema C - Saltitando


Tipo de problema: Programação Dinâmica
Autor do Problema: Pedro Ribeiro (DCC/FCUP)

Problema:
Dado um número inteiro K e uma sequência de N números inteiros positivos, qual é a maior soma possível, seleccionando números da sequência, por ordem, espaçados no máximo por K posições e alternando o sinal dos números seleccionados.

Restrições:
1 ≤ K ≤ 1 000 000
1 ≤ N ≤ 1 000 000
1 ≤ Vi ≤ 1 000


Solução base:

Gerar todas as sequências de saltos possíveis recursivamente e guardar a melhor soma encontrada. Existe um número exponencial de sequências possíveis, assim, esta abordagem daria aproximadamente 40 pontos.


Programação Dinâmica - versão base:
À medida que todas as hipóteses são exploradas, há caminhos que estão a ser recalculados sistematicamente.

Visto que só é possível andar para a frente, a partir de uma posição i da sequência, sabendo se o passo dado é com a perna esquerda (valor negativo) ou direita (positivo), o resultado vai ser sempre o mesmo. Assim basta calcular esses valores uma única vez e guardá-los.

Isto é o mesmo que dizer para usar Programação Dinâmica. Quando é dado um passo com a perna direita, é necessário saber qual é a melhor posição para saltar com a perna esquerda e vice-versa. Assumindo que se calculam os valores de trás para a frente, a tabela é calculada com a fórmula:

seq[i] 7 14 8 2 19 20 17 13 4 8 5
dir[i] 29 36 30 7 20 24 21 17 1 8 5
esq[i] 29 16 16 22 5 1 0 -5 4 -3 -5

Esta abordagem, implementada de forma directa com 2 ciclos encadeados (i e j), teria uma complexidade O(N*K) e daria cerca de 60 pontos.


Programação Dinâmica - O(N*K) -> O(N log K)
A abordagem anterior processa cada elemento da sequência uma vez e, para cada elemento, processa os K elementos seguintes nos arrays esq e dir para calcular o valor máximo nesse intervalo.

Processar cada elemento pelo menos uma vez é obrigatório (factor O(N)). No entanto, é possível melhorar o passo para encontrar os máximos. Para cada i, só interessa uma "janela" de tamanho K: [i+1, i+K]. À medida que os i são processados (e.g. da direita para a esquerda), esta janela também se "desloca" da mesma forma. Assim, usando uma Fila de Prioridade (Priority Queue) ou uma Árvore Balanceada de Pesquisa (Binary Search Tree), é possível determinar o máximo dos K valores contidos na janela actual em O(log K). Quando o processamento do elemento i termina, o elemento i+K é retirado da janela e é inserido o elemento na posição i que acabou de ser calculado.

Para cada uma das N posições são feitas consultas, remoções e inserções nas estruturas de dados referidas. Como estas operações são realizadas em O(log K), esta abordagem teria um tempo de execução total de O(N log K), suficiente para obter cerca de 80 pontos.


Programação Dinâmica em O(N)
No entanto, é possível ir mais longe e retirar o factor O(log K), mesmo sem estruturas de dados rebuscadas. Tome-se como exemplo a sequência descrita na figura abaixo:

Como se pode ver na figura, a ideia base é processar a sequência de números (e.g. neste exemplo é feito da esquerda para a direita) e manter uma lista de números ordenada de forma decrescente, retirando desta lista os números estão fora da "janela" actual.

Cada número é inserido 1 vez nesta janela. Durante a inserção na lista, o número ou é colocado no fim da lista ou descarta elementos que são menores ou iguais a este. Assim, O tempo deste processamento extra é para toda a sequencia é O(N), logo o tempo de execução total desta solução é O(N+N) = O(N), sendo merecedor dos 100 pontos.


Ligações interessantes: