Informática - Ideia 01

Escrito por Lúcio Cardoso:

A técnica de compressão de coordenadas consiste, essencialmente, em mapear valores grandes dados em um problema para valores menores, a fim de reduzir gastos de memória e tempo. Vamos ilustrar a ideia com os seguintes exemplos:

Exemplo 1

Dado um vetor $V$ de $N$ números inteiros, calcule a quantidade de inversões em $V$, isto é, a quantidade de pares $(i, j)$ tais que $i < j$ e $V[i] > V[j]$.

Restrições: $N \leq 10^5$ e $1 \leq V[i] \leq 10^9, \forall i \leq N$.

Solução: Perceba que a quantidade total de inversões em $V$ é o mesmo que o somatório, para cada índice $i$, da quantidade de inversões que $i$ participa, ou seja, a quantidade de índices $j$ tais que $i < j$ e $V[i] > V[j]$. Para calcular isso, usaremos a estrutura de dados BIT (ou Binary Indexed Tree) da seguinte maneira: Criamos uma BIT onde cada um de seus índices guardará a quantidade de números em $V$ com valor igual a tal índice. De início, deixamos a BIT vazia e iteramos por cada posição $i$ do vetor, começando de $N$ e indo até 1. Assim, para descobrir de quantas inversões $i$ participa, basta calcular a soma dos valores desde o índice 1 ao $V[i]-1$ na BIT (o total de números menores que $V[i]$ até o momento). Depois, acrescentamos 1 ao índice $V[i]$ da estrutura, realizando o mesmo procedimento nos índices seguintes. Como a BIT realiza as duas operações de soma e atualização em $O(\log{}n)$, a complexidade final será $O(n\log{}n)$. Porém, a BIT precisa de uma posição reservada para cada um dos valores em $V$, que podem ser muito grandes (até $10^9$), e já que criar uma BIT com $10^9$ elementos é muito custoso, precisamos de outra solução.

Observe que como a quantidade de números distintos em $V$ é no máximo $N$, o vetor da BIT possui muitos "espaços vazios". Além disso, o valor de cada elemento em $V$ é irrelevante; o que nos interessa ao calcular as inversões são apenas as relações ($>$ ou $<$) entre tais valores. Queremos então reduzir (comprimir) os números no vetor sem modificar as relações entre eles.

Para isso, vamos inserir cada valor de $V$ em um vetor auxiliar e então ordená-lo. Depois, mapeamos cada número neste vetor para um número menor de acordo com a ordem presente (ou seja, o menor número será mapeado para 1, o segundo menor para 2, etc.), comprimindo, assim, os valores de $V$. Podemos, assim, substituir cada um dos números no vetor original pelos seus respectivos valores mapeados, pois como o vetor auxiliar foi ordenado, as relações entre os números foram mantidas. Utilizando o próprio map do C++, é possível realizar a compressão desejada em $O(N\log{}N)$, e já que o maior valor comprimido de um número em $V$ será $N$, podemos usar a BIT seguindo o mesmo algoritmo descrito acima. A complexidade final será $O(N\log{}N)$. Confira o código para melhor entendimento:

Exemplo 2

Temos um vetor $V$ de $N$ inteiros com seus valores inicialmente iguais a 0. São dados $M$ pares $(i, x)$ $(x \in \mathbb{Z}_+^*)$ indicando que o valor de $V[i]$ foi atualizado para $x$. Os pares são dados em ordem estritamente crescente de $i$. Após isso, $K$ perguntas serão feitas, sendo representandas por um par $(l, r)$. Para cada pergunta, calcule a soma dos valores em $V$ com índices entre (e incluindo) $l$ e $r$.

Restrições: $N \leq 10^9, M \leq 10^5, K \leq 10^5$.

Solução: Novamente, não é eficiente guardar o vetor $V$, já que o valor de $N$ pode ser muito grande. No entanto, há muitos números iguais a 0 no vetor, e como nenhum deles irá contribuir para a resposta das perguntas, podemos enxergá-los como "gaps". Vamos então fazer uma compressão apenas com as posições dadas nos $M$ pares, inserindo cada um deles em um vetor $C$ na ordem em que são dados. Note, assim, que $C$ já estará ordenado pelo valor $i$ (o primeiro elemento) de cada par. Feito isso, comprimimos as $M$ posições dadas, já que pela descrição do problema, são todas distintas (considere que o valor mapeado do índice $i$ num par em $C$ é a própria posição do par neste vetor).

Porém, os números nos índices $l$ e $r$ dados nas perguntas podem ser 0, e, consequentemente, não serão considerados na compressão; logo, a ordem relativa de tais índices com aqueles em $C$ será perdida. Apesar disso, note que se o valor no índice $l$ de uma pergunta, de fato, for 0, a soma no intervalo $[l...r]$ será a mesma que no intervalo $[a...r]$, onde $a$ é o primeiro índice em $V$ — maior ou igual a $l$ —, cujo valor no vetor é positivo. Isso vale porque todos os números entre $a$ e $l$ são 0. De maneira similar para $r$, se o valor em $r$ é 0, a soma em $[l...r]$ será a mesma que em $[l...b]$, onde $b$ é último índice em $V$ — menor ou igual a $r$ —, cujo valor no vetor é positivo. É possível encontrar os valores mapeados de $a$ e $b$ em $O(\log{}M)$ fazendo-se uma busca binária no vetor $C$, para cada uma das perguntas (mais detalhes no código abaixo). De tal forma, conseguimos respondê-las trabalhando apenas com índices do vetor $C$.

A fim de finalizar o problema, precisamos calcular a soma dos valores entre dois índices $l$ e $r$ quaisquer em $C$. Se $x_i$ for o valor $x$ do $i$-ésimo par em $C$, então observe que

$$\sum_{i=l}^r x_i = \sum_{i=1}^r x_i - \sum_{i=1}^{l-1} x_i$$

Portanto, se $soma[i]$ é igual à soma dos valores $x$ desde a posição 1 até $i$,

$$\sum_{i=l}^r x_i = soma[r] - soma[l-1]$$

Logo, é possível calcular a soma referida acima em $O(1)$, precalculando o vetor $soma$ para cada posição no vetor com complexidade $O(M)$ (basta ver que $soma[i] = soma[i-1] + x_i)$. Esta técnica é bastante útil e é conhecida como soma de prefixos. A complexidade final do problema será $O(K\log{}M)$, devido à busca binária realizada em cada uma das $K$ perguntas. Confira o código abaixo para melhor entendimento:

Problemas para praticar

• Arco e Flecha (OBI 2016 - P1 - F2)
• BGSHOOT
• Wowow (Olimpíada Canadense de Computação (CCO) 2010)
• Enemy is weak

Obs.: Os problemas acima utilizam compressão de coordenadas de alguma maneira, porém podem precisar de alguma estrutura de dados (como BIT ou Segment Tree) ou outra técnica.