DP -> Broken Profile / Plug DP

Frontier-mask DP on small-width grids, with occupancy masks first and connectivity-labeled plug states as the stronger follow-up.

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

Microtopics

• frontier-mask
• profile-dp
• column-sweep
• next-mask-generation
• domino-tiling
• plug-dp

Learning Sources

Source	Type
cp-algorithms broken profile	Reference
USACO Guide broken profile	Reference
OI Wiki plug DP	Reference

Practice Sources

Source	Type
CSES Counting Tilings	Practice

Repo Companion Material

Material	Type
Broken Profile hot sheet	quick reference
Template Library exact starter route	starter route
Counting Tilings note	anchor note
Bitmask DP	compare point
DP cheatsheet	compare point

Curated External Problems

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Counting Tilings	CSES	Hard	Grid DP	Counting; Frontier DP	Bitmask Basics; Local Placements	Domino Tiling; Frontier Mask; Column Sweep	The cleanest first verifier for occupancy-mask profile DP on a small-width grid.

Challenge

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Compound Escape	USACO Platinum	Very Hard	Plug-DP	Counting; Frontier DP	Occupancy Masks; Grid Frontier Thinking	Frontier State; Counting; Challenge	A challenge-level extension once simple occupancy masks are no longer the only frontier information you can reason about.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
COUNTINGTILINGS	Counting Tilings	primary	hard	-	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py