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