Bit-Parallelism / Bitset Optimization Ladder

This lane is for when one boolean DP row is still the right model, but scalar state updates are no longer the right implementation.

It stays intentionally narrow:

• exact starter = dynamic bitset shift-OR reachability
• flagship rep = one problem where modeling reduces to component sizes, then bitset subset sum does the rest
• string-bitset and other packed-state tricks stay as later compare points

Who This Is For

Use this lane if:

• Knapsack Family already feels familiar
• you can recognize a boolean reachability DP quickly
• the main bottleneck is the width of one boolean row, not the recurrence shape itself

Warm-Up

• ordinary subset-sum reachability
• why reachable |= reachable << w matches the boolean 0/1 transition
• why this is not the same family as FWHT / XOR Convolution / Subset Convolution

Warm-up compare points:

• Knapsack Family
• FWHT / XOR Convolution / Subset Convolution

Core

• packed shift-OR reachability
• tail trimming
• exact flagship rep: School Excursion

Target skill:

• see one feasibility DP on a large sum axis and know when word packing is the real win

Stretch

• CSES - Money Sums
• string bitset speedups
• other boolean-state packed DP rows

Target skill:

• know when the bitset route is just a cleaner implementation of the same DP, and when it is the only practical implementation

Retrieval Layer

• exact quick sheet -> Bit-Parallelism / Bitset Optimization hot sheet
• exact starter -> bitset-reachability-shift.cpp
• parent chooser -> DP cheatsheet
• compare point -> Knapsack Family

External Practice

• CSES - School Excursion
• CSES - Money Sums

Tutorial Link

• Bit-Parallelism / Bitset Optimization