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⟹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∈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∈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(E3)
Usando o lema acima, podemos utilizar de um algoritmo simples para resolver o problema em O(E3). Para cada vértice U inicialmente verdadeiro, vamos checar se S(U)∩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(E3). 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(E3/32).
// Comentário Noic OBI 2019 - Fase 2 - Programação Nível 2 | |
// Detetive | |
#include <bits/stdc++.h> | |
using namespace std; | |
const int maxn = 1e3+10; | |
// bitset indicando quais sources do grafo chegam em cada vértice | |
bitset<maxn> path[maxn]; | |
// grafo das implicações | |
vector<int> grafo[maxn]; | |
// ingrau de cada vértice | |
int grau[maxn]; | |
// vetor de marcação da dfs | |
bool mark[maxn]; | |
bool verdadeiro[maxn]; | |
void dfs(int source, int u) | |
{ | |
// source tem um caminho para u | |
path[u][source] = 1; | |
mark[u] = true; | |
for (auto v: grafo[u]) | |
if (!mark[v]) | |
dfs(source, v); | |
} | |
int main(void) | |
{ | |
int E, I, V; | |
scanf("%d %d %d", &E, &I, &V); | |
for (int i = 1; i <= I; i++) | |
{ | |
int u, v; | |
scanf("%d %d", &u, &v); | |
// u -> v | |
grafo[u].push_back(v); | |
grau[v]++; | |
} | |
for (int i = 1; i <= E; i++) | |
{ | |
if (grau[i] == 0) | |
{ | |
memset(mark, 0, sizeof mark); | |
dfs(i, i); | |
} | |
} | |
for (int i = 1; i <= V; i++) | |
{ | |
int u; | |
scanf("%d", &u); | |
verdadeiro[u] = true; | |
for (int v = 1; v <= E; v++) | |
{ | |
// o comando & é usado para encontrar a interseção de bitsets | |
// count() calcular a quantidade de bits ligados no bitset | |
if ( (path[u]&path[v]).count() == path[u].count()) | |
verdadeiro[v] = true; | |
} | |
} | |
// imprime a resposta | |
for (int i = 1; i <= E; i++) | |
if (verdadeiro[i]) | |
printf("%d ", i); | |
printf("\n"); | |
} |
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 2x2 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 2x2 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≤c,b≤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 2x2 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)⋅(y+1) é máximo e que todos os seus elementos sejam iguais a 1. Resta agora encontrarmos esta matriz em B.
Algoritmo em O(NM2)
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 Xm e Ym 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 Ym.
Assim, para encontrar o valor (Xm+1)⋅(Ym+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 j0 mais à direita tal que 1≤j0<j e h(i,j0)<h(i,j).
- Encontre o índice j1 mais à esquerda tal que j<j1≤M e h(i,j1)<h(i,j).
- Caso (j1−j0)⋅(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(NM2): 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 j0 e j1 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 j0 de j1 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 j0 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 j1, 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).
// Comentário Noic OBI 2019 - Fase 2 - Programação Nível 2 | |
// Matriz Super Legal | |
#include <bits/stdc++.h> | |
using namespace std; | |
typedef pair<int, int> pii; | |
const int maxn = 1e3+10; | |
int n, m; | |
// altura de cada célula | |
int h[maxn][maxn]; | |
// matrizes | |
int A[maxn][maxn], B[maxn][maxn]; | |
int j_0[maxn][maxn], j_1[maxn][maxn]; | |
void calc_h(void) | |
{ | |
for (int i = 1; i < n; i++) | |
{ | |
for (int j = 1; j < m; j++) | |
{ | |
if (!B[i][j]) continue; | |
// calculamos h[i][j] baseando-nos na célula acima | |
if (B[i-1][j] == 1) h[i][j] = 1+h[i-1][j]; | |
else h[i][j] = 1; | |
} | |
} | |
} | |
void calc_j0(void) | |
{ | |
for (int i = 1; i < n; i++) | |
{ | |
stack<pii> stk; | |
for (int j = 1; j < m; j++) | |
{ | |
// algoritmo 2 | |
while (!stk.empty() && stk.top().second >= h[i][j]) | |
stk.pop(); | |
// se j0 não existe, digamos que ele será uma posição a | |
// menos do limite (1) | |
if (stk.empty()) j_0[i][j] = 0; | |
else j_0[i][j] = stk.top().first; | |
stk.push({j, h[i][j]}); | |
} | |
} | |
} | |
void calc_j1(void) | |
{ | |
for (int i = 1; i < n; i++) | |
{ | |
stack<pii> stk; | |
for (int j = m-1; j >= 1; j--) | |
{ | |
// algoritmo 2 | |
while (!stk.empty() && stk.top().second >= h[i][j]) | |
stk.pop(); | |
// se j1 não existe, digamos que ele será uma posição a | |
// mais do que o limite (m-1) | |
if (stk.empty()) j_1[i][j] = m; | |
else j_1[i][j] = stk.top().first; | |
stk.push({j, h[i][j]}); | |
} | |
} | |
} | |
int main(void) | |
{ | |
scanf("%d %d", &n, &m); | |
for (int i = 1; i <= n; i++) | |
for (int j = 1; j <= m; j++) | |
scanf("%d", &A[i][j]); | |
// checando todas as matrizes 2x2 | |
for (int i = 1; i < n; i++) | |
for (int j = 1; j < m; j++) | |
if (A[i][j]+A[i+1][j+1] <= A[i+1][j]+A[i][j+1]) | |
B[i][j] = 1; | |
calc_h(); | |
calc_j0(); | |
calc_j1(); | |
// resposta do problema | |
int ans = 0; | |
for (int i = 1; i < n; i++) | |
for (int j = 1; j < m; j++) | |
if (h[i][j]) | |
ans = max(ans, (j_1[i][j]-j_0[i][j])*(h[i][j]+1)); // (x_m+1)*(y_m+1) | |
printf("%d\n", ans); | |
} |
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 PG 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 PG multiplicado por 1000 gramas.
Complexidade: O(n).
// Comentário Noic OBI 2019 - Fase 2 - Programação Nível 2 | |
// Supermercado | |
#include <bits/stdc++.h> | |
using namespace std; | |
int main(void) | |
{ | |
int n; | |
cin >> n; | |
// inicializamos a resposta com um valor muito grande, | |
// digamos 10^9 | |
double ans = 1e9; | |
for (int i = 1; i <= n; i++) | |
{ | |
double p, g; | |
cin >> p >> g; | |
// usamos a função min do C++ para escolher a resposta mínima | |
ans = min(ans, 1000.00*(p/g)); | |
} | |
// dizemos que a precisão do cout será de 2 dígitos após o ponto decimal | |
cout.precision(2); | |
cout.setf(ios::fixed); | |
cout << ans << "\n"; | |
} |