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

Comentário por Lúcio Cardoso e Willian Wang

Para conferir a prova na íntegra, clique aqui.

Detetive

Conhecimento prévio necessário:

• Conceitos de Grafos
• DFS (Busca em Profundidade)
• Estrutura de dados Bitset

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

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

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

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