Comentário por Lúcio Cardoso e Willian Wang
Para conferir a prova na íntegra, clique aqui.
Detetive
Conhecimento prévio necessário:
Modelando o problema em um grafo
Vamos transformar a situação do problema em um grafo direcionado. Se $$A \implies B$$, iremos dizer que o vértice $$A$$ terá uma aresta (direcionada) para o vértice $$B$$.
Chamaremos de source todos os vértices cujo ingrau (quantidade de arestas que apontam para tal vértice) é igual a $$0$$. Perceba que não existe caminho de nenhum vértice no grafo para alguma source. Além disso, se um vértice $$U$$ é definido como verdadeiro, então no mínimo uma das sources do grafo que tem um caminho para $$U$$ é, também, verdadeira. Ou seja, podemos fazer a seguinte afirmação:
Fato: Defina $$S(U)$$ como o conjunto das sources do grafo que possuem um caminho para $$U$$. Então, caso $$U$$ seja verdadeiro, existe um vértice $$s \in S(U)$$ que é verdadeiro.
Interseção dos conjuntos $$S(U)$$
Imagine que existe um vértice $$U$$ inicialmente verdadeiro no grafo. Vamos tomar um outro vértice $$V$$ qualquer, o qual não sabemos se é verdadeiro ou não. Perceba que se $$S(U)$$ é um subconjunto de $$S(V)$$, então $$V$$ será certamente verdadeiro, pois alguma source $$s \in S(U)$$ que é verdadeira também possuirá um caminho para $$V$$. Podemos generalizar esta observação com o seguinte lema:
Lema: Seja $$V$$ um vértice qualquer. O vértice $$V$$ será verdadeiro se, e somente se, existe algum vértice $$U$$ incialmente verdadeiro tal que $$S(U)$$ é um subconjunto de $$S(V)$$.
Com isso, precisaremos encontrar, para cada vértice, o conjunto de sources que chegam nele. Podemos fazer isso usando uma DFS partindo de cada source: guardaremos um vetor de booleanos $$path[]$$ para cada vértice $$v$$, indicando quais sources possuem um caminho para ele, e assim que a DFS de alguma source $$s$$ chegar em $$v$$, indicaremos que $$path[v][s] = true$$. A complexidade total realizando cada uma dessas DFSs será $$O(E(E+I))$$.
Algoritmo em $$O(E^3)$$
Usando o lema acima, podemos utilizar de um algoritmo simples para resolver o problema em $$O(E^3)$$. Para cada vértice $$U$$ inicialmente verdadeiro, vamos checar se $$S(U) \cap S(V) = S(U)$$, para todo vértice $$V$$ do grafo. Se sim, marcaremos $$V$$ como verdadeiro. Usando o nosso vetor de booleanos $$path[]$$, podemos encontrar a interseção em $$O(E)$$. Logo, como realizamos uma operação em $$O(E)$$ com todos os vértices do grafo para cada vértice verdadeiro, a complexidade do algoritmo é $$O(E^3)$$. Essa solução era suficiente para um total de $$70$$ pontos no problema.
Otimização do algoritmo com bitsets
Um bitset é uma estrutura de dados do C++ utilizada para representar conjuntos. Com ela, podemos realizar interseção e união de conjuntos de tamanho $$N$$ em $$O(N/32)$$. Apesar da complexidade $$O(N/32)$$ ser equivalente a $$O(N)$$, na prática, o bitset é muito mais rápido. Para mais informações, é recomendada a leitura da referência do C++ sobre bitsets.
Para otimizar o algoritmo acima, podemos representar o vetor booleano $$path[]$$ como um bitset. Assim, a interseção dos conjuntos $$S(U)$$ e $$S(V)$$ pode ser encontrada em $$O(E/32)$$, totalizando uma complexidade final de $$O(E^3/32)$$.
https://gist.github.com/luciocf/4d7ac156ded3163be4ae59bc5ee73859
Matriz Super-Legal
Conhecimento prévio necessário:
Este mesmo problema estava presente na prova do Nível 1 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:
- Fixe uma célula $$(i, j)$$ qualquer da matriz $$B$$ de tal forma que $$B(i, j) = 1$$.
- Encontre o índice $$j_0$$ mais à direita tal que $$1 \leq j_0 < j$$ e $$h(i, j_0) < h(i, j)$$.
- Encontre o índice $$j_1$$ mais à esquerda tal que $$j < j_1 \leq M$$ e $$h(i, j_1) < h(i, j)$$.
- Caso $$(j_1 – j_0) \cdot (h(i, j) + 1)$$ seja maior do que a resposta atual, atualize-a para este valor.
- 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:
- 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))$$.
- 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)$$.
- 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)$$.
- O índice $$j_0$$ será o valor do primeiro elemento do par no topo da pilha (ou será inexistente caso a pilha esteja vazia).
- Insira o par $$(j, h(i, j))$$ na pilha.
- 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
Supermercado
Conhecimento prévio necessário:
- Entrada e Saída
- Algoritmos Gulosos
Perceba que, se $$G$$ gramas de um produto custam $$P$$ Bits, então $$1$$ grama custa $$\frac{P}{G}$$ Bits. Por consequência disso, é sempre uma escolha melhor comprar $$1$$ kilograma usando apenas do produto cujo custo por $$1$$ grama é o menor possível. Podemos, assim, ler cada um dos valores $$P, G$$ de um produto e imprimir aquele de menor valor $$\frac{P}{G}$$ multiplicado por $$1000$$ gramas.
Complexidade: $$O(n)$$.
https://gist.github.com/luciocf/a8c15bd4e4366a8f4984a54b8c75994e