Seletiva IOI 2018 - Dia 2

Se você quiser se preparar para a OBI e seletiva, 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.

Clique aqui para conferir a prova na íntegra *A seletiva da OBI 2017 foi feita para a IOI 2018

Árvore

Comentário escrito por Enzo Dantas

Subtask 1 (20 pontos): $N, Q \le 10^3$

Essa subtask pode ser resolvida simulando linearmente cada query.

Subimos cada vértice linearmente ("de um em um") até o LCA e inserimos todos os elementos do caminho em um array. Feito isso, ordenamos o array em ordem crescente e retornamos o k-ésimo elemento.

 

Complexidade:

Cada query é $O(N)$ para criar o array e $O(NlogN)$ para ordená-lo. Logo, a complexidade final é $O(QNlogn)$.

Subtask 2 (40 pontos): $N, Q \le 10^4$ e $1 \le W_i \le 50$

Conhecimento prévio necessário:

• Lowest Common Ancestor (LCA)

Em problemas com valores pequenos como esse, em que $W_i \le 50$, uma boa intuição é tratar cada valor individividualmente e depois juntá-los de alguma forma.

Nesse caso, imagine que cada vértice tem apenas dois valores possíveis: 0 ou 1. Queremos calcular quantos 1's existem no caminho de $A$ a $B$, para depois podermos juntar os 50 valores e descobrir o k-ésimo.

Calculando quantidade de 1's:

É possível adaptar a sparse table do LCA para guardar quantos 1's existem em cada pulo fazendo $qtd[log][a] = qtd[log-1][a] + qtd[log-1][pai[log-1][a]]$. Ou seja, assim como na sparse table tradicional do LCA, dividimos o pulo em dois e os juntamos, nesse caso com uma adição.

Entretanto, é possível usar uma ideia mais simples: defina $qtd[u]$ = quantidade de 1's de u até a raiz (o vértice 1 será a raiz). A quantidade de 1's no caminho de $A$ a $B$ é equivalente a $qtd[A] + qtd[B] - 2*qtd[LCA] + val[LCA]$ (lembre que estamos assumindo que $val[x]$ = 0 ou 1). Calcular o array $qtd$ é bem simples: percorremos a árvore com uma DFS e fazemos $qtd[u] = qtd[pai[u]] + val[u]$.

Esse mesmo processo pode ser repetido 50 vezes (uma vez para cada valor) e teremos o que precisamos - a quantidade de cada valor no caminho de $A$ a $B$.

Juntando os valores:

Para cada query, criamos um array auxiliar $aux$ de tamanho 50 tal que $aux[i]$ = quantidade de valores $i$ no caminho de $A$ a $B$. Em seguida, percorremos esse array linearmente até achar o índice do primeiro prefixo que possui uma soma maior ou igual a $K$, e esse índice é a resposta da query.

Complexidade:

Em cada query temos que achar o LCA dos dois vértices e percorrer o array $aux$ de tamanho 50. Logo, cada query é $O(logn + 50)$. Além disso, calcular o array $qtd$ para cada valor é $O(50N)$. Assim, a complexidade final fica $O(Q(logn+50)+50N)$ = $O(50(Q+N))$.

 

 

Subtask 3 (20 pontos): $N, Q \le 10^5$

Conhecimento prévio necessário:

• Euler Tour
• Algoritmo de MO
• Busca em Seg

Aqui, é importante pensar em casos especifícos do problema ($K_i=1$, por exemplo, onde teríamos que pegar o mínimo). Um caso muito importante em problemas de caminho em árvore é imaginar que o problema é em um array em vez de em uma árvore. Nesse caso, o problema vira "Ache o k-ésimo menor elemento em intervalos $[L,R]$". Esse problema pode ser resolvido de 2 maneiras: merge sort tree ou MO.

A ideia da merge sort tree não é facilmente aplicável na árvore e possui uma implementação complicada por si só. Além disso, os limites dessa e da próxima subtask sugerem que a solução esperada para essa subtask possui complexidade $O(N \sqrt{N})$. Sendo assim, pensamos no algoritmo de MO. A solução possui 3 passos: linearizar a árvore, aplicar o MO, e achar o k-ésimo.

Linearizando a árvore:

Uma ideia conhecida em problemas de caminho em árvore que usam Euler Tour é "cancelar" vértices que estão no meio da ordem da linearização mas não estão no caminho desejado. Por exemplo: imagine que queremos a soma dos vértices da raíz até algum vértice $u$. O jeito de linearizar a árvore para responder tais perguntas é somar o valor quando entramos no vértice e subtrair o valor quando saímos. Assim, o valor de qualquer subárvore no segmento que vai da raíz até $u$ será anulado e os valores no caminho que realmente importa estarão disponíveis. Analogamente, podemos inserir o vértice na linearização tanto na entrada como na saída e cancelaremos os duplicados.

MO:

Com a árvore linearizada, o caminho entre vértices $a$ e $b$ é o intervalo $[tout_a, tin_b]$ (assumindo que $tout_a$ está a esquerda de $tin_b$). Logo, temos o seguinte problema: retorne o k-ésimo menor elemento não duplicado em vários intervalos $[L,R]$ de um array. A ideia do MO aqui é análoga à do problema Distinct Values Queries do CSES: mantemos um mark dos elementos que já estão inclusos no intervalo atual e contamos apenas os que aparecem uma única vez. Ou seja, quando encontramos um duplicado, o removemos. Um pequeno detalhe é que podem haver elementos de mesmo valor no problema. Para contornar isso, salvamos um pair (valor, vértice) na linearização e removemos vértices duplicados em vez de valores duplicados.

Achando o k-ésimo:

É possível usar BIT ou Segment Tree aqui, mas usaremos Segment Tree para simplificar a explicação. A x-ésima folha da Seg guardará quantos valores x existem no intervalo atual do MO, então quando adicionamos ou removemos um valor x, fazemos seg.upd(x, ±1). Finalmente, para achar o k-ésimo elemento do intervalo atual do MO, fazemos uma busca na Seg.

Complexidade:

Complexidade do MO: toda vez que movemos um ponteiro fazemos uma operação em $O(logN)$ na Seg. Logo, como movemos ponteiros $O(\sqrt{N}(Q+N))$ vezes em um MO normal, a complexidade desse MO será $O(\sqrt{N}(Q+N)logN)$.

A complexidade da linearização é $O(N)$, então a complexidade final será a complexidade do MO, que é $O(\sqrt{N}(Q+N)logN)$.

 

Subtask 4 (20 pontos): Nenhuma restrição adicional

Conhecimento prévio necessário:

• Segment Tree persistente
• Busca em Seg
• Lowest Common Ancestor (LCA)

A ideia dessa solução é manter, para cada vértice, uma seg dos elementos no caminho desse vértice até a raiz. Assim, para uma query entre os vértices $a$ e $b$ com lca $u$, podemos fazer uma busca binária na resposta e fazer uma busca nas Seg's de $a$, $b$, e $u$ para verificar se achamos o k-ésimo. Entretanto, cada query teria uma complexidade de $O(log^{2}N)$, o que fica bem no limite de tempo $(20*20*5*10^5 = 2*10^8)$. Caso seja necessário, com o intuito de otimizar a busca, podemos fazer uma busca nas três segs simultaneamente, o que tem uma complexidade de $O(logN)$.

Para manter uma Seg para cada vértice, usamos uma Seg persistente em que cada vértice tem uma versão que aponta para a versão do pai e insere seu valor com um update persistente na Seg.

Complexidade:

Construir cada versão da Seg persistente é $O(logN)$, então construir toda a Seg é $O(NlogN)$. Cada query é respondida com uma busca binária, então a complexidade das queries é $O(QlogN)$. Assim, a complexidade final é $O((N+Q)logN)$.

Clique aqui para conferir o código