Rare
0/18

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.

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

### Problems

StatusSourceProblem NameDifficultyTags
ACEasy
CFEasy
Old GoldEasy
GoldEasy
Old GoldEasy
CSESNormal
IZhONormal
YSNormal
Show TagsBitmasks, DP, Meet in Middle
KattisNormal
Show TagsBinary Search, Bitmasks, DP, Geometry
IZhOHard
COCIHard
Show TagsBitmasks, DP, Game Theory, Sqrt
CEOIVery Hard
IOIVery Hard

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

Any help would be appreciated! Just submit a Pull Request on Github.

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

StatusSourceProblem NameDifficultyTags
CFHard
Show TagsCombinatorics, DP
CFVery Hard