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