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

Escrito por Lúcio Figueiredo, Leonardo Paes e Thiago Mota

Para conferir a prova na íntegra, clique aqui.

Metrô da Nlogônia

Conhecimento prévio necessário:

• Conceitos de Grafos
• Diâmetro de uma Árvore

Note que os sistemas Círculo e Quadrado são ambos árvores, ou seja, grafos conexos e acíclicos. Assim, a tarefa do problema é encontrar dois vértices $U$ e $V$ de modo que $U$ pertença ao sistema Círculo, $V$ pertença ao sistema Quadrado e o diâmetro do grafo resultante ao ligar $U$ e $V$ (que será uma árvore) sejá o menor possível.

Para uma árvore $T$ qualquer, defina $h(T, x)$ (ou excentricidade de $x$ em $T$) como a maior distância do vértice $x$ para algum vértice de $T$, ou seja, a maior profundidade de algum vértice quando a árvore é enraizada no vértice $x$. Sendo $C$ a árvore do sistema Círculo e $Q$ a árvore do sistema quadrado, o seguinte lema vale:

Lema 1: Se $U$ é um vértice de $C$ e $V$ é um vértice de $Q$, o diâmetro da árvore resultante ao ligar $U$ e $V$ será igual a $max \Big( diam(C), diam(Q), h(C, U)+h(Q, V)+1 \Big )$, onde $diam(T)$ é o diâmetro de uma árvore $T$ qualquer.

Na figura acima, obtemos que o diâmetro da árvore resultante ao ligar $U$ e $V$ é $6$, já que $diam(C) = 3$, $diam(Q) = 2$ e $h(C, U) + h(Q, V)+1 = 6$.

Como o valor de $diam(C)$ e $diam(Q)$ não dependem da nossa escolha de $U$ e $V$, queremos escolhê-los de forma que o valor de $h(C, U)+h(Q, V)$ seja o menor possível, ou seja, de modo que $U$ e $V$ tenham a menor excentricidade possível nas suas respectivas árvores.

Para uma árvore qualquer, o vértice cuja excentricidade é a menor possível é chamado centro da árvore. Logo, o problema se resume em encontrar os centros de cada uma das duas árvores. Para entender como achar o centro de uma árvore, acesse o material do Noic sobre Diâmetro de uma Árvore.

Confira o código abaixo para melhor entendimento:

Mesa Redonda

Conhecimento prévio necessário:

• Estruturas Condicionais

Primeiro temos que descobrir em qual posição Ana irá sentar. Para descobrir isto, basta checar o resto da divisão do número sorteado por $3$. Com essa informação, iremos utilizar o mesmo procedimento para descobrir a posição de Ana, com a diferença de que se a posição que Beatriz for sentar já foi utilizada por Ana, ela terá que ser movida uma cadeira para frente. Desse modo, resta olhar qual cadeira sobrou e essa posição é a resposta.

Exploração do Capitão Levi

Conhecimento prévio necessário:

• Ordenação
• BIT (Binary Indexed Tree)
• Compressão de Coordenadas

Inicialmente, vamos ordenar os pontos dados de maneira crescente em relação à coordenada $x$, ou seja, de modo que para qualquer par de pontos com índices $i$ e $j$ com $i < j$, vale que $x_i \leq x_j$.

A tarefa do problema se resume em calcular a quantidade de pares de pontos $(i, j)$ de forma que $\frac{y_j - y_i}{x_j-x_i} \geq \frac{P}{Q}$. Como o par $(i, j)$ é equivalente ao par $(j, i)$, vamos calcular os pares de pontos de modo que $i < j$, para garantirmos que $x_j - x_i$ possuirá um valor positivo (devido à ordenação inicial).

Para simplificar o problema, caso $Q$ seja negativo, vamos multiplicar o valor de $Q$ e de $P$ por $-1$; desta forma, tornamos $Q$ positivo e não modificamos o valor de $\frac{P}{Q}$. Feito isto, podemos trabalhar de maneira simples com a inequação principal do problema, da seguinte forma:

$\frac{y_j - y_i}{x_j-x_i} \geq \frac{P}{Q} \implies Q \cdot (y_j-y_i) \geq P \cdot (x_j-x_i) \implies Q \cdot y_j - P \cdot x_j \geq Q \cdot y_i - P \cdot x_i$ $(1)$.

Sendo $f(i) = Q \cdot y_i - P \cdot x_i$, utilizando a inequação $(1)$, reduzimos o problema para calcular, para cada ponto $i$, a quantidade de pontos $j$ $(i < j)$ de modo que $f(i) \leq f(j)$.

Podemos resolver este problema utilizando um vetor de frequências: Vamos iterar pelos pontos $i$ desde $N$ até $1$, e armazenaremos em $freq[x]$ a quantidade de pontos com índice maior que $i$ cujo valor $f()$ é igual a $x$. Assim, no ponto $i$, aumentamos nossa resposta em $\sum_{k=1}^{f(i)} freq[k]$, e após isso, adicionamos $1$ no valor de $freq[f(i)]$.

No entanto, note que a complexidade do método descrito não é suficiente para resolver o problema, já que o valor máximo de $f(i)$ pode ser grande. Porém, perceba que podemos otimizar o nosso algoritmo utilizando uma BIT: A operação de calcular $\sum_{k=1}^{f(i)} freq[k]$ é idêntica à função $soma(f(i))$ da BIT e a operação de adicionar $1$ a $freq[f(i)]$ é equivalente a $upd(f(i), 1)$.

Agora, só resta uma dificuldade em nossa solução: O valor de $f(i)$ pode ser grande (até $10^7 \cdot 10^9$), e o tamanho do vetor da BIT deve ser grande o suficiente para armazenar valores em posições desta magnitude. Porém, perceba que existem, no máximo, $N$ valores distintos de $f(i)$. Logo, podemos utilizar a técnica de Compressão de Coordenadas nos valores $f(i)$, e assim, utilizar a BIT com memória de tamanho $O(N)$.

Assim, a complexidade final da solução é $O(N \log_{} N)$, já que precisamos ordenar o nosso vetor e utilizar as funções da BIT.

Confira o código abaixo para melhor entendimento:

Grand Prix da Nlogônia

Conhecimento prévio necessário:

• DFS (Busca em profundidade)
• Busca Binária
• Árvore de Segmentos (Segment Tree)

Inicialmente, perceba que podemos realizar uma busca binária para encontrar o menor índice $X$ tal que ao aceitar cada plano de $1$ a $X$, o grafo resultante possuirá um ciclo. Porém, precisamos construir o grafo de maneira eficiente, já que cada plano pode adicionar até $N$ novas arestas no grafo.

Construindo o grafo modificado

Note que cada plano adiciona arestas no grafo de uma forma específica: um plano $(U, L, R)$ liga $U$ ao intervalo de vértices $[L, R]$. Tendo em mente que estamos trabalhando com intervalos, vamos utilizar uma Árvore de Segmentos que nos auxiliará na construção do grafo.

A segment tree será utilizada como um grafo, em conjunto com os $N$ vértices iniciais. A construção deste novo grafo será realizada da seguinte forma:

• Cada vértice não-folha da segment tree terá uma aresta direcionada para os seus dois filhos, de modo que partindo de um vértice que representa um intervalo $[L, R]$ na árvore, conseguimos chegar em cada folha neste intervalo.
• A folha de intervalo $[L, L]$ na segment tree possuirá uma aresta direcionada para o vértice $L$ do grafo inicial.
• Ao adicionarmos um plano $(U, L, R)$, iremos criar arestas direcionadas do vértice $U$ para cada nó da segment tree que está totalmente contido no intervalo $[L, R]$ (ou seja, os mesmos nós utilizados ao fazer uma query no intervalo $[L, R]$ da segment tree, quando a utilizamos em sua aplicação convencional).

Perceba que, ao adicionarmos as arestas desta forma, um vértice $U$ que foi ligado ao intervalo $[L, R]$ consegue alcançar todos vértice $V \in [L, R]$: Basta seguir a aresta de $U$ ao vértice da segment tree que "cobre" o vértice $V$ (ou seja, o nó da árvore cujo intervalo contém $V$), percorrer o caminho deste vértice até a folha da árvore que representa $V$ e, por fim, percorrer a aresta desta folha para $V$.

Logo, se $U$ consegue alcançar o vértice $V$ no grafo original (o grafo resultante ao criar arestas do vértice de um plano a todos os vértices no intervalo neste plano), $U$ também consegue alcançar $V$ no grafo modificado com a segment tree. Além disso, como o intervalo $[L, R]$ é representado pela união de $O(log_{} N)$ nós da segment tree, a quantidade de arestas criadas ao aceitarmos $P$ planos é de complexidade $O(P \cdot log_{} N)$.

Na imagem acima, vértices azuis representam os nós da árvore de segmentos, e os vértices de cor rosa representam os vértices originais. A imagem indica as arestas presentes no grafo para $N = 4$ e com os planos $(1, 2, 4)$ e $(3, 4, 4)$.

Encontrando um ciclo no novo grafo

O único problema que ainda precisamos resolver é como descobrir se o grafo resultante ao adicionar um prefixo de planos (durante a busca binária) é acíclico ou não. Podemos descobrir isso utilizando uma DFS e um vetor de marcação, digamos, $mark[]$. O vetor de marcação possuirá os seguintes valores:

• Se o vértice $u$ ainda não foi percorrido pela DFS, $mark[u] = 0$.
• Se o vértice $u$ foi percorrido pela DFS, mas a sua DFS ainda não foi concluída, $mark[u] = 1$.
• Se a DFS de $u$ foi concluída, $mark[u] = 2$.

Note que um ciclo será encontrado se, e somente se, durante a DFS realizada em algum vértice $u$, existe um vértice uma aresta de $u$ para algum vértice $v$ de modo que $mark[v] = 1$, pois neste caso, existe um caminho de $v$ para $u$ que não percorre a aresta $(u, v)$. Assim, conseguimos encontrar um ciclo no grafo com complexidade $O(N+M)$ (complexidade da DFS).

Complexidade final

Durante cada uma das $O(\log_{} M)$ iterações da busca binária, serão construídas $O(P \cdot \log_{} N)$ arestas no grafo, onde $P$ é a quantidade de planos aceitos; assim, a DFS realizada possuirá complexidade $O(N + P \cdot \log_{} N)$, e portanto, a complexidade final da solução é $O(M \cdot \log_{}^2 M)$.

Confira o código abaixo para melhor entendimento:

Etiquetas

Conhecimento prévio necessário:

• Programação Dinâmica
• Soma de Prefixos

Para resolvermos esse problema, utilizaremos uma técnica conhecida como Programação Dinâmica. A ideia será calcular a soma dos valores dos inteiros que iremos tirar ao usar as etiquetas, com o objetivo de minimizá-la, já que queremos maximizar a soma dos números que restaram.

Seja $dp[i][j]$ o mínimo valor possível considerando apenas a fita formada pelos $i$ primeiros inteiros e utilizando $j$ etiquetas de tamanho $c$. Então, as transições da programação dinâmica consistem de duas escolhas:

• Colocar uma etiqueta na posição atual ($i$), cobrindo os números de índice $i-c+1$ até $i$. O valor deste caso é igual a $soma[i-c+1][i] + dp[i-c][j+1]$, onde $soma[l][r]$ é igual à soma dos inteiros no intervalo $[l, r]$. Podemos encontrar esta soma em $O(1)$ utilizando a técnica de soma de prefixos.
• Não colocar uma etiquta na posição $i$. O valor deste caso é igual a $dp[i-1][j]$.

Logo, a resposta para o problema será a soma de todos os inteiros do vetor dado subtraída de $dp[n][k]$. A complexidade final da solução é $O(N \cdot K)$, já que $dp$ possui estados de complexidade $O(N)$ e $O(K)$, com transições em $O(1)$.

Abaixo se encontram duas maneiras diferentes de se implementar a programação dinâmica; a primeira versão calcula $dp$ recursivamente, e a segunda, iterativamente.

Os casos bases para $dp$ na solução recursiva são: $dp[i][k] = 0$ e $dp[i][j] = inf$ , $i \leq 0, j \neq k$.

Os casos bases para $dp$ na solução iterativa são: $dp[0][0] = 0$ e $dp[0][j] = inf$ , $j \neq 0$.

Confira os códigos abaixo para melhor entendimento:

Solução Recursiva:

Solução Iterativa: