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 be the number of routes that visit all the cities in the subset and end at city . The transitions will then be:
where is the subset without city .
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
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
AC | Easy | Show TagsBitmasks, DP | |||
CF | Easy | Show TagsBitmasks, MinCostFlow | |||
Old Gold | Easy | Show TagsBitmasks, DP | |||
Old Gold | Easy | Show TagsBitmasks, DP | |||
Gold | Normal | Show TagsBitmasks, DP | |||
CSES | Normal | Show TagsBitmasks, DP | |||
IZhO | Normal | Show TagsBitmasks, DP | |||
Kattis | Normal | Show TagsBinary Search, Bitmasks, DP, Geometry | |||
YS | Hard | Show TagsBitmasks, DP, Meet in Middle | |||
Gold | Hard | Show TagsBitwise, DP | |||
IZhO | Hard | Show TagsBitmasks, DP | |||
COCI | Hard | Show TagsBitmasks, DP, Game Theory, Tree | |||
Gold | Hard | Show TagsBitmasks, DP | |||
CEOI | Very Hard | Show TagsBitmasks, DP | |||
IOI | Very Hard | Show TagsBitmasks, DFS, DP, Tree |
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 can be represented by (in binary), where the bits correspond to divisibility by .
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 is equivalent to choosing a set of bitmasks that AND to . For example, we can see that doesn't have GCD because . On the other hand, has GCD because .
Problems
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
CF | Hard | Show TagsCombinatorics, DP | |||
CF | Very Hard | Show TagsBitmasks, DP, NT | |||
CF | Insane | Show TagsBinary Search, Bitmasks, NT | |||
CF | Insane | 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!