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.
| // Assumindo que todos os sucessores estão em t[i] | |
| // Saindo do planeta x e andando k passos | |
| proximo (planeta x, número k) { | |
| enquanto (k > 0) { | |
| x = t[x]; // avança o x em uma posição | |
| k–; // diminui a quantidade de passos restantes em 1 | |
| } | |
| } |
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).
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int MAXN = 2e5 + 10; | |
| const int MAXLOG = 30; | |
| int prox[MAXLOG + 1][MAXN]; | |
| int main() { | |
| int n, q; | |
| cin >> n >> q; // só usaremos o valor q no futuro | |
| for (int x = 1; x <= n; x++) { | |
| cin >> prox[0][x]; | |
| } | |
| } |
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$$).
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int MAXN = 2e5 + 10; | |
| const int MAXLOG = 30; | |
| int prox[MAXLOG + 1][MAXN]; | |
| int main() { | |
| int n, q; | |
| cin >> n >> q; // só usaremos o valor q no futuro | |
| for (int x = 1; x <= n; x++) { | |
| cin >> prox[0][x]; | |
| } | |
| for (int i = 1; i <= MAXLOG; i++) { | |
| for (int x = 1; x <= n; x++) { | |
| prox[i][x] = prox[i-1][[prox[i-1][x]]; | |
| } | |
| } | |
| } |
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:
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int MAXN = 2e5 + 10; | |
| const int MAXLOG = 30; | |
| int prox[MAXLOG + 1][MAXN]; | |
| int main() { | |
| ios::sync_with_stdio(0);ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); // otimizações de entrada/saída | |
| int n, q; | |
| cin >> n >> q; | |
| for (int x = 1; x <= n; x++) { | |
| cin >> prox[0][x]; | |
| } | |
| for (int i = 1; i <= MAXLOG; i++) { | |
| for (int x = 1; x <= n; x++) { | |
| prox[i][x] = prox[i-1][[prox[i-1][x]]; | |
| } | |
| } | |
| while(q–) { | |
| int x, k; | |
| cin >> x >> k; | |
| for (int i = 0; i <= MAXLOG; i++) { | |
| if (k & (1 << i)) x = prox[i][x]; | |
| } | |
| cout << x << "\n"; | |
| } | |
| } |
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
