Bitmask DP
Authors: Michael Cao, Siyong Huang, 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 – read through this problem before continuing!
Tutorial
Resources | |||
---|---|---|---|
CPH | Elevator Rides, SOS, Hamiltonian | ||
NW | |||
PAPS | example - similar to Hamiltonian | ||
CF | Hamiltonian walks | ||
HE |
Solution
Solution
Problems
Status | Source | Problem Name | Difficulty | Tags | |||||
---|---|---|---|---|---|---|---|---|---|
AC | Easy | Show TagsBitmasks, DP | |||||||
CF | Easy | Show TagsBitmasks, MinCostFlow | |||||||
Old Gold | Easy | Show TagsBitmasks, DP | |||||||
Gold | Easy | Show TagsBitmasks, DP | |||||||
Old Gold | Easy | Show TagsBitmasks, DP | |||||||
CSES | Normal | Show TagsBitmasks, DP | |||||||
IZhO | Normal | Show TagsBitmasks, DP | |||||||
YS | Normal | Show TagsBitmasks, DP, Meet in Middle | |||||||
Kattis | Normal | Show TagsBinary Search, Bitmasks, DP, Geometry | |||||||
IZhO | Hard | Show TagsBitmasks, DP | |||||||
COCI | Hard | Show TagsBitmasks, DP, Game Theory, Sqrt | |||||||
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 were represented by 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 .
This section is not complete.
Maybe this is just standard NT, but I've always thought about it as a bitmask. Also, any tutorials or more problems of this type?
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!