Not Frequent
 0/20

Bitmask DP

Authors: Michael Cao, Siyong Huang

Contributors: Andrew Wang, Neo Wang

DP problems that require iterating over subsets.

Pro Tip

You can often use this to solve subtasks.

Bitmask DP

Focus Problem – try your best to solve this problem before continuing!

Tutorial

Resources
CPH

Elevator Rides, SOS, Hamiltonian

nwatx
PAPS

example - similar to Hamiltonian

CF

Hamiltonian walks

DPCC

Diagram

HE

Solution

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

dp[S][i]=xadj[i]dp[S{i}][x] if xSdp[S][i] = \sum_{x \in adj[i]} dp[S \setminus \{i\}][x] \text{ if $x \in S$}

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

C++

#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

Problems

StatusSourceProblem NameDifficultyTags
ACEasy
Show TagsBitmasks, DP
CFEasy
Show TagsBitmasks, MinCostFlow
Old GoldEasy
Show TagsBitmasks, DP
Old GoldEasy
Show TagsBitmasks, DP
GoldNormal
Show TagsBitmasks, DP
CSESNormal
Show TagsBitmasks, DP
IZhONormal
Show TagsBitmasks, DP
KattisNormal
Show TagsBinary Search, Bitmasks, DP, Geometry
YSHard
Show TagsBitmasks, DP, Meet in Middle
GoldHard
Show TagsBitwise, DP
IZhOHard
Show TagsBitmasks, DP
COCIHard
Show TagsBitmasks, DP, Game Theory, Tree
GoldHard
Show TagsBitmasks, DP
CEOIVery Hard
Show TagsBitmasks, DP
IOIVery Hard
Show TagsBitmasks, DFS, DP, Tree

Application - Bitmask over Primes

Rough Idea

In some number theory problems, it helps to represent each number were represented by a bitmask of its prime divisors. For example, the set {6,10,15}\{6, 10, 15 \} can be represented by {0b011,0b101,0b110}\{0b011, 0b101, 0b110 \} (in binary), where the bits correspond to divisibility by [2,3,5][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 11 is equivalent to choosing a set of bitmasks that AND to 00. For example, we can see that {6,10}\{6, 10 \} doesn't have GCD 11 because 0b011&0b101=0b00100b011 \& 0b101 = 0b001 \neq 0. On the other hand, {6,10,15}\{6, 10, 15 \} has GCD 11 because 0b011&0b101&0b110=0b000=00b011 \& 0b101 \& 0b110 = 0b000 = 0.

Problems

StatusSourceProblem NameDifficultyTags
CFHard
Show TagsCombinatorics, DP
CFVery Hard
Show TagsBitmasks, DP, NT
CFInsane
Show TagsBinary Search, Bitmasks, NT
CFInsane
Show TagsBitmasks, Combinatorics, DP

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!