# 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 $\{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!