DP -> SOS DP

Subset/superset zeta sweeps on the full boolean cube, including witness propagation after complement-mask modeling.

• Topic slug: dp/sos-dp
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 1
• Repo companion pages: 5
• Curated external problems: 2

Microtopics

• subset-zeta
• superset-zeta
• mask-cube-sweep
• subset-aggregates
• complement-masks
• witness-propagation

Learning Sources

Source	Type
USACO Guide Sum over Subsets DP	Reference
OI Wiki prefix sum and SOS subsection	Reference

Practice Sources

Source	Type
Codeforces Compatible Numbers	Practice
CSES SOS Bit Problem	Practice

Repo Companion Material

Material	Type
SOS DP hot sheet	quick reference
Template Library exact starter route	starter route
Compatible Numbers	flagship note
Bitmask DP	compare point
DP cheatsheet	quick reference

Curated External Problems

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Compatible Numbers	Codeforces	Very Hard	Bitmask	Full-Cube Sweep; Complement Modeling; Offline Propagation	Bitmask States; Complement Masks; Subset Direction	Bitmasks; Subset Zeta; Witness Propagation; Bitwise Complement	The cleanest first rep where one subset-direction SOS sweep carries a witness value and the real modeling step is querying the complement mask.

Stretch

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
SOS Bit Problem	CSES	Hard	Bitmask	Full-Cube Sweep; Count Aggregation; Complement Counting	Sos DP; Bitwise Predicates; Mask Bucketing	Subset Zeta; Superset Zeta; Bitwise Or; Bitwise And	A strong follow-up where the same lane has to support both subset-side and superset-side counting in one problem.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
COMPATIBLENUMBERS	Compatible Numbers	primary	2200	-	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py