Problema A - Triângulos de Pascal


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

Problema:
Dada uma grelha de concorrentes, composta pelos caracteres 'C' ou 'P', qual é o tamanho do maior triângulo existente na grelha composto exclusivamente por caracteres 'P'?

Restrições:
1 ≤ L, C ≤ 1 500.

Ao longo desta análise considerarei, sem perda de generalidade, matrizes quadradas de lado N (L = C = N).


Ponto prévio:
Lidar com as 4 orientações possíveis dos triângulos complica as abordagens e pode levar-nos a cometer erros facilmente. Assim, é preferível lidar com uma das 4 orientações e rodar a matriz em 90 graus 3 vezes. Desta forma teremos a certeza de encontrar o triângulo de tamanho máximo apesar de só verificarmos uma das orientações possíveis.


Solução base:
Para cada 'P' da matriz, verificar qual é o triângulo maior a que este 'P' pertence.

Esta seria uma solução O(N^5) que daria aproximadamente 40 pontos.


Solução base - optimização:

Assumindo que se escolheu o layout mostrado na figura acima para os triângulos, para cada 'P' da matriz, poderia verificar-se apenas é o maior triângulo existente que tem esse 'P' como canto inferior esquerdo.

Deste modo, para cada 'P' numa posição (i,j), a ideia seria testar os tamanhos de triângulos 1,2,3, ..., enquanto formam triângulos válidos pois se o triângulo de tamanho 4 é inválido, é impossível um triângulo maior ser válido tendo (i,j) como canto inferior esquerdo.

Esta seria uma solução O(N^4) que daria aproximadamente 50 pontos.


Somas acumuladas

Uma outra solução possível seria processar cada célula (i, j) da matriz e verificar todos os triângulos possíveis cujo vértice superior é (i, j). Processando linha a linha, de i para baixo, é necessário saber se existem 'P's consecutivos suficientes para formar o triângulo. Para saber este passo, pode-se usar programação dinâmica para em cada linha da matriz para saber o número de 'P's entre 2 colunas dessa linha.

Esta abordagem processa as N^2 células da matriz e, para cada uma delas, pode efectuar no máximo N iterações para testar os N tamanhos possíveis. Assim, o tempo de execução seria O(N^3) que daria aproximadamente 75 pontos.


Programação Dinâmica - outra estratégia
Voltando à solução base, pode-se optar por outra estratégia de pesquisa.
Continuando a considerar (i,j) como o canto inferior esquerdo do triângulo, o maior triângulo está limitado pelo maior triângulo existente acima (cujo canto inferior esquerdo é (i-1, j+1)) e pelo número de 'P's consecutivos a partir de j. Assim, pode-se construir duas matrizes:

Construindo a matriz dp de cima para baixo, da esquerda para a direita, cada posição da matriz é actualizada em tempo O(1) (constante).
Esta abordagem teria um tempo de execução total O(N^2) que seria merecedora dos 100 pontos.


Ligações interessantes: