A Primer on Bitmask DP

Neo Wang / March 20, 2021

– views

Introduction

Before we begin, read this problem and come up with possible strategies to tackle it. Note that nn is surprisingly low. Upon more careful consideration of your solution, you should realize that this problem is incredibly difficult to tackle in anything better than O(nm2n)\mathcal{O}(nm2^n) time complexity. In this blog post, we will discuss the dynamic programming technique that enables us to solve this problem.

Motivations

Sometimes, problems require using subsets as the "optimal subtask." As CPH notes,

it is often possible to change an iteration over permutations into an iteration over subsets.

Therefore, iterating over the 2n2^n number subsets is much faster than iterating through the n!n! number of permutations. CPH further notes that for an input of size n=20n=20, then n!2.41018n! \approx 2.4\cdot 10^{18} which greatly exceeds 2201062^{20}\approx 10^6. The technique we will discuss iterates through such subsets.

Key Ideas

Our first key idea lies in the representation of numbers through the usage of bits. Here, rather than representing our numbers as integer values, we represent a number xx as the xx-th bit from the right. Notice that this causes the time complexity to grow exponentially, as for every number xx causes an increase by an additional power of 22.

Example: Store the subset {1,3,4,8}\{1, 3, 4, 8\}

This corresponds to ...100011010...100011010 which corresponds to 28+24+23+21=2822^8+2^4+2^3+2^1=282.

Basic Set Operations

Using this new representation, we can perform the following set operations using bitwise operators.

  • Intersection - including two bits if they exist in both sets: a&ba\&b.
  • Union - including bits if they exist in either set: aba|b.
  • Symmetric difference - including bits if they are present in either set but not both: aa ^ bb.

If we want to iterate through the 2n2^n subsets of {0,1,,n1}\{0, 1,\ldots,n-1\}, we can simply loop from 0,1,,n10,1,\ldots ,n-1 of our current bit representation of the set. In code this looks like

for(int i = 0; i < (1<<n); i++) {
    // process each subset
}

Another key bit operation we must know for the following problems comes in the form of (1n)1(1\ll n)-1 which creates a bitset with exactly nn ones. Ex. 251=31=01111122^5-1=31=011111_2

Feel free to refer back to this section when reading about the below problems.

Tackling CPH - Optimal Selection

Read through this chapter in order to get a general understanding of the problem presented. Since this blog post serves as an elaboration on the material covered, you should read that before continuing.

Below is the code used to solve the problem. We will perform a line-by-line analysis of what it does. It is a good idea to go back and forth between the explanation and the code itself.

for(int d = 1; d < n; d++) loops from the first day to the nn-th day. This should be straightforward.

for(int s = 0; s < (1<<k); s++) loops through each of the 2k2^k subsets of {0,1,,k1}\{0, 1,\ldots,k-1\}. Reference our code above if you are confused.

total[s][d] = total[s][d-1]; the total best price on day dd is the best total on day d1d-1. This makes sense because the worst case is that no improvement is made on the previous day.

for(int x = 0; x < k; x++) loops through each of the xx items.

if(s&(1<<x)) recall that the and operator only includes bits if they exist in both sets. Thus s&(1<<x) is equivalent to saying if element xSx \in S.

The next line is rather complicated, so we will break it into several pieces.

total[s^(1<<x)][d-1] is the best total for any subset without xx. d1d-1 just means on any day before.

price[x][d] is the price of item xx on day dd.

total[s][d] = min(total[s][d], total[s^(1<<x)][d-1]+price[x][d]); Either we take the previous best value, or we buy item xx on day dd for a total value of the best value on the previous day that doesn't contain item xx total[s^(1<<x)][d+1] plus the price of the item today price[x][d].

Putting this altogether, the below dynamic programming approach should make sense.

Time Complexity: O(nk2k)\mathcal{O}(nk2^k)

for(int d = 1; d < n; d++) {
    for(int s = 0; s < (1<<k); s++) {
        total[s][d] = total[s][d-1];
        for(int x = 0; x < k; x++) {
            if(s&(1<<x)) {
                total[s][d] = min(total[s][d], total[s^(1<<x)][d-1]+price[x][d]);
            }
        }
    }
}

Tackling Hamiltonian Flights

The first thing we want to do is to come up with a dynamic programming recurrence. Since a huge hint has already been given through the bitmask dynamic programming paradigm, you might want to think about a way to convert this problem into "dynamic programming on subsets."

The solution lies in representing dp[S][i]\texttt{dp}[S][i] as the number of routes that visit all the cities in subset SS and end at city ii. This can be formulated as:

dp[S][i]=xadj[i]dp[S\{i}][x]ifxS\texttt{dp}[S][i]=\sum_{x\in \text{adj}[i]}\texttt{dp}[S\backslash \{i\}][x]\: \text{if}\: x \in S

We can check whether or not the kk-th bit is set by using S&(1(k1))S \& (1 \ll (k-1)). Another equivalent operation is (S(k1))&1(S \gg (k-1))\& 1. You can read more about how this works here.

Below is our solution to Hamiltonian Flights. Just as before, we will perform a line-by-line analysis on how the code works.

The first thing you might notice is that we are pushing in our directed flights backwards through adj[b].pb(a). This is because in our dynamic programming approach, we choose to build the sets based of previously established "optimal solutions."

dp[1][1] = 1. There is only one way for the first city to fly to itself.

for(int s = 2; s < (1<<n); s++) starts from the second city (represented as ...102=2...10_2=2), and iterates through all the subsets as before.

s & (1 << (n-1)) checks if the n1n-1-th bit is set.

s != ((1 << n) - 1) checks that the current set is not equal to 01111011\ldots 11 where 00 is the nn-th bit from the right.

If both of the above conditions are true, then we continue looping. This equates to setting to mask to "ignore all instances of subsets that don't include the n1n-1-th city and are is not the subset that contains all cities."

for(int v : adj[d]) traverses the adjacency list of city dd.

Then, for each vertex, we check if vv is in the mask with s&(1(v1))s \& (1\ll (v-1)).

If vv is in the mask, then we can add the total amount of flights to the subset SS.

We can finally query the flights that travel through the cities {1,2,,n}\{1,2,\ldots,n\} with dp[(1n)1][n]\texttt{dp}[(1\ll n)-1][n]. This works because (1n)1(1\ll n)-1 contains exactly nn toggled bits (ex. 251=01111122^5-1=011111_2).

Time Complexity: O(nm2n)\mathcal{O}(nm2^n)

hflights.cpp
#include <bits/stdc++.h> // see /general/running-code-locally
using namespace std;

using ll = long long;
using vi = vector<int>;
#define pb push_back

void setIO() {
    cin.tie(0)->sync_with_stdio(0); // see /general/fast-io
}

const int mod = 1e9+7;

vi adj[21];
ll dp[1<<20][21]; // amount of flights of subset S ending at city d

int main() {
    setIO();

    int n, m; cin >> n >> m;

    for(int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        adj[b].pb(a);
    }

    dp[1][1] = 1; // there is one way to fly from 1 to itself

    for(int s = 2; s < (1<<n); s++) { // we start from the second city
        if((s & (1 << (n-1))) && s != ((1<<n) - 1)) continue;
        for(int d = 1; d <= n; d++) { // loop through each city
            if((s & (1 << (d-1))) == 0) continue;
            for(int v : adj[d]) {
                if(s & (1<<(v-1))) { // if v is in the mask
                    dp[s][d] += dp[s-(1<<(d-1))][v];
                    dp[s][d] %= mod;
                }
            }
        }
    }

    cout << dp[(1<<n)-1][n] % mod;
}
🌓