Comentário Seletiva 2017 – Seleção

Comentário por Murilo Maeda

Link do problema

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

Segue o código para maior esclarecimento: