Aula por João Pedro Castro
Nessa aula nós vamos falar sobre a ideia do “Binary Lifting”. Uma técnica utilizada para resolver problemas onde cada elemento só tem um sucessor (ou ancestral), sendo possível encontrar o k-ésimo sucessor de um elemento em tempo logarítmico. A ideia consiste em fazer um preprocessamento de forma inteligente, com uma ideia similar a da programação dinâmica, para depois responder à perguntas rapidamente.
Problema – Planets Queries I
Em cada planeta existe um teletransportador para outro (ou o mesmo) planeta. Responda $$q$$ perguntas da forma: começando em um planeta $$x$$ e viajando por $$k$$ teletransportadores, em que planeta você irá parar?
Primeiramente, vamos pensar em uma forma trivial de resolver o problema. Como sabemos onde vamos parar saindo de cada planeta andando $$1$$ passo, podemos simular em $$O(k)$$ aonde vamos parar andando $$k$$ passos. Uma forma de fazer isso é simplesmente guardando a posição atual e trocando ela pelo seu sucessor (o teletransportador localizado na posição atual) $$k$$ vezes. Segue um pseudo-código para melhor entendimento.
https://gist.github.com/ortsc/1794d93f97a446d69ca1391a2eccbcd5
Essa é uma implementação que funciona, mas é muito lenta para limites altos. Porém existem propriedades nessa trivialidade que podemos levar para a nossa solução final, sendo a principal delas avançar uma quantidade de posições que somadas equivalem à $$k$$ avanços, algo intuitivo e que realmente está correto, pois cada avanço individual contribui para o progresso geral, e a soma de múltiplos avanços resulta no mesmo deslocamento final que avançar tudo de uma só vez (por exemplo, avançar 4 passos e depois 2 passos é o mesmo que avançar 6 passos).
O real truque do Binary Lifting vem a partir da ideia de ao invés de avançar pelas potências $$1$$ (ou seja, o próprio $$1$$), vamos avançar pelas potências de $$2$$. Como explicado na aula sobre Bitmask, todo número pode ser escrito como uma soma de potências de $$2$$, afinal essa é exatamente a representação binária de um número, logo, ao passarmos por todas as potências de dois e escolhermos se queremos ou não andar até o $$2^i$$ sucessor, é possível andar exatamente qualquer quantidade inteira de avanços.
O primeiro passo deve ser preprocessar o $$2^i$$ sucessor de cada planeta, para isso vamos usar uma ideia similar à da Programação Dinâmica, decidindo o caso base de cada planeta para só depois calcular o resto. O caso base vai ser algo dado no problema, o próprio $$2^0$$ sucessor de cada planeta $$x$$: o planeta que você chega ao entrar no teletransportador em $$x$$. O código em C++ abaixo é uma das maneiras de guardar esse sucessor (estou usando o modelo de input do problema tratado).
https://gist.github.com/ortsc/a487a2f9ac8dd30bb31cbdf48de65eff
O que estamos fazendo é declarar um vetor $$prox$$, que tem as dimensões de $$MAXLOG + 1$$ por $$MAXN$$. A definição dele pode ser escrita como:
$$prox[i][x] = \text{aonde vamos parar saindo de x e andando por $2^i$ teletransportadores}$$
Por isso usamos o $$prox[0][x]$$ como caso base, já que ele vai ser o planeta que paramos logo após entrar em um teletransportador. O motivo de usarmos as dimensões também é bem simples, já que no máximo iremos precisar andar $$10^9$$ passos (um limite dado no enunciado do problema), e o $$log2(10^9) \approx 30$$, e como o array é 0-indexado é necessário adicionar mais um, tornando a verdadeira “altura” da matriz em $$31$$. Já para a “largura”, ela é só a quantidade máxima de planetas.
Agora, precisamos achar uma maneira de inteligentemente calcular todos os valores (pelo menos os necessários) dentro dessa matriz. Para isso, vou usar a propriedade que vimos na solução trivial anteriormente: andar $$p$$ passos, depois mais $$p$$ passos, para assim andar $$2p$$ passos. Imagine que você quer encontrar o $$prox[1][x]$$, ou seja, onde você vai parar andando $$2^1 = 2$$ passos. Para fazer isso, você pode descobrir onde você vai parar andando $$1$$ passo (algo que você já tem guardado), e depois buscar onde você vai parar andando mais $$1$$ passo saindo desse outro ponto. Exemplificando, diga que $$a = prox[0][x]$$, então podemos dizer que $$prox[1][x] = prox[0][a]$$. De uma forma mais geral:
Para descobrir $$prox[i][x]$$:
- $$a = prox[i-1][x]$$
- $$b = prox[i-1][a]$$
E a resposta que nós buscamos vai ser $$b$$, já que andamos $$2^{i-1}$$ passos, e depois mais $$2^{i-1}$$ passos: $$2^{i-1} + 2^{i-1} = 2 \cdot 2^{i-1} = 2^i$$. Podemos escrever toda essa equação em uma linha, mas você pode usar a forma que preferir: $$prox[i][x] = prox[i-1][prox[i-1][x]]$$.
Para calcular tudo usaremos um loop dentro do outro, com complexidade de $$O(log2(10^9) \cdot N)$$. Não incluiremos o $$i = 0$$ pois já temos ele calculado (e teríamos problemas já que $$0 – 1= -1$$).
https://gist.github.com/ortsc/3b4d579f2f6c0aa99377244b021a9adb
Por fim, só precisamos dividir o $$k$$ de cada query em soma de potências de $$2$$, uma técnica novamente já mencionada na aula de Bitmask, e então avançar $$2^i$$ posições para cada bit na posição $$i$$ que estiver ativo, faremos isso em um loop de $$0$$ até $$MAXLOG$$ checando se o bit está ativo pelo $$&$$ binário. A implementação completa se encontra abaixo:
https://gist.github.com/ortsc/b72937ec70f8eda59671ab8eca3dc558
Com essa ideia deve ser possível entender o Binary Lifting, e resolver problemas relacionados.
Problemas para praticar
É importante perceber que enquanto não existem muitos problemas que só usam Binary Lifting, ela é uma ideia imprescindível para diversas técnicas mais avançadas, como o próprio LCA (Menor Ancestral Comum).
*Extremamente difícil