Seletiva IOI 2020 - Dia 3

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

Aptidões

Subtask 1-5 ( $Q = 1$ )

Primeiro vamos ver como resolver o problema tendo apenas uma query. Sendo assim, vamos falar que o valor de cada competidor é $val_i = T*t_i + P*p_i$ ; agora queremos selecionar os competidores de forma a maximizar a soma dos valores.

Podemos ver o problema como um grafo bipartido, em que ligamos o competidor $i$ (parte da esquerda do grafo) com todos os $K_i$ baldes $j$ (parte direita do grafo). Temos que escolher algumas arestas de como que cada vértice tenha no máximo 1 aresta escolhida conectando a ele e a soma dos valores dos vértices da esquerda seja máxima.

Isso parece com algum outro problema? Sim, queremos encontrar um matching com a soma máxima. Não só um matching, mas um matching máximo com soma máxima, ou seja, o matching que estamos procurando tem o mesmo tamanho do matching máximo (com maior quantidade de vértices).

Isso acontece porque se temos algum caminho aumentante, então podemos aumentar o tamanho do matching (e portanto aumentar a soma dos valores); então o matching de soma máxima também é um matching máximo.

Vamos pensar em como normalmente fazemos o problema geral de bipartite matching máximo: temos os vértices em alguma ordem arbitrária $1, 2,...,N$ e vamos chamando uma função $add(i)$ que tenta adicionar o vértice $i$ no matching encontrando um caminho aumentante partindo de $i$ , e portanto, colocar ele no matching sem remover nenhum vértice que já está no matching. Perceba que quando eu chamo $add(i)$ , eu já tentei colocar no matching todos os vértices $1,2,...,i-1$ , então ao tentar colocar $i$ , não pode acontecer se eu remover algum deles do matching.

Primeiro, vamos criar um array $id_1,...,id_N$ para reindexar os competidores ordenando eles em ordem decrescente de $val$ : $val_{id_1} \geq val_{id_2} \geq ... \geq val_{id_N}$ . Perceba que sempre vale a pena colocar o vértice $id_1$ no matching (considerando que ele tem pelo menos uma aresta), porque caso ele não esteja, podemos remover algum outro vértice com um valor menor e adicioná-lo. Considerando que $id_1$ está no matching, sempre vale a pena tentar colocar o $id_2$ no matching de um modo que não removemos o $id_1$ pelo mesmo motivo.

Continuando desse jeito, sempre vale a pena tentar colocar o vértice $id_i$ no matching sem remover os vértices $id_1,id_2,...,id_{i-1}$ . Ou seja, vamos tentando adicionar os vértices na ordem decrescente de valor chamando $add(id_1)$ , depois $add(id_1)$ ... até $add(id_N)$ e somando quando conseguimos de fato adicionar o vértice.

Prova mais formal

Seja $C_i$ o conjunto dos vértices no matching usando apenas vértices até o $id_i$ e $soma(C_i)$ a soma dos valores desses vértices.

Digamos que temos já sabemos $C_{i-1}$ e queremos encontrar $C_i$ .

Já que o matching com soma máxima é um matching máximo, ao adicionar o vértice $id_i$ temos 2 casos: $|C_i| = |C_{i-1}|\rightarrow$ não vale a pena colocar o vértice $id_i$ em $C_i$ , pois caso ele fosse colocado, eu teria que remover um vértice que já está em $C_{i-1}$ e tem o valor maior que $val_{id_i}$ .
Portanto, $C_i = C_{i-1}$ .

$|C_i| = |C_{i-1}|+1 \rightarrow$ o tamanho do matching máximo aumentou em 1, então existe um caminho aumentante partindo de $id_i$ .
Sabemos que a diferença $soma(C_i) - soma(C_{i-1})$ é no máximo $val_{id_i}$ e podemos chegar nesse valor se simplesmente adicionamos $id_i$ ao matching $C_{i-1}$ sem remover nenhum vértice que já está nele usando o caminho aumentante.
Portanto, $C_i = C_{i-1} \cup {id_i}$ .

[collapse]

Cada vez que chamamos que chamamos $add(id_i)$ é $O(M)$ pois resetamos o vetor de marcados e no pior dos casos passamos uma vez por todos os vértices que já estão no matching até agora, nunca por algum antes de $id_i$ que não está no matching até agora. Então no total chamamos $add(id_i)$ $N$ vezes, totalizando $O(N*M)$ para uma única query.

Obs: Isso passa em todas as parciais até a 5.

Subtask 6-8 ( $M \leq 15$ e $K_i = M$ )

Essas subtasks possuem uma solução muito diferente do problema inteiro e das subtasks anteriores, então não iremos falar dela nesse editorial. A ideia usada nelas é de fazer convex hull para encontrar os melhores $M$ competidores em cada query.

Para $M = 1$ é um convex hull mais direto, para $M = 15$ precisamos fazer $15$ camadas do convex hull. Ou seja, faz um convex hull, tira todos os vértices que estão nele, faz outro convex hull com os que sobraram, tira eles de novo... Se um competidor não está em nenhuma das 15 camadas, então sempre vai existir pelo menos 15 competidores melhores do que ele.

Subtask 9 (Sem restrições adicionais)

Não temos tempo para fazer um matching bipartido para cada query, então temos que fazer algo mais inteligente.

Primeiro, o valor em si de $T$ e $P$ não importa, o que importa para saber qual o matching máximo é a razão $T/P$ . Além disso, o valor de cada $val_i$ também não importa, e sim a ordem deles. Cada valor de $T/P$ vai equivaler a um vetor $id = id_1,...,id_N$ , mas perceba que muitos $T/P$ vão ter o mesmo $id$ . Quantas ordens diferentes podem existir?

Teremos no máximo $N^2$ ordens diferentes porque cada par $i,j$ vai trocar no máximo uma vez enquanto $T/P$ aumenta. Considerando que $p_i > p_j$ e $t_i < t_j$ , então $i$ começa ganhando (quando $T/P$ é pequeno) e para encontrar quando eles trocam: $t_i*T + p_i*P < t_j*T + p_j*P \Rightarrow T(t_i-t_j) < P(p_j-p_i) \Rightarrow (p_j-p_i)/(t_i-t_j) > T/P$ . Eles trocam quando $T/P = (p_j-p_i)/(t_i-t_j)$ , então quando chegarmos nisso, basta remover a aresta de $i$ e chamar $add(j)$ para tentar adicionar ele no matching (caso ele não já esteja).