Final ONI 2005: Problema A - Futebol

Já estão apurados os finalistas das Olimpíadas de Informática 2014. A final é já na próxima semana :)

Mas hoje vou continuar a análise dos problemas que tenho vindo a fazer. Começo a final de 2005, ano do meu 12º, com o problema A - Futebol.

Neste problema, é-nos dada a dimensão de um terreno rectangular com Y linhas e X colunas (1 ≤ Y, X ≤ 1000). Em cada célula do mapa existe relva ou uma árvore. Queremos construir um campo de futebol com L linhas e C colunas. Em que posição do mapa devemos construir o campo, de modo a termos de cortar o mínimo de árvores possível?

Exemplo do enunciado: mapa com 5 linhas e 8 colunas, para um campo de futebol 2x3 basta cortar 1 árvore

Análise

 O problema tem um enunciado simples e também tem uma abordagem natural: para cada célula do mapa, contar o número de árvores existentes no rectângulo LxC em que um dos cantos é essa célula.

Podemos transformar o mapa dado numa matriz de 0s e 1s, onde 0 = relva e 1 = árvore. Simplificando, este abordagem seria algo do género:

1 2 3 4 5 6 7 8 9

for (i = L-1; i < Y; i++) for (j = C-1; j < X; j++) { // (i, j) é o canto superior direito int soma = 0; for (k = 0; k < L; k++) for (p = 0; p < C; p++) soma += mapa[i - k][j - p]; if (soma < minimo) minimo = soma; }

Bastante simples e funciona. Contudo, temos 4 ciclos encadeados. Y, X, L e C podem ter valores até 1000, por isso esta abordagem seria O(1000⁴), o que é demasiado ineficiente.

Dificilmente podemos deixar de testar cada célula do mapa. Isso tem logo uma complexidade de O(1000²), por isso, temos de tentar contar o número de árvores no rectângulo LxC de forma eficiente.

Uma forma de fazer isso é recorrer a uma técnica muito comum a que podemos chamar matriz de somas. Isto é, construímos uma matriz de dimensões iguais ao mapa dado onde cada posição (i, j) da matriz contém o número (ou soma) de árvores existentes no rectângulo que vai de (0, 0) a (i, j).

Matriz de somas para o mapa apresentado na figura anterior

A figura acima apresenta a matriz de somas para o mapa do exemplo anterior. A célula na linha 3, coluna 2, contém o número de árvores contidas no rectângulo a verde, ou seja, desde a célula (0, 0).

Posto isto, como descobrir o número de árvores para um rectângulo de dimensões LxC? E.g. o rectângulo apresentado na figura abaixo (i = 3, j = 5)

A posição (3, 5) tem o valor 10, ou seja, existem 10 árvores desde (0, 0) até (3, 5).

Como só queremos o rectângulo de dimensão 2x3 de (2, 3) a (3, 5), temos de subtrair o rectângulo a vermelho claro de (0, 0) a (1, 5)

Assim como o rectângulo a azul de (0, 0) a (3, 2)

No entanto, como se pode ver nas duas figuras anteriores, o rectângulo a amarelo, de (0, 0) a (1, 2) foi subtraído duas vezes, por isso, temos de somar uma vez o seu número de árvores.

Assim o valor do rectângulo 2x3 é soma[3][5] - soma[1][5] - soma[3][2] + soma[1][2] = 10 - 5 - 6 + 2 = 1 (verdade como se pode ver na primeira figura, com o mapa de árvores, onde este rectângulo está com fundo cinzento).

De modo geral, o número de árvores de um rectângulo LxC é igual a soma[i-L][j] - soma[i][j-C] + soma[i-L][j-C].

Faltou dizer como calcular a matriz de somas de forma eficiente. Podemos seguir um raciocínio semelhante, com soma e subtracção de rectângulos.
Isto é, soma[i][j] = soma[i-1][j] + soma[i][j-1] - soma[i-1][j-1]. Deixo a explicação desta fórmula como exercício para o leitor (como foi dito, basta seguir um raciocínio como o anterior).

Complexidade do algoritmo
A matriz de somas pode ser pré-calculada em O(Y*X) pela formula apresentada acima. Para cada célula, fazemos uma soma e uma subtracção.

Usando a fórmula para determinar o número de árvores num rectângulo LxC, podemos saber este número em O(1) graças à matriz de somas. É apenas uma subtracção e uma soma.

Deste modo, o algoritmo passa da complexidade temporal O(1000⁴) para O(Y*X) ou O(1000²). O mapa e a matriz de somas requerem O(Y*X) de espaço em memória, o que é perfeitamente aceitável (~4 mb de memória). Assim, esta abordagem seria merecedora dos 100 pontos :)