Seletiva IOI 2018 - Dia 1

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

Seleção

Comentário escrito por Murilo Maeda

Conhecimento prévio necessário:

Busca binária na resposta

Nesse problema há duas dificuldades principais: o tamanho grande da matriz, então não podemos nem percorrê-la nem mantê-la em uma matriz, e a forma desorganizada que os números aparecem na matriz, não há um padrão que nos permita concluir coisas sobre a posição e organização de números na matriz.

Para resolver o primeiro problema, basta simplesmente não mantermos a matriz. Vamos manter somente os vetores $x$ e $y$ e quando precisarmos de um valor, só somamos os valores necessários de $x$ e $y$ .

Agora, vamos resolver o segundo problema.

Note que, como queremos encontrar os $K$ menores números, a posição deles na matriz não importa. Por isso, podemos ordenar os vetores $x$ e $y$ , do menor para o maior e formar a matriz $M$ na qual $M_{ij} = x[i] + y[j]$ . Agora, temos duas propriedades dessa matriz: em uma mesma linha, se a percorrermos de $1$ a $N$ , os valores estarão dispostos em ordem não decrescente. O mesmo ocorre quando percorremos uma coluna de $1$ a $N$ .

A partir disso, vamos analizar o que acontece quando queremos saber quantos valores menores ou iguais a um determinado valor $c$ estão na matriz $M$ . Note que, se encontrarmos em uma determinada linha $l$ o índice $k$ de modo que o valor $M_{lk}$ é o maior valor maior ou igual a $c$ na linha $l$ , nas linhas com índice menor que $l$ , o maior valor maior ou igual a $c$ vai estar em um índice maior ou igual a $k$ , já que os valores em uma coluna e em uma linha estão em ordem não decrescente. Por isso, para um determinado número $c$ , para descobrir quantos valores menores ou iguais a ele estão na matriz $M$ , podemos simplesmente fazer o seguinte: passamos pela linha n e pegamos $k_n$ e o somamos no número de valores menores ou iguais a $c$ . Para uma linha $l$ : a percorremos a partir do índice $k_{l+1}$ enquanto os valores forem menores ou iguais a $c$ . Paramos no índice $k_{l}$ e somamos $k_l$ no número de valores menores ou iguais a $c$ .

Com isso, podemos calcular em $O(n)$ quantos valores são menores ou iguais a $c$ na matrisz $M$ . Então, basta fazermos uma busca binária na resposta, tentando encontrar o valor que queremos. Fazemos isso chutando o número da resposta, checando quantos valores são menores ou iguais a ele em $M$ e em seguida comparando esse resultado com $k$ .

Clique aqui para conferir o código

Caminhos Mínimos

Comentário escrito por Enzo Dantas

Conhecimento prévio necessário:

Dijkstra

Primeiramente, indagamos se, para um valor extremamente grande de $K$ , $d(1,u) = p(1,u)$ para todo vértice $u$ . Isso aconteceria pois cada aresta teria peso aproximadamente igual e o Dijkstra viraria uma BFS. Se o Dijkstra tende a virar uma BFS com o aumento do $K$ , imaginamos se essa propriedade é monotônica, ou seja, se a partir de um certo valor de $K$ temos $d(1,u) = p(1,u)$ para todo $u$ , e abaixo dele a condição não é válida. Se isso fosse verdade, poderíamos fazer uma busca binária no $K$ e teríamos a nossa resposta. Vamos então tentar provar que isso é verdade.

Defina $A$ como o menor caminho em arestas e $B$ como o menor caminho em peso de arestas do vértice 1 até um vértice qualquer $u$ . Assuma que $W_B + qtd_B*K < W_A + qtd_A*K$ . Juntando os dois temos $K < \frac{W_A - W_B}{qtd_B - qtd_A}$ . Logo, abaixo do valor $\frac{W_A - W_B}{qtd_B - qtd_A}$ temos que $A \neq B \implies d(1,u) \ne p(1,u)$ , e acima dele temos $d(1,u) = p(1,u)$ , como queríamos demonstrar.

Clique aqui para conferir o código