# Dynamic Programming on Bitmasks

Authors: Michael Cao, Siyong Huang, Andrew 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 | ||

PAPS | example - similar to Hamiltonian | ||

CF | Hamiltonian walks | ||

HE |

## Solution

Solution

## Problems

Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|

AC | Easy | ## Show TagsBitmasks | Check AC | |||

CF | Easy | ## Show TagsBitmasks, MinCostFlow | Check CF | |||

Old Gold | Easy | ## Show TagsBitmasks | External Sol | |||

Old Gold | Easy | ## Show TagsBitmasks | External Sol | |||

CSES | Normal | ## Show TagsBitmasks | CPH 10.5 | |||

IZhO | Normal | ## Show TagsBitmasks | ||||

YS | Normal | ## Show TagsBitmasks, Meet in Middle | View Solution | |||

Kattis | Normal | ## Show TagsBitmasks, Geometry, Binary Search | View Solution |

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

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

## Give Us Feedback on Dynamic Programming on Bitmasks!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.