PKU 2332 - One is good, but two is better

Autor da análise: raphael_ribasraphael_ribas

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2332

Resumo

É dado uma matriz que contém 0's, 1's e 2's. O objetivo é cobrir todos os 2's com dois retângulos sem cobrir nenhum 1 e que a área total coberta seja mínima. Os retângulos podem se sobrepor.

Solução

A solução desse problema é bem direta, não envolve nenhum algoritmo muito complicado.

A estratégia adotada é gerar (quase) todas as soluções possíveis e escolher a melhor. Mas o número de soluções possíveis é muito grande ($N^4 M^4$) e queremos reduzir um pouco. Para isso vamos fazer algumas observações. Por enquanto, vamos deixar de lado a existência dos 1's.

Primeiro, uma vez que foi escolhido o primeiro retângulo, de todos os retângulos que cobrem os 2's não cobertos, só estamos interessados no menor deles. Por sorte, tal retângulo pode ser encontrado de forma gulosa. Agora só precisamos testar $N^2 M^2$ soluções.

A segunda observação é a seguinte. Seja $j$ o menor índice de uma coluna que contém algum 2. Algum dos dois retângulos da solução ótima deve cobrir esse 2 e nenhum retângulo deve cobrir alguma posição a esquerda da coluna $j$, se houvesse tal solução, poderíamos encolher o retângulo sem que deixe de cobrir nenhum 2 e teríamos uma solução menor, ou seja, tal solução não seria ótima. Com isso podemos concluir que pelo menos um dos dois retângulos da solução ótima possui como limite a esquerda a coluna $j$. Portanto ao gerar o primeiro retângulo, só precisamos gerar os retângulos que posuem como limite a esquerda a coluna $j$. Isso reduz o número de soluções que precisamos testar para $N^2 M$.

Agora precisamos de algum algoritmo eficiente para gerar o segundo retângulo. Para isso podemos fazer uma busca binária para cada um dos quatro limites do retângulo, isto é, vamos gastar um tempo $O(\lg N + \lg M)$. Em cada passo da busca binário, temos que verificar se o retângulo atual cobre todos os 2's restantes. Usando uma matriz de soma podemos calcular em tempo constante quantos 2's tem dentro de um retângulo. Para saber quantos 2's os dois retângulos cobrem, bastar somar quantos cada um cobre individualmente e subtrair a cobertura da intersecção dos dois. Assim cada passo da busca leva tempo constante.

Existe uma outra forma mais eficiente para encontrar o segundo retângulo. Uma vez escolhido os limites da esquerda, de cima e de baixo do primeiro retângulo, o algoritmo tenta todos os limites a direita em ordem crescente. O que pode ser feito é, antes de começar o loop que testa todos os limites a direita, é computado de forma gulosa um retângulo que cobre todos os 2, isso pode ser feito em tempo $O(N+M)$. Esse retângulo será o segundo retângulo, cada vez que o primeiro retângulo cresce para a direita, o segundo retângulo só pode diminuir, então podemos, de forma gulosa, reduzir o segundo o máximo possível para cada vez que o primeiro cresce. Fazendo uma análise cuidadosa, o custo de reduzir o retângulo é amortecido, no total não vamos reduzir mais do que $O(N+M)$ vezes para testas todos os limites a direita do primeiro retângulo. Com isso o algoritmo resultante possui complexidade $O(N^3)$, assumindo que $N \geq M$.

Por fim, temos que ignorar as soluções que cobrem algum 1. Para isso basta usar a matriz de soma para os 1's e testar se algum dos retângulos cobre algum 1. E tudo que precisamos fazer em relação aos 1's é ignorar as soluções que cobrem algum 1. A respota final vai ser a melhor das soluções geradas conforme especificado acima com exceção das que cobrem algum 1.

A área total coberta por dois retângulos pode ser calculada pela soma da área dos dois retângulos menos a área da intersecção dos dois. Esta fórmula é uma aplicação direta do princípio de inclusão e exclusão.

O algoritmo apresentado tem complexidade $O(N^2 M (\lg N+ \lg M))$, o que é bem razoável dado que $N, M \leq 50$. Ou sejam $N$ e $M$ tal que $N \geq M$ podemos dizer que a complexidade é $O(N^3 \lg N)$, ou simplesmente $O(N^3)$ usando a segunda estratégia.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License