Skip to content

Broken Profile / Plug DP Ladder

This lane is for the first time a mask stops meaning "chosen subset" and starts meaning "current grid frontier."

It is intentionally a narrow lane:

  • one exact occupancy-mask starter
  • one flagship domino-tiling rep
  • a clear warning that full plug DP is a stronger follow-up, not the first snippet

Who This Is For

Use this lane if:

  • Bitmask DP already feels comfortable
  • one small grid dimension is visible in the constraints
  • the real state is a frontier between processed and unprocessed cells

Warm-Up

  • rotate the grid so the smaller dimension is the masked one
  • define exactly what a 1 bit means in the current frontier
  • generate one legal next_mask by scanning rows inside a column

Target skill:

  • tell the difference between subset masks and frontier masks

Core

  • occupancy-mask broken profile
  • row DFS that generates next_mask
  • exact flagship rep: Counting Tilings

Target skill:

  • compute one column transition without mixing current-column and next-column meaning

Stretch

Target skill:

  • know that full plug DP is the next escalation after occupancy-mask frontier DP, not the same thing

Retrieval Layer

Exit Criteria

You are ready to move on when:

  • you can explain the frontier mask without talking vaguely about "processed stuff"
  • you can generate next_mask by local placements only
  • you know when occupancy masks stop being enough and full plug labels are needed

External Practice