Tipo de problema: Geometria
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.
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[i1][i2] e csums[j1][j2], que representam, respetivamente, o número de pontos na linha i1 desde a coluna 0 à i2 e o número de pontos na coluna j1 desde a linha 0 à j2 (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[i1][i2] é necessário primeiro considerar cada linha i1. Depois, para cada linha i1, temos que o valor de list[i1][i2] = list[i1][i2 - 1] + <número de pontos na coluna i2 e na linha i1> (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 l1 e l2 e as colunas c1 e c1, a soma de estrelas é igual a: (lsums[l1][c2] - lsums[l1][c1 - 1]) + (lsums[l2][c2] - lsums[l2][c1 - 1]) + (csums[c1][l2] - csums[c1][l1 - 1]) + (csums[c2][l2] - csums[c2][l1]) (cuidado com os casos extremos, quando por exemplo c/l = 0).
Esta seria uma solução O(K ^ 4) que daria aproximadamente 60 pontos.
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.