Dynamic Programming on Bitmasks
Authors: Michael Cao, Siyong Huang, Andrew Wang
DP problems that require iterating over subsets.
Focus Problem – read through this problem before continuing!
Bitmasks, Meet in Middle
Bitmasks, Geometry, Binary Search
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.
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.