# 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 – read through this problem before continuing!

### Tutorial

Resources | ||||
---|---|---|---|---|

CPH | Elevator Rides, SOS, Hamiltonian | |||

NW | ||||

PAPS | example - similar to Hamiltonian | |||

CF | Hamiltonian walks | |||

DPCC | Diagram | |||

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 $\{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$.

### 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!