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

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:

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)$$.

https://gist.github.com/wilwxk/98d40ab9fe428fd41bc5746ced80ddc1

Ponto do Meio

Conhecimento Prévio Necessário:

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)$$.

https://gist.github.com/wilwxk/1ad4e71d42c5344723eabea9235381ac

 

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:

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.

[spoiler title=’Prova’ style=’steelblue’ collapse_link=’true’]

Note que, pelo enunciado do problema, todas as submatrizes $$2$$x$$2$$ de uma matriz super-legal devem ser legais. Queremos, então, provar que a condição é suficiente.

Fato 1: Toda matriz $$2$$x$$M$$ ($$M \geq 2$$) que possui todas as suas submatrizes $$2$$x$$2$$ legais é super-legal.

Prova do Fato 1:

Vamos supor, por indução, que o fato vale para qualquer matriz $$2$$x$$K$$, onde $$2 \leq K < M$$. Se provarmos que a matriz $$2$$x$$M$$ é legal,  podemos concluir, como um resultado da hipótese de indução, que ela é super-legal.

Note que o caso base é o caso trivial consistindo apenas de uma matriz $$2$$x$$2$$. Temos que:

1. $$A(1, 1) + A(2, 2) \leq A(1, 2) + A(2, 1)$$, pois a matriz de cantos $$(1,1)$$ e $$(2, 2)$$ é legal.

2. $$A(1, 2) + A(2, M) \leq A(1, M) + A(2, 2)$$, pois, por hipótese de indução, a matriz de cantos $$(1, 2)$$ e $$(2, M)$$ é legal.

Somando as desigualdades, temos que:

$$A(1, 1) + A(2, 2) + A(1, 2) + A(2, M) \leq A(1, 2) + A(2, 1) + A(1, M) + A(2, 2)$$

$$ \implies A(1, 1) + A(2, M) \leq A(1, M) + A(2, 1)$$.

Ou seja, a matriz $$2$$x$$M$$ é legal. Assim, o Fato 1 está provado por indução.

Fato 2: Toda matriz $$N$$x$$2$$ ($$N \geq 2$$) que possui todas as suas submatrizes $$2$$x$$2$$ legais é super-legal.

Prova do Fato 2: Análoga à prova do Fato 1.

Agora, vamos supor, novamente por indução, que uma matriz $$P$$x$$Q$$ ($$2 \leq P < N, 2 \leq Q < M$$) qualquer é super-legal. Para finalizar a prova, é suficiente provar que a matriz $$N$$x$$M$$ será legal.

Perceba que os casos base da indução são exatamente o Fato 1 e o Fato 2. Temos que:

1. $$A(1, 1) + A(N-1, M) \leq A(1, M) + A(N-1, 1)$$, pois pela hipótese de indução, a matriz de cantos $$(1, 1)$$ e $$(N-1, M)$$ é legal.

2. $$A(N-1, 1) + A(N, M) \leq A(N-1, M) + A(N, 1)$$, pois, pelo Fato 1, a matriz de cantos $$(N-1, 1)$$ e $$(N, M)$$ é legal.

Somando as desigualdades, obtemos que:

$$A(1, 1) + A(N-1, M) + A(N-1, 1) + A(N, M) \leq A(1, M) + A(N-1, 1) + A(N-1, M)$$

$$ + A(N, 1) \implies A(1, 1) + A(N, M) \leq A(1, M) + A(N, 1)$$.

Ou seja, a matriz $$N$$x$$M$$ inteira é legal. Assim, a prova está concluída.

[/spoiler]

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)$$.

https://gist.github.com/luciocf/7d8ab6f74780f3c1b3cce7f9e715f8ac