Comentário Noic OBI 2019 – Fase 2 – Programação Nível 1

Comentário por Willian Wang e Lúcio Cardoso

Para conferir a prova na íntegra, clique aqui.

Nota esquecida

Conhecimento prévio necessário:

• Entrada e Saída

Perceba que $$A+B = 2*M$$ e $$B = 2*M – A$$.

Um possível erro é tentar calcular $$B$$ usando divisão com variáveis inadequadas, como $$B=(M+A/2)*2$$ sendo $$A$$ e $$M$$ inteiros, por isso uma boa prática é sempre evitar a operação de divisão no código.   

Complexidade: $$O(1)$$.

Ponto do Meio

Conhecimento Prévio Necessário:

• Entrada e Saída
• Loops
• Funções Recursivas

Seja $$f(x)$$ a quantidade de pontos no lado do quadrado no passo $$x$$. É possível notar que $$f(x) = 2*f(x-1) -1$$ e criar uma função recursiva em cima disso.

O método recursivo de calcular a resposta descrito faz parte de uma área mais ampla chamada programação dinâmica. 

Complexidade: $$O(n)$$.

 

Implementar a solução acima deve garantir os 100 pontos do problema, mas quando analisamos mais a fundo a recursão, descobrimos que $$f(x) = 2^x + 1$$, e com isso criar uma solução com complexidade logarítmica usando a técnica de exponenciação de matrizes, deixamos claro que essa solução não é necessária para o problema.

Matriz Super-Legal

Conhecimento prévio necessário:

• Loops
• Estruturas da STL – Stack
• Problema da Semana #39 – Avançado

Este mesmo problema estava presente na prova do Nível 2 e, provavelmente, foi um dos problemas mais interessantes dessa fase da OBI.

O seguinte lema é essencial na solução do problema:

Lema: Uma matriz é super-legal se, e somente se, todas as suas submatrizes $$2$$x$$2$$ são legais.

Redução do Problema

Utilizando dessa observação, vamos construir uma nova matriz $$B$$ de dimensões $$(N-1)$$x$$(M-1)$$, de valores $$0$$ ou $$1$$. Ela será definida da seguinte maneira:

• Se a submatriz $$2$$x$$2$$ de $$A$$ de cantos $$(i, j)$$ e $$(i+1, j+1)$$ for legal, então $$B(i, j) = 1$$.
• Caso contrário, $$B(i, j) = 0$$.

Suponha que a maior matriz super-legal de $$A$$ possui cantos $$(a, b)$$ e $$(c, d)$$ ($$a \leq c, b \leq d$$). Então, teremos que todos os valores na submatriz em $$B$$ de cantos $$(a, b)$$ e $$(c-1, d-1)$$ serão iguais a $$1$$. Ou seja, todas as submatrizes $$2$$x$$2$$ em $$A$$ com canto superior esquerdo indo desde $$(a, b)$$ até $$(c-1, d-1)$$ devem ser legais.

Logo, a maior submatriz super-legal em $$A$$ representa, em $$B$$, a submatriz de comprimentos $$x$$ e $$y$$ tal que o valor $$(x+1) \cdot (y+1)$$ é máximo e que todos os seus elementos sejam iguais a $$1$$. Resta agora encontrarmos esta matriz em $$B$$.

Algoritmo em $$O(NM^2)$$

Defina $$h(i, j)$$ como o maior valor $$k$$ tal que $$B(i, j), B(i-1, j), …, B(i-k+1, j)$$ são células de valor $$1$$. Ou seja, $$h(i, j)$$ é a “altura” da célula $$B(i, j)$$. Além disso, defina $$X_m$$ e $$Y_m$$ como os comprimentos da matriz que desejamos encontrar em $$B$$. Perceba que o valor $$h$$ de cada uma das células na última linha da matriz procurada é maior ou igual a $$Y_m$$.

Assim, para encontrar o valor $$(X_m+1) \cdot (Y_m+1)$$ máximo, ou seja, a área da maior matriz super-legal, podemos realizar o seguinte algoritmo:

Algoritmo 1:

1. Fixe uma célula $$(i, j)$$ qualquer da matriz $$B$$ de tal forma que $$B(i, j) = 1$$.
2. Encontre o índice $$j_0$$ mais à direita tal que $$1 \leq j_0 < j$$ e $$h(i, j_0) < h(i, j)$$.
3. Encontre o índice $$j_1$$ mais à esquerda tal que $$j < j_1 \leq M$$ e $$h(i, j_1) < h(i, j)$$.
4. Caso $$(j_1 – j_0) \cdot (h(i, j) + 1)$$ seja maior do que a resposta atual, atualize-a para este valor.
5. Repita as etapas $$1…4$$ para as outras células não-nulas de $$B$$.

Essencialmente, o algoritmo acima escolhe uma célula e encontra a matriz de maior comprimento $$X$$ possível tal que seu comprimento $$Y$$ seja $$h(i, j)$$ e que a célula $$(i, j)$$ seja uma das células na base da matriz.

Assim, note que é possível realizar um algoritmo de complexidade $$O(NM^2)$$: Podemos encontrar os valores $$h(i, j)$$ para cada célula em $$O(NM)$$ (mais detalhes no código abaixo) e realizar o Algoritmo 1 para cada uma das $$(N-1)(M-1)$$ células, encontrando os valores $$j_0$$ e $$j_1$$ em $$O(M)$$. Essa solução era suficiente para conseguir $$60$$ pontos no problema.

Otimização do Algoritmo 1

Para uma solução mais eficiente, vamos encontrar os valores $$j_0$$ de $$j_1$$ de maneira rápida. Para isso, iremos utilizar a estrutura de dados stack (pilha) da STL do C++. O algoritmo será o seguinte:

Algoritmo 2:

1. Inicie na célula $$(i, 1)$$ da matriz $$B$$, onde $$i$$ é a linha atual (iniciando por $$1$$) e declare uma pilha vazia de pares da forma $$(j, h(i, j))$$.
2. Se a célula atual for $$(i, j)$$, remova o par no topo da pilha caso seu segundo elemento tenha valor maior ou igual a $$h(i, j)$$.
3. Repita a etapa $$2$$ até que a pilha esteja vazia ou até que o valor do segundo elemento do par no seu topo seja menor do que $$h(i, j)$$.
4. O índice $$j_0$$ será o valor do primeiro elemento do par no topo da pilha (ou será inexistente caso a pilha esteja vazia).
5. Insira o par $$(j, h(i, j))$$ na pilha.
6. Repita as etapas $$2…5$$ para os elementos restantes na linha atual. Após isso, recomece da etapa $$1$$ na linha seguinte.

O Algoritmo 2 é extremamente similar àquele usado no Problema da Semana #39 – Avançado. Para melhor entendimento, confira a sua solução.

Para encontrar o valor $$j_1$$, o algoritmo será análogo: Basta iterar por cada linha de trás para frente e refazer o mesmo processo. Finalmente, perceba que a complexidade do Algoritmo 2 em cada uma das $$N-1$$ linhas de $$B$$ será $$O(M)$$, já que cada elemento na linha é inserido/removido da pilha no máximo uma vez.

Complexidade da solução: $$O(NM)$$.