Seletiva IOI 2020 - Dia 4

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 2019 foi feita para a IOI 2020

Torneio

Escrito por Caique Paiva

Conhecimento Prévio Necessário:

Problemas Interativos
Grafos

Esse problema foi um pouco diferente de outros problemas da seletiva. Ele é um problema interativo de grafos, e todas as subtasks são disjuntas do problema final, então, vamos resolver cada subtask de cada vez. Uma coisa que vai ser útil em cada subtask é ver o problema como um grafo direcionado completo, onde $i \rightarrow j$ se, e somente se, $i$ ganha de $j$ . Para todas as subtasks, defina query como a interação de vencedor_partida.

Subtask 2:

Conhecimentos Prévios Necessários:

Algoritmo de Mergesort

Veja que, se olharmos na linguagem de grafos, o problema pergunta qual que é o grau de saída de todos os vértices. Portanto, perceba que o grau de saída de todos os vértices são diferentes, pois caso exista dois vértices $i$ e $j$ tal que $deg_{out} i = deg_{out} j$ , suponha sem perda de generalidade que $i$ ganha de $j$ , portanto todo mundo que $j$ ganha, $i$ também vai ganhar, logo $deg_{out} i \ge deg_{out} j + 1$ , absurdo!

Com isso, como $0 \le deg_{out} i \le n-1$ , temos que $deg_{out} 1, deg_{out} 2, \cdots , deg_{out} n$ é uma permutação de $[0, 1, 2, \cdots , n-1]$ , então, se ordenamos os vértices por grau de saída, vamos saber o valor de cada um deles! Então o problema vira ordenar os vértices por grau de saída. Mas isso é simples, pois se $i$ ganha de $j$ , então $deg_{out} i > deg_{out} j$ , logo, se $i$ ganha de $j$ , então $i$ está numa posição maior que o $j$ na ordenação, podemos fazer um mergesort para calcular isso em $O(Nlog)$ , que passa na quantidade de queries!

Clique aqui para ver o código

Subtask 3 e 4:

Veja que, caso $i$ ganhe de $j$ , então $j$ não pode ser resposta. Logo, vamos fazer o seguinte algoritmo. Primeiro, faça $s = \{ 1, 2, 3, \cdots, n \}$ .

Caso tamanho de $s$ seja $1$ , pare o algoritmo. Caso contrário, seja os valores do conjunto $s_1, s_2, \cdots, s_t$ . Faça $query(s_1, s_2), query(s_3, s_4), \cdots$ , ou seja, fazendo as queries em pares até o algoritmo parar, e tire do conjunto $s$ quem perdeu, ou seja, estamos mantendo somente as possíveis respostas no conjunto.

Seja $v$ o elemento que sobrou no conjunto. Agora, faça as perguntas $query(v, 1), query(v, 2), \cdots, query(v, n)$ . Caso $v$ realmente tenha ganhado de todo mundo, imprima $v$ como resposta, caso contrario, imprima que não tem. Veja que cada passo do algoritmo gasta tamanho de $s$ dividido por 2 queries, e diminui o tamanho do conjunto pela metade, e como o conjunto começa com $n$ elementos, a quantidade de queries que esse algoritmo gasta é $O( \frac{N}{2} + \frac{N}{4} + \cdots + \frac{N}{2^k} )$ , onde $k = \lfloor \log_2 n \rfloor$ . além disso, o segundo passo do algoritmo gasta $N-1$ queries, portanto, o algoritmo todo roda em $O(N + \frac{N}{2} + \frac{N}{4} + \cdots) < 2N$ , que passa na quantidade de queries.

Clique aqui para ver o código

Subtask 5:

Vamos provar o seguinte lema:

Lema: Em um grupo de $10$ pessoas, existe alguém que perdeu mais que 4 partidas

Prova: Suponha por absurdo, que no grupo de $10$ pessoas, todos perderam no máximo $4$ partidas. Traduzindo para a linguagem de grafos, temos que $deg_{in} v \le 4$ para todo vértice, e portanto, $deg_{out} v \ge 5$ , pois a quantidade de partidas para cada vértice é $9$ . Portanto, sabemos que

$4*10 \ge \sum deg_{in} v = \sum deg_{out} v \ge 5*10$

Absurdo! Logo, em um grupo de $10$ pessoas, existe alguém que perdeu.

Dado esse lema, vamos fazer o seguinte algoritmo. Seja $s$ o conjunto das nossas possíveis respostas. Comece com $s = \{ 1 \}$ , e crie um vetor chamado $deg[N]$ , que guarda em $deg[i]$ qual é o $deg_in$ do vértice $i$ .

Passo $i$ : Vamos ver se $i$ é uma possível resposta ou não. Seja $s_1, s_2, \cdots , s_t$ os elementos de $s$ . Faça as perguntas $query(i, s_1), query(i, s_2), \cdots , query(i, s_t)$ , e para quem perder em cada partida, aumente o $deg[x]$ desse vértice em $1$ . Bote $i$ em $s$ , e, para todo vértice em $s$ , caso $deg[x] > 4$ , tire o do conjunto. Pare o algoritmo quando $i = n$ .

Por conta do lema, temos que o tamanho de $s$ sempre é menor ou igual que $9$ , portanto, fazemos no máximo $9N$ queries, pois, em cada passo, fazemos $t$ queries, onde $t$ é o tamanho do conjunto $s$ , e $t \le 9$ . Veja que, para todo elemento fora de $s$ , $deg_{in} v > 4$ , logo ele não é resposta, então, basta testar para os elementos em $s$ para ver se eles são respostas, logo, para cada elemento de $s$ , faça $query(s_i, 1), query(s_i, 2), \cdots, query(s_i, n)$ , e caso $deg_{in} s_i > 4$ , tire ele do conjunto. Nesse passo, fizemos no máximo $9N$ queries, pois temos no máximo $9$ elementos em $s$ . Daí, $s$ seja a resposta do nosso problema. No total, fizemos no máximo $18N$ queries, que passa no nosso problema.

Clique aqui para ver o código

Subtask 6:

Lema: Caso um torneio tenha um ciclo, então ele tem um triângulo (Ou seja, um cíclo de tamanho 3).

Prova: Suponha que o nosso grafo não tem ciclo de tamanho $3$ . Seja $C >3$ o tamanho do menor ciclo do grafo. Seja $v_1, v_2, \cdots, v_c$ os vértices desse ciclo. Veja os vértices $v_1, v_2, v_3$ . Se $v_3$ ganhar de $v_1$ , então nós achamos o nosso triângulo! Caso contrário, ou seja, $v_1$ ganhe de $v_3$ , então, $v_1, v_3, \cdots , v_c$ também é ciclo, e tem tamanho $C-1$ , absurdo, pois $C$ é o ciclo de menor tamanho (Veja que esse argumento não funcionaria para $C = 3$ pois já estamos usando a aresta $v_1, v_3$ no ciclo).

Logo, ao invés de acharmos um ciclo qualquer, podemos ir atrás de um triângulo! Primeiro, vamos retirar todos os vértices com $deg_{out} = 0$ . Podemos descobrir quais são esses vértces fazendo a pergunta de quantidade de vitórias para cada vértice $v$ . Depois de feito isso, pegue o vértice com menor $deg_{out}$ , chame-o de $v$ , e divida o grafo em $2$ grupos, os que vencem de $v$ e os que perdem de $v$ . Para descobrir esses vértices, basta fazer $query(i, v)$ para todo $i$ . Veja que, como nós retiramos os vértices com $deg_{out} = 0$ do grafo, então nem o grupo de vencedores e nem o grupo de perdedores estão vazios.

Lema 2: Alguém que perde de $v$ vai ganhar de alguém que ganha de $v$ .

Prova: Suponha por absurdo que todo mundo que perde de $v$ também perde de todo mundo que ganha de $v$ . Seja $u$ o vértice de $deg_{out}$ máximo do grupo de perdedores. Veja que, como $u$ perde para todo mundo que ganha de $v$ , então ele só pode ganhar de quem perde para $v$ , ou seja, $deg_{out} u < deg_{out} v$ , absurdo, pois escolhemos $v$ para ser o vértice com $deg_{out}$ mínimo.

Portanto, seja $u$ o vértice de $deg_{out}$ máximo no grupo dos perdedores. Como provado acima, ele vai ganhar de alguém do grupo dos vencedores, logo, basta fazer $query(i, u)$ para todo vértice no grupo dos vencedores, até achar alguém que perde para $u$ . Feito isso, nós vamos ter achado nosso triângulo, e o problema acaba fazendo menos de $3N$ queries, que passa nas constantes do problema

Clique aqui para ver o código

Ratinhos

Escrito por Caique Paiva

Subtask 2 ( $K_j = 2$ ):

Conhecimentos Prévios Necessários:

Algoritmo de LCA

Vamos dar uma olhada num exemplo qualquer.

Temos $5$ caixas, as caixas $[1, 14], [2, 9], [3, 5], [6, 8], [10, 13]$ . Temos também um queijo em $4$ , e outro em $11$ . Podemos ver então, que a resposta desse caso é $3$ , pois podemos começar com o ratinho em $4$ , quebrar as caixas $3$ , $2$ e $5$ , e então ir para a casinha $11$ . Veja como nós construímos essa resposta, começamos em um queijo, formos quebrando as caixinhas para "cima", até conseguir ter um caminho para chegar na casinha do outro queijo, quebrando umas casas para "baixo". Os termos "cima" e "baixo" vem de acordo com a profundidade das caixas. Ué, cima, baixo, profundidade? A maneira que a gente construiu esse caminho lembra muito como a gente constrói caminhos em árvores!

Então a ideia vai ser o seguinte, vamos criar uma árvore de $n+1$ vértices, onde a raiz dessa árvore vai ser o vértice $0$ , e vamos criar uma caixa imaginária gigantesca, que contém todas as outras caixas. Então, para cada $i$ , o pai dele vai ser $j$ , onde, se eu furar a caixa $i$ , eu vou direto para a caixa $j$ . A definição formal é bem feia, mas basta ver o exemplo para as caixas acima que vai ficar bem mais claro:

Vamos chamar aquela caixa que encobre todas as outras de $0$ . Então, se eu sair da caixa $1$ (A caixa $[2, 9]$ ), aonde eu vou parar? Para a caixa $0$ , que é o pai dela. Se eu furar a caixa $2$ , para qual caixa eu vou? Para a caixa $1$ . E assim vai. E com essa interpretação, o problema ficou muito simpes.

Temos uma árvore de $N$ vértices, e $Q$ queries. Na query $j$ , recebemos $k_j$ vértices. Sua tarefa é achar o menor caminho que passa por todos os vértices selecionados.

Vamos ver como resolver esse problema na próxima subtask, mas, para resolver a subtask de $k_j = 2$ , basta pegar os dois vértices, e calcular a distância deles na árvore, e podemos fazer isso com algoritmo de LCA.

Clique aqui para ver o Código

Subtask 4:

Conhecimentos Prévios Necessários:

Para essa subtask, vou explicar o conceito de Árvores Virtuais. Caso queria saber mais sobre, veja esse vídeo no youtube. Imagine que temos uma query com os vértices $v_1, v_2, \cdots, v_k$ , então, queremos achar o menor caminho que passa por todos esses vértices. Veja que qualquer caminho que passa por todos esses vértices, também vai ter que passar pelo LCA dois a dois de todos os vértices (Ou seja, o caminho passa pelo LCA( $v_1, v_2$ ), LCA( $v_1, v_3$ ), LCA( $v_2, v_3$ ), e assim vai). Então, vamos definir uma árvore virtual:

Seja $G$ uma árvore e $v_1, v_2, \cdots, v_k$ vértices escolhidos em $G$ . A árvore virtual $T$ desses vértices vai conter $v_1, v_2, \cdots, v_k$ e todos os LCA dois a dois desses vértices. Além disso, as arestas desse grafo tem pesos, e a $dist(u, v)$ na árvore virtual é a mesma que a distância de $(u, v)$ na árvore original.

Certo, como construir essa árvore? Para isso, vamos pegar o tempo de entrada da dfs começando por $0$ de todo vértice, ordene $v_1, v_2, \cdots, v_k$ pelo tin, e então, pegue $LCA(v_1, v_2), LCA(v_2, v_3), \cdots , LCA(v_{k-1}, v_k)$ , coloque eles num vetor junto com $v_1, v_2, \cdots, v_k$ , ordene por tin de novo, e então, teremos vértice $u_1, u_2, \cdots, u_{2k-1}$ , e então, adicione a aresta $u_i, u_{i+1}$ com peso $dist(u_i, u_{i+1})$ .

Esse algortimo constrói a árvore que queriamos. Basta ver que, se eu tenho um par $v_i, v_j$ , $LCA(v_i, v_j) = LCA(v_i, v_{i+1}, \cdots , v_j)$ , que então vai ser o LCA de algum dois vértices consecutivos desse intervalo (De novo, caso queria mais detalhes sobre porque isso funciona, veja o vídeo acima).

Perfeito! Construimos nossa árvore virtual em $O(klog k)$ , onde $k$ é a quantidade de vértices da query, e então, reduzimos a query para: Dado uma árvore, qual é o menor caminho que passa por todos os vértices dela? E agora para resolver isso é simples. Como eu vou passar por todos os vértices da árvore, eu vou passar por todas as folhas, então, o que eu posso fazer é: Escolher duas folhas $u, v$ , pegar o caminho entre elas, e então, para cara vértice no caminho de $u$ até $v$ , eu pego todos os vértices da subárvore dele que não estão no caminho, passo por eles e volto para esse vértice, e então prossigo no caminho. Esse algoritmo vai percorrer por todos os vértices, e tem tamanho $2*($ soma dos pesos de todas as arestas do grafo $) - dist(u, v)$ . Portanto, o melhor par $(u, v)$ que podemos escolher, é o par com $dist(u, v)$ máximo! Ou seja, basta rodarmos um algoritmo de achar o diamêtro na árvore virtual, que nós temos a resposta da query, e o algoritmo de diâmetro é $O(k)$ !