Bitmask DP

Bitmask DP

Tutorial

Solution

Let $dp[S][i]$ be the number of routes that visit all the cities in the subset $S$ and end at city $i$. The transitions will then be:

where $S \setminus \{i\}$ is the subset $S$ without city $i$.

Time Complexity: $\mathcal{O}(2^N \cdot N^2)$

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAX_N = 20;
const ll MOD = (ll)1e9 + 7;

ll dp[1 << MAX_N][MAX_N];
// come_from[i] contains the cities that can fly to i

Copy
import sys

MOD = 10**9 + 7

input = sys.stdin.readline

n, m = map(int, input().strip().split())
dp = [[0 for _ in range(n)] for _ in range(1 << n)]
dp[1][0] = 1

Merging Subsets

In some problems, for a set $S$, it is not sufficient to transition from $S \setminus \{i\}$. Instead, it is necessary to transition from all strict subsets of $S$.

Though it may seem like we have to do $\mathcal{O}(2^N \cdot 2^N) = \mathcal{O}(4^N)$ transitions, there's really only $\mathcal{O}(3^N)$ transitions!

To see why, let's count the number of ordered pairs $(T, S)$ where $T \subset S$. Instead of counting directly, notice that each element $x$ is either:

1. In $T$ and $S$
2. In neither
3. In $S$ but not in $T$.

If $x$ is in $T$ but not in $S$, $T$ isn't a valid subset.

Given that each element can be in three possible states, our overall complexity is actually $\mathcal{O}(3^N)$.

To implement this, we can do some bitwise tricks:

Copy
for (int mask = 0; mask < (1 << n); mask++) {
	for (int submask = mask; submask != 0; submask = (submask - 1) & mask) {
		int subset = mask ^ submask;
		// do whatever you need to do here
	}
}

When we subtract $1$ from $\texttt{submask}$, the rightmost bit flips to a $0$ and all bits to the right of it will become $1$. Applying the bitwise AND with $\texttt{mask}$ removes all extra bits not in $\texttt{mask}$. From this process, we can get all strict subsets in increasing order by calculating $\texttt{mask} \oplus \texttt{submask}$, which does set subtraction.

Explanation

The goal of this problem is to partition the nodes into sets such that the nodes in each set form a complete graph. Let $\texttt{dp}[S]$ be the minimum number of partitions such that in each partition, the graph formed is a complete graph.

We can first find which sets $T$ form a complete graph, setting $\texttt{dp}[T]$ to $1$ and $\infty$ otherwise. This can be done naively in $\mathcal{O}(2^N \cdot N^2)$ or $\mathcal{O}(2^N \cdot N)$ by setting the adjacency list as a bitmask and using bit manipulations if a set of nodes is a complete graph.

Then we can transition as follows:

Implementation

Time Complexity: $\mathcal{O}(3^N + 2^N \cdot N)$

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> adj(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;

Problems

Application - Bitmask over Primes

Rough Idea

In some number theory problems, it helps to represent each number with a bitmask of its prime divisors. For example, the set $\{6, 10, 15 \}$ can be represented by $\{0b011, 0b101, 0b110 \}$ (in binary)*, where the bits correspond to divisibility by $[2, 3, 5]$.

Then, here are some equivalent operations between masks and these integers:

• Bitwise AND is GCD
• Bitwise OR is LCM
• Iterating over bits is iterating over prime divisors
• Iterating over submasks is iterating over divisors

Choosing a set with GCD $1$ is equivalent to choosing a set of bitmasks that AND to $0$. For example, we can see that $\{6, 10 \}$ doesn't have GCD $1$ because $0b011 \& 0b101 = 0b001 \neq 0$. On the other hand, $\{6, 10, 15 \}$ has GCD $1$ because $0b011 \& 0b101 \& 0b110 = 0b000 = 0$.

Problems