Bitmask

Escrito por Lawrence Melo

Bitmask (Máscara de bits) é uma técnica de força bruta utilizada para testar, de forma mais eficiente, todas as possibilidades de uma determinada situação. A bitmask se baseia na representação binária de um número, por exemplo, $1001010_{2}$ $= 74$ , onde os bits são indexados do $0$ e da direita pra esquerda.

Já que em cada bit do número só é possível encontrar os valores $0$ ou $1$ , podemos usar esse fato para representar situações. Por exemplo, suponha que queremos representar quais cidades já foram visitadas em uma viajem à 6 cidades distintas. Se já visitamos as cidades $3$ e $1$ , representamos a bitmask como $bitmask = 01010_{2} = 10$ . Se não visitamos nenhuma cidade $bitmask = 000000_{2} = 0$ . Da mesma forma, caso todas as cidades tenham sido visitadas $bitmask = 111111_{2} = 63 = 2^{6} - 1$ .

Manipulação de bits

Para avançarmos em bitmask é necessário usarmos algumas operações binárias que são essenciais.

Checar se o bit $j$ de um número $n$ está ligado:

Para checar se o bit $j$ está ligado, basta olhar se $n$ & $2^{j}$ é maior que $0$ , veja and binário.

	bool ligado(int n, int j)
	{
	if(n & (1 << j)) return true;
	else return false;
	}

view raw

ligado.cpp

hosted with ❤ by GitHub

Ligar o bit $j$ de um número $n$ :

Para ligar o bit $j$ , basta fazer $n = n$ | $2^{j}$ , veja or binário.

	void ligar(int &n, int j)
	{
	n = n \| (1 << j);
	}

view raw

ligar.cpp

hosted with ❤ by GitHub

Exemplos de uso de Bitmask

Exemplo 1

Você tem $n$ questões. Você estimou a dificuldade da i-ésima questão como $c_{i}$ . Agora você tem que preparar uma prova com essas questões tal que a dificuldade total das questões seja pelo menos $l$ e no máximo $r$ e que a diferença entre a questão mais difícil e a mais fácil seja pelo menos $x$ . Calcule a quantidade de maneiras de preparar a prova.

Restrições:

$2 \leq n \leq 15$
$1 \leq l \leq r \leq 10^{9}$
$1 \leq x \leq 10^{6}$

Solução:

Podemos armazenar numa bitmask que guarda as questões que estamos usando, ou seja, se o bit $i$ está ligando então estamos usando a i-ésima questão na prova. Então vamos percorrer todas as bitmasks possíveis e checar se ela satisfaz os requisitos para a prova. Segue a implementação:

	#include <bits/stdc++.h>
	using namespace std;
	const int inf = 1e9 + 10;


	int n, l , r, x;
	int v[20];
	long long resp;

	int main()
	{
	ios::sync_with_stdio(false), cin.tie();

	cin >> n >> l >> r >> x;

	for(int i = 0; i < n; i++)
	cin >> v[i];

	for(int mask = 0; mask <= (1 << n) - 1; mask++)// percorro todas as bitmasks
	{
	long long s = 0;

	int maior = 0;

	int menor = inf;

	for(int i = 0; i < n; i++)// percorro todos os bits
	{
	if(mask & (1 << i)) //checo se a questão está na prova que estou olhando
	{
	s += v[i];
	maior = max(maior, v[i]); // calculo a maior dificuldade
	menor = min(menor, v[i]); // calculado a menor dificuldade
	}
	}

	if(s >= l and s <= r and (maior - menor) >= x) resp++; // se a prova é valida, adiciono um no contador

	}
	cout << resp << "\n";
	return 0;
	}

view raw

ideias02c2.cpp

hosted with ❤ by GitHub

Complexidade: $\mathcal{O}(2^{n} n)$ .

Exemplo 2

Temos $n$ cidades e $m$ estradas de mão dupla entre elas. Queremos saber o menor custo para visitar todas as cidades sem passar por uma cidade mais de uma vez, começando da cidade 0.

Restrições:

$1 \leq n \leq 15$ .
$n - 1 \leq m \leq \frac{n(n - 1)}{2}$ .
A distância entre duas cidades é menor que $10^{3}$ .
As cidades são enumeradas de $0$ à $n - 1$ .

Solução:

Utilizaremos uma ideia de programação dinâmica com auxílio de bitmask, $dp[2^{n}][n]$ , onde $dp[mask][i]$ representa o custo mínimo para visitar todas as cidades que estão marcadas na bitmask sendo que a última cidade visitada é a $i$ . Nesse caso, se a cidade $j$ está marcada, então o bit $j$ está ligado. Com isso, a recursão da programação dinâmica é:

$dp[mask][i]$ = $\begin{cases} 0 & , \mbox{se } mask = 2^{n} - 1 \\ \displaystyle \min\limits_{0 \leq v \leq n - 1} \big( dp[mask | 2^{v}][v] + C[i][v] \big) & , \mbox{caso contrario}\end{cases}$

Código para melhor entendimento:

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long ll;

	const int maxn = 16, maxm = (1 << 15) + 10;

	int n, m;
	int mat[maxn][maxn], dp[maxm][maxn];

	int solve(int mask, int i)
	{

	if(mask == (1 << n) - 1) return dp[mask][i] = 0; // caso todas as cidades já tenham sido visitadas

	if(dp[mask][i] != -1) return dp[mask][i]; // se a DP ja foi calculada

	int ans = 1e9;

	for(int v = 0; v < n; v++)
	{
	if(mask & (1 << v) or !mat[i][v]) continue; // se a cidade atual já foi visitada ou não há rota de i à v

	ans = min(ans, solve((mask \| (1 << v)), v) + mat[i][v]); //pego o minimo entre ir para cada vizinho

	}

	return dp[mask][i] = ans;
	}

	int main()
	{
	ios::sync_with_stdio(false), cin.tie(nullptr);

	cin >> n >> m;

	while(m--)
	{
	int a, b, w;
	cin >> a >> b >> w;
	mat[a][b] = mat[b][a] = w;
	}

	memset(dp, -1, sizeof(dp));

	cout << solve(1, 0) << "\n"; // começando da cidade 0


	}

view raw

ideias02c1.cpp

hosted with ❤ by GitHub

Complexidade: $\mathcal{O}(2^{n} n^{2})$ .

Exercícios para praticar:

Combate à Dengue	URI
Rota do Taxista	URI
Penalização	URI
Artskjid	DMOJ
Paths	KATTIS
Kronican	COCI 2016
Preparing Olympiad	Codeforces
Vitamins	Codeforces
Matching	DMOJ