Problema B - Constelação Retangular

Tipo de problema: Geometria
Autor do Problema: Pedro Ribeiro (DCC/FCUP)

Problema:
Dadas as coordenadas inteiras de N estrelas, a tua tarefa é descobrir qual é o maior número de estrelas que se conseguem colocar no contorno de um único retângulo com dois lados verticais e dois lados horizontais.

Restrições:
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Solução Base:
A solução mais simples de todas passa por primeiro construir uma lista ordenada de linhas e uma lista ordenada de colunas. Por lista ordenada significa que uma linha com coordenada y menor que outra vem primeiro na lista. Para cada linha/coluna temos uma lista de pontos (só precisamos de uma coordenada) que estão presentes nessa lista/coluna. Agora para obter a resposta basta considerar cada conjunto de 2 linhas mais 2 colunas, que equivale a 4 ciclos encadeados, e para cada par de 2 linhas mais 2 colunas contamos o número de pontos nesse retângulo (notem que o retângulo não equivale à soma dos pontos em cada linha/coluna, pois há pontos que ficam de fora, ver estrelas a vermelho na imagem a seguir).

Se considerarmos o número de linhas/colunas como K, temos que a solução vai depender deste valor. Notem que este valor depende do valor das coordenadas máximas (pois não pode haver mais linhas que o valor das coordenadas máximas).

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

Solução Melhor:
Uma ideia interessante para remover a contagem de pontos seria recorrer a somas acumuladas. Neste caso vamos considerar somas acumuladas entre linhas/colunas. Consideremos duas matrizes, lsums[i₁][i₂] e csums[j₁][j₂], que representam, respetivamente, o número de pontos na linha i₁ desde a coluna 0 à i₂ e o número de pontos na coluna j₁ desde a linha 0 à j₂ (estamos a considerar que a lista começa em 0). Sem perda de generalidade vamos calcular a matriz de somas apenas para as linhas (as colunas são análogas).

Para calcular cada valor de lsums[i₁][i₂] é necessário primeiro considerar cada linha i₁. Depois, para cada linha i₁, temos que o valor de list[i₁][i₂] = list[i₁][i₂ - 1] + <número de pontos na coluna i₂ e na linha i₁> (este último valor pode ser guardado numa matriz à parte aquando do processamento do input, mas pode inclusivé ser guardado na própria matriz list[][]).

Tendo estas matrizes calcular a soma de pontos em qualquer retângulo torna-se fácil, considerando que temos as linhas l₁ e l₂ e as colunas c₁ e c₁, a soma de estrelas é igual a: (lsums[l₁][c₂] - lsums[l₁][c₁ - 1]) + (lsums[l₂][c₂] - lsums[l₂][c₁ - 1]) + (csums[c₁][l₂] - csums[c₁][l₁ - 1]) + (csums[c₂][l₂] - csums[c₂][l₁]) (cuidado com os casos extremos, quando por exemplo c/l = 0).

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

Solução Ótima:
A solução ótima não é muito diferente da anterior. Considerando que temos as mesmas matrizes de somas acumuladas, o truque é perceber como fixando duas linhas, ir apenas buscar as melhores duas colunas nesse intervalo. Sendo assim a solução passa por primeiro contruir uma matriz M[o], que representa o max(<número de estrelas na coluna i entre as duas linhas fixadas> + <número de estrelas à esquerda da coluna i para cada uma das linhas fixadas>) [todos estes valores são calculados usando as matrizes de somas acumuladas], com i a variar entre o e o número máximo de colunas (o que significa que esta matriz é construida da direita para a esquerda).

Tendo a matriz M[o] calculada, agora basta fazer um ciclo desde a coluna 0 até à última coluna e para cada coluna i temos que o retângulo máximo é aquele que tem o valor máximo para colunas à direita de i, que corresponde ao valor de M[i + 1] ("+1" pois não inclui a própria coluna). Sendo assim, o valor para essa coluna é: M[i + 1] + <número de estrelas na coluna i entre as duas linhas fixadas> - <número de estrelas à esquerda da coluna i para cada uma das linhas fixadas> (retiramos o último valor pois só queremos as estrelas entre a coluna i e a coluna ótima e no cálculo de M[] para essa coluna adicionamos a mais, para aproveitar a matriz de somas acumuladas). Notem que esta solução assume que as linhas e colunas estão ordenadas como previsto na solução base. É também necessário cuidado com casos onde só há uma coluna ou só uma linha.

Como para cada duas linhas só temos um ciclo encadeado, então a solução melhora por um fator de K.

Esta seria uma solução O(K ^ 3) que daria aproximadamente 100 pontos.

Ligações interessantes:

• Somas Acumuladas na Wikipedia.