PrevNext
Not Frequent
 0/13

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
CPHElevator Rides, SOS, Hamiltonian
PAPSexample - similar to Hamiltonian
CFHamiltonian walks
HE

Solution

Solution

Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
ACEasy
Show Tags

Bitmasks

Check AC
CFEasy
Show Tags

Bitmasks, MinCostFlow

Check CF
Old GoldEasy
Show Tags

Bitmasks

External Sol
Old GoldEasy
Show Tags

Bitmasks

External Sol
CSESNormal
Show Tags

Bitmasks

CPH 10.5
IZhONormal
Show Tags

Bitmasks

YSNormal
Show Tags

Bitmasks, Meet in Middle

View Solution
KattisNormal
Show Tags

Bitmasks, 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 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.

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 NameDifficultyTagsSolutionURL
CFHard
Show Tags

DP, Combinatorics

Check CF
CFVery Hard
Show Tags

DP, Bitmasks, NT

Check CF
CFInsane
Show Tags

Bitmasks, NT, Binary Search

Check CF
CFInsane
Show Tags

DP, Bitmasks, Combinatorics

Check CF

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.

PrevNext