OBOI 2023 - Fase 2 - Nível Pleno

Se você quiser se preparar para a OBI, não deixe de conferir o Roteiro de estudos de informática, e também a página de informática do NOIC, com todos nossos materiais.

Para conferir a prova na íntegra, clique aqui.

Par de Palitos

Comentário escrito por Estela Baron

Conhecimento prévio necessário:

• Ordenação

Conjunto de testes N <= 500:

Para resolver essa parcial, podemos calcular toda diferença possível entre dois números (lembrando que é necessário ver o módulo). A complexidade fica $O(N^2)$, a qual não é boa para N = $10^5$.

Conjunto de testes N <= $10^5$

Observe que, para um determinado palito, calcular a menor diferença é ver a distância das alturas entre o maior palito menor ou igual ao atual; ou  entre o menor palito maior ou igual ao atual. Para fazer isso, podemos ordenar os valores dos palitos em ordem crescente e verificar a diferença entre cada dois valores adjacentes. Para obtermos a nossa resposta, basta armazenar o menor valor encontrado e imprimir. A complexidade da solução fica $O(NlogN)$.

Para conferir o código, clique aqui.

Permutação Máxima

Comentário escrito por Caique Paiva

Conhecimentos Prévios Necessários:

• Algoritmos Gulosos

A ideia do problema é bem simples. Depois de fazer alguns casos na mão ($n = 2, 3, 4$), você vê que a resposta nesses casos vai ser a permutação $[N, N-1, \cdots, 1]$ (para $n = 2 \rightarrow [2, 1]$ é a resposta, para $n = 3 \rightarrow [3, 2, 1]$ é a resposta, e assim vai). Durante a prova, a ideia não é provar isso, mas você codar e torcer para isso ser a resposta, já que não tem penalidade para WA. Dito isso, é possível provar, embora ela seja meio complicada, então só recomendo pensar na prova caso você também se interesse por matemática olímpica.

Para implementar, basta criar uma variável $res= 0$, e fazer um for de $n$ até $1$ fazendo $res += |n-i+1 - i|$. Veja que $res$ pode ficar bem grande, então é importante criar ele como uma variável long long.

Clique aqui para ver o código

Entrega de Mantimentos

Comentário escrito por Enzo Dantas

Conhecimento prévio necessário:

• Algoritmo Guloso

Subtask 1

Para os limites pequenos, podemos calcular em O(N) a resposta para cada coordenada entre (0,0) e (100,100).

Solução completa

Intuitivamente, imaginamos um ponto no plano e qual seria a resposta para ele. Deslizando esse ponto livremente, chegamos a primeira observação: se movermos um ponto para a esquerda/direita, as distâncias verticais não mudam, apenas as horizontais (a situação análoga acontece ao deslizar o ponto para cima/baixo). Logo, é possível calcular as coordenadas X e Y independentemente.

Assim, o problema foi reduzido para o seguinte: dados vários pontos numa linha, retorne um ponto qualquer que minimiza o somatório das distâncias aos outros pontos. Seguindo a idea de imaginar um ponto e deslizá-lo pelo plano, percebemos o seguinte: quando o deslizamos 1 unidade para a direita, por exemplo, o somatório aumenta em 1 para cada ponto a sua esquerda e diminui em 1 para cada ponto a sua direita. Assim, se há mais pontos a direita, vale a pena deslizar para a direita e vice-versa. Logo, o ponto ótimo fica em uma posição tal que há metade dos pontos a sua esquerda e metade a sua direita (ou seja, a mediana), pois qualquer movimentação dele diminuiria ou não mudaria o somatório. Para o caso em que N é par, os dois pontos centrais são ótimos. Como o enunciado pede para maximizar o X em caso de empate, retornamos o mais a direita.

Logo, a solução final consiste em separar as coordenadas X e Y em dois arrays diferentes, ordená-los, e retornar as duas medianas.

Clique aqui para conferir o código

Heróis

Comentário escrito por Enzo Dantas

Conhecimento prévio necessário:

• Dijkstra

Subtask 1

Para os limites pequenos, podemos fazer um Dijkstra para cada um dos vértices especiais e percorrer todos os pares para ver a menor distância. Complexidade: $O(K*(N+M)*log + K^2)$.

Subtask 2

O grafo dado é uma árvore. Podemos testar, para cada vértice $u$, qual seria o menor caminho caso $u$ fosse o lca entre os dois mais pertos. Para isso, usamos uma DP tal que $dp[u]$ = vértice especial mais perto de $u$ na subárvore de $u$.

Casos base: se $u$ é um vértice especial, então $dp[u]=0$. Caso contrário, $dp[u]=INF$ $(2*10^9)$.

Transição: tentamos combinar os dois melhores filhos, ou seja, achamos os dois filhos $v1$ e $v2$ que possuem o menor valor de dp+aresta e salvamos que uma possível resposta é $dp[v_1]+dp[v_2] + w(u,v_1)+w(u,v_2)$. Caso $u$ seja um vértice especial, combinamos $u$ com o melhor filho, ou seja, $dp[v_1]+w(u,v_1)$.

Clique aqui para conferir o código

Solução completa

A solução completa usa uma ideia conhecida como Dijkstra Multisource. Faremos um único Dijkstra, mas a priority_queue (ou set) usada no Dijkstra já começa com vários vértices inicializados com distância zero (ou seja, há vários pontos iniciais, por isso o nome "multisource"). Assim, cada vértice terá salvo a menor distância para o vértice especial mais próximo.

Imagine que cada vértice especial agora possui uma "região" próxima de si tal que todos os vértices nessa região são mais próximos dele do que de qualquer outro vértice especial. Testaremos cada aresta $(u,v)$ que conecta duas regiões diferentes, ou seja, salvamos que $w(u,v)+dist[u]+dist[v]$ é uma possível resposta e pegamos a menor entre todas elas. Note que, para saber se uma aresta conecta duas regiões diferentes, precisamos salvar para todo vértice o índice do vértice especial mais próximo, o que pode ser feito facilmente no Dijkstra.

Clique aqui para conferir o código

Bonsai

Comentário por Henrique Vianna

Conhecimento prévio necessário:

• DP em Árvore
• Problema da Mochila (Knapsack)
• Euler Tour

Perceba que o enunciado se resume ao seguinte: Dada uma árvore $T$ em que os vértices possuem valores $v[i]$ (que podem inclusive ser negativos), maximize $\sum_{u \in T}v[u]$ após a remoção de até $K$ vértices, juntos às suas respectivas subárvores. Na resolução desse exercício, analisaremos cada uma das parciais, antes de chegar à solução final.

Parcial 1: A árvore é uma linha, ou seja, $u[i] = i, v[i] = i + 1$  $\forall 1 \leq i \leq N - 1$.

Nessa parcial, podemos imaginar a a árvore como um vetor, em que as operações que podemos fazer é remover um sufixo seu. Perceba entretanto, que o valor de $K$ é irrelevante: sempre existe uma solução ótima em que exatamente um sufixo é removido, podendo esse ser nulo. Por consequência, sempre manteremos um prefixo desse vetor, ou seja, a resposta é simplesmente a maior soma de prefixo de $T$.

Parcial 2: $1 \leq N \leq 10^3$ e $1 \leq K \leq 100$

Para resolver essa parcial, faremos uso de uma dp, sendo que:

$dp[u][j]$ é o minimo que consigo remover com exatamente $j$ operações entre os vértices da subárvore de $u$.

A recorrência dessa dp é relativamente simples. Faremos uso de uma segunda dp, $dp2$, para nos auxiliar nessa recorrência:

$dp2[i][j]$ é o minimo que consigo remover em $j$ operações considerando os $i$ primeiros filhos de $u$.

A recorrência de $dp2[i][j]$ é bastante similar à DP clássica da Knapsack: deve-se brutar, para o filho atual, quantas operações serão feitas dentro de sua subárvore. Chamaremos esse numero de $c$. Sendo assim:

$dp2[i][j] = min(dp2[i - 1][j], dp2[i - 1][j - c] + dp[v][c])$, tal que $1 \leq c \leq j$

Ao final, para termos os valores de $dp[u][j]$ de fato, basta fazermos:

$dp[u][j] = dp2[f][j]$, sendo $f$ o numero de filhos de $u$.

A resposta é simplesmente $\sum_{i= 1}^{N}v[i] - min(dp[1][j])$, com $1 \leq j \leq K$.

Parcial 2: Sem restrições adicionais.

A $dp$ acima, apesar de ser suficiente para a parcial 2, não é rápida o suficiente para obter-se $100$ pontos, haja vista sua complexidade de $\mathcal{O}(N*K^2)$. Precisamos, portanto, otimizá-la. Uma maneira inteligente de fazer isso é "linearizar" a árvore, fazendo uma $dp$ similar a essa em seu Euler Tour. Para tanto, basta calcularmos o $tin$ e $tout$ de cada um dos vértices numa $dfs$ inicial. Calcularemos a $dp$ nos vértices ordenados por $tin$. Define-se:

$dp[i][j]$ é o minimo que consigo remover com exatamente $j$ operações entre os  $i$ últimos vértices do Euler Tour.

Vale notar que estamos calculando a nossa $dp$ no sufixo, ou seja, passando do ultimo vértice do Euler Tour ao primeiro. A recorrência, portanto, é dada por:

$dp[i][j] = min(dp[i + 1][j],dp[tout[tour[i]+1]][j-1]+sub[tour[i])$, sendo que $sub[u]$ guarda a soma dos $v[i]$ na subárvore de $u$.

A resposta é calculada da mesma forma que na parcial $2$. Sendo assim, conseguimos resolver o problema em $\mathcal{O}(N*K)$.

Para melhor compreensão, confira o código aqui.