Problema B - Publicidade via Satélite

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

Problema:
Dada uma matriz contendo pontos, qual o maior losango que podemos colocar de modo a não sobrepor qualquer dos pontos existentes?

Restrições:
1 <= L, C <= 1000. (Matriz com tamanho máximo 1000x1000)

Ao longo da análise considerarei, sem qualquer perda de generalidade, matrizes quadradas de lado N.

Solução base:
Para cada losango, verificar se existe algum ponto no seu interior.
Guardar o maior losango que respeita esta condição.


Uma solução como a apresentada possui complexidade O(N^5), e como facilmente se descobre com um pouco de matemática, consegue passar no tempo enquanto o tamanho da matriz for inferior a aproximadamente 40.

De facto, sendo o tamanho da nossa matriz tão limitado, qualquer solução que percorresse todos os losangos e verificasse todos os pontos no seu interior obteria os mesmos 50 pontos.

Crescer o losango:
Depois de olhar para a solução anterior é evidente que não necessitamos de verificar todos os losangos.

Se percorrermos os losangos por uma determinada ordem, assim que um losango falhar sabemos que todos os losangos que contenham este losango falharão também.


Esta solução tem complexidade O(N^4), e mais uma vez descobrimos que consegue passar no tempo enquanto o tamanho da matriz for inferior a aproximadamente 100.

Simplificar o problema:
Por vezes olhamos para um problema e pensamos: "se este detalhe fosse alterado, era tudo muito mais fácil!".
Neste problema, aposto que gostavam muito mais de trabalhar com quadrados do que com losangos.
E se rodássemos o nosso mapa? As duas soluções mais eficientes exigiam que fizessemos esta operação.

Imaginemos a seguinte matriz 3x4, com o losango B-EFG-J marcado.
Preenchi o resto das células com letras para ajudar a visualização. 

 

 


  
1 
2 
3 
4 



 
1 
A 
B 
C 
D 

 

 
2 
E 
F 
G 
H 

 
 


3 
I 
J 
K 
L
Rodada, ficamos com uma matriz 6x6 (linhas+colunas-1). Algumas das células não obtém correspondência na matriz anterior, pelo que podemos deixá-las vazias. 
 

 


  
1 
2 
3 
4 
5 
6  



 
1 
. 
. 
. 
D
. 
.

 

 
2 
. 
. 
C 
.
H
.

 

 
3 
. 
B 
. 
G
. 
L

 

 
4 
A 
. 
F 
.
K 
.

 

 
5 
. 
E 
. 
J
. 
.

 

 
6 
. 
. 
I 
.
. 
.

Como podem observar, os losangos da matriz transformam-se em quadrados com esta transformação.
Podemos obter facilmente a posição de cada célula pela seguinte fórmula:

nova linha = linha antiga + C - coluna antiga, sendo C o número de colunas.
nova coluna = linha antiga + coluna antiga - 1

Somas acumuladas:

Matriz original: 

 

 

 
  
1 
2 
3 
4 
5 
6 

 

 
1 
A  
. 
. 
. 
A  
. 

 

 
2 
. 
. 
. 
A  
. 
. 

 

 
3 
. 
. 
. 
. 
A  
. 

 

 
4 
. 
. 
. 
. 
. 
. 

 

 
5 
. 
. 
. 
. 
A  
. 

 

 
6 
A  
. 
. 
. 
. 
A

Matriz resultante: 

 

 

 
  
1 
2 
3 
4 
5 
6 

 

 
1 
1  
1 
1 
1 
2  
2 

 

 
2 
1 
1 
1 
2  
3 
3 

 

 
3 
1 
1 
1 
2 
4  
4 

 

 
4 
1 
1 
1 
2 
4 
4 

 

 
5 
1 
1 
1 
2 
5  
5 

 

 
6 
2  
2 
2 
3 
6 
7

A matriz de somas acumuladas permite-nos descobrir se existe alguma árvore em qualquer sub-rectângulo em tempo constante! O(1)

Por exemplo, para calcular o número de árvores no rectângulo entre (3, 2) e (5, 5):

m[5][5] - m[2][5] - m[5][1] + m[2][1]

Usar a matriz:

Sabendo que os losangos se transformam sempre em quadrados nesta matriz, podemos muito facilmente verificar:

Obtemos assim uma solução O(N^3).

Eliminar quadrados desnecessários

Na realidade não necessitamos de testar todos os quadrados. Mais especificamente, não necessitamos de testar quadrados cujo tamanho seja inferior ao tamanho do maior quadrado já encontrado.

Desta forma, guardando a informação relativa ao melhor quadrado até ao momento, conseguimos só testar quadrados maiores, passando a nossa solução a ter uma complexidade O(N^2), merecedora dos 100 pontos!

Ligações interessantes: