Aula - Binary Lifting

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
	}
	}

view raw

sucessork_trivial

hosted with ❤ by GitHub

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];
	}
	}

view raw

parte1-binlift.cpp

hosted with ❤ by GitHub

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]];
	}
	}
	}

view raw

parte2-binlift.cpp

hosted with ❤ by GitHub

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";
	}
	}

view raw

parte3-binlift.cpp

hosted with ❤ by GitHub

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

Planet Queries I

Company Queries I

*Planet Queries II

*Extremamente difícil