⚙️AlgorithmAdvanced

DP on Broken Profile - Plug DP

Key Points

  • •
    Plug DP (DP on broken profile with plugs) sweeps a grid cell by cell while remembering how partial path segments cross the frontier as labeled “plugs.”
  • •
    States encode which frontier positions have pending path endpoints and which of those endpoints belong to the same partial component.
  • •
    Transitions at each cell locally decide which two (or one at S/T) incident edges exist, then merge, continue, or create plugs while preventing premature cycles.
  • •
    Canonical relabeling of component IDs after every transition keeps state-space small and avoids equivalent duplicates.
  • •
    For Hamiltonian paths, all non-endpoint cells must have degree 2, and endpoints (S and T) must have degree 1; obstacles force degree 0.
  • •
    The number of states per frontier is roughly Catalan in the number of columns when using non-crossing encodings, giving O(m n ) behavior.
  • •
    Efficiency relies on pruning: forbid early cycle closures (unless the final cell) and normalize labels to keep hashes compact.
  • •
    Typical practical limits are widths up to 10–12 with good optimizations; careful hashing and canonicalization are critical.

Prerequisites

  • →Grid graphs and Manhattan adjacency — Hamiltonian constraints and local degree choices are defined on the 4-neighbor grid graph.
  • →Dynamic programming on profiles (bitmask DP) — Plug DP extends broken-profile DP by adding connectivity (label) information to the frontier.
  • →Hash maps and state compression — Efficiently storing and deduplicating frontier states requires compact packing and hashing.
  • →Union-find / label merging intuition — When two plugs meet, their components must be merged by replacing labels across the profile.
  • →Catalan numbers and non-crossing matchings — Understanding bracket encodings and the approximate state count hinges on Catalan structures.
  • →Graph degrees and paths/cycles — Local transitions enforce per-vertex degrees that define Hamiltonian paths/cycles.
  • →Canonicalization (state normalization) — Avoids exponential blow-up by identifying equivalent states differing only by label names.
  • →Amortized complexity and pruning — Practical performance depends on per-transition costs and aggressive invalid-state pruning.

Detailed Explanation

Tap terms for definitions

01Overview

Imagine pushing a broom across a floor grid from top-left to bottom-right. At the broom’s bristles (the “frontier”), you keep track of loose ends of partial paths that will be connected later. Plug DP formalizes this idea: we sweep the grid and carry a compact encoding of how path segments currently cross the sweep-line. The encoding lists, for each frontier position, whether a path-end (a “plug”) is present and which plugs are paired in the same partial component. As we move cell by cell, we make local decisions (which edges around the current cell are part of the final path), and we update, merge, create, or remove plugs accordingly.

This technique generalizes classic broken-profile DP (like domino tilings) by not only tracking occupancy but also the connectivity between frontier points. That connectivity is what enables solving Hamiltonian path/cycle problems on grids with obstacles: every non-endpoint cell must have degree 2; endpoints have degree 1. When two plugs are connected inside a cell, their components merge; if they belong to the same component, we are about to close a cycle, which we only allow at the very end for a Hamiltonian cycle or carefully for a Hamiltonian path.

The power of Plug DP comes with complexity: the state space can grow large, but with non-crossing encodings (parenthesis/bracket states) or canonical label compression, it remains manageable for widths up to about a dozen. Proper hashing, normalization, and pruning are essential to reach competitive runtimes (common on high-rated CF tasks).

02Intuition & Analogies

Think of each frontier position as a socket on a power strip that can have a dangling wire (a plug). Each plug belongs to some cable (component). As you move across the grid, each cell either: (a) connects two adjacent wires together (like joining two wire ends), (b) extends a wire to the right or downward (pass-through), (c) starts a new pair of wires (for cycles), or (d) closes off an end at a special cell (endpoint for a Hamiltonian path). The frontier is the current face of the construction: the only places where the unfinished wires stick out.

When two plugs that are part of different cables get connected, the cables merge into a bigger one (merge plug labels). If two plugs from the same cable get connected, you would form a loop (cycle) then and there. For Hamiltonian path problems, we want exactly one connected path that uses every allowed cell. So we forbid closing a loop early—if you create a cycle before covering all cells, there’s no way to stitch remaining cells into the already-closed loop. Only at the very last step can a closure be allowed (for Hamiltonian cycles) or, for a Hamiltonian path, we ensure only two endpoints (S and T) exist overall and the final frontier is empty.

To keep memory sane, we continuously rename (normalize) component IDs in the frontier to a canonical small set like {1,2,3,...} based on left-to-right first appearance. Two frontier configurations that differ only by relabeling are treated as the same DP state. This is like bundling identical wiring diagrams by redrawing labels neatly, so the DP doesn’t revisit the same situation under different accidental names.

03Formal Definition

Let the grid have m rows and n columns. We sweep cells in row-major order. At each step, the DP frontier is the cut between processed and unprocessed cells. A Plug DP state consists of: (1) a profile vector P of length n, where P[j] is either 0 (no plug at column j) or a positive integer label indicating the component ID of a pending plug going downward through the frontier at column j; and (2) an auxiliary left plug L (0 or a label) for the pending horizontal plug to the right of the previously processed cell in the current row. Two states are equivalent if there exists a relabeling (permutation) of positive labels such that their (P, L) match; we store canonical representatives via normalization. At each cell (i, j), with incoming plugs (from above) and L (from the left), we choose a subset of incident edges among {up, left, right, down} consistent with problem constraints. For Hamiltonian path: every free cell c ≠ {S, T} must have degree 2; S and T must have degree 1; blocked cells have degree 0. The transition updates produce new P' and L' and possibly merge labels: if two nonzero labels meet inside the cell, we replace all occurrences of the larger with the smaller (union). If a merge would close a cycle (both labels equal), we allow it only under end-conditions (e.g., last cell and no remaining plugs). The DP value at (i, j, state) aggregates counts (or booleans) over all valid predecessors. With non-crossing-structure encodings (e.g., bracket states), the number of distinct normalized states per frontier is O(), where is the n-th Catalan number; otherwise, with generic labels, it’s typically larger but still tractable for with pruning.

04When to Use

Use Plug DP when you must enforce global connectivity/degree constraints on grid graphs while sweeping locally: Hamiltonian paths/cycles, single-cycle coverings, counting cycle covers under obstacles, or problems where partial connections must be remembered across the sweep. Typical competitive-programming tasks include:

  • Hamiltonian path between S and T through all free cells (degree-1 at endpoints, degree-2 elsewhere).
  • Hamiltonian cycle in a rectangular grid with holes (every used cell degree-2, one final cycle).
  • Single-loop puzzles (e.g., Slitherlink-like constraints), where exactly one simple cycle must be formed using allowed edges.
  • Advanced tilings or matching variants where pairing information across the frontier matters (beyond mere occupancy).

If connectivity does not matter (e.g., plain domino tilings without connectivity constraints), standard broken-profile (bitmask DP) is usually simpler and faster. Switch to Plug DP when naive profile DP cannot encode “which end connects to which end” and you must avoid creating multiple components or premature cycles.

⚠️Common Mistakes

  • Forgetting canonicalization: If you carry raw component labels, equivalent states proliferate, causing exponential blow-ups. Always renumber labels after each transition in first-appearance order.
  • Allowing early cycles: If you connect two plugs of the same component before the sweep ends, you close a loop and block unprocessed cells. Only allow such closure at the final step (for cycles) or not at all (for paths unless it’s the intended final connection).
  • Boundary mistakes: Emitting a right plug in the last column or a down plug in the last row produces impossible edges; transitions must respect borders and obstacles.
  • Degree miscounts at S/T: For Hamiltonian paths, only S and T may have degree 1; all other free cells must have degree 2. Accidentally permitting degree 0 or 2 at S/T (or degree 1 elsewhere) invalidates the path.
  • Not merging labels globally: When two different components get joined, you must replace every occurrence of one label across the entire frontier (and the left plug), not just locally at the current column.
  • Overcounting due to symmetric closures: If counting cycles, ensure the acceptance condition is “frontier empty and exactly one cycle formed” and that you do not count the same cycle multiple times due to different closure orders.
  • Hash-map churn: Reusing buffers, reserving buckets, and avoiding large temporary allocations per transition dramatically improves performance.

Key Formulas

Catalan number

Explanation: Catalan numbers count non-crossing pairings (well-formed parentheses). When frontier structures are non-crossing, the number of canonical states is on the order of , which bounds DP state growth with width n.

Runtime via frontier states

Explanation: We process m×n cells, and each cell updates across about S(n) states (number of canonical states for width n). For bracket encodings, S(n) is roughly Catalan; with generic labeled plugs, it can be larger but still manageable for small n.

Asymptotics of non-crossing states

Explanation: The number of non-crossing frontier states grows like Catalan numbers, asymptotically about 4^n/(√ This guides feasibility for widths up to ~12.

Frontier memory

Explanation: At each step we only keep the current frontier layer (hash map from state to value), so memory scales with the number of canonical states.

Central binomial coefficient

Explanation: Useful upper bound for counting frontier patterns when bracket constraints are relaxed. It bounds S(n) from above in some plug DP variants.

Label normalization cost

Explanation: Naively merging labels can cost O(n) per transition; across n columns, total per cell can be proportional to n. Optimizations can reduce constant factors.

Typical labeled-plug complexity

Explanation: A common rough bound when using labeled plugs with hash maps and per-transition normalization. With pruning and bracket encodings, practical performance is often better.

Complexity Analysis

Let n be the number of columns (frontier length) and m the number of rows. Plug DP processes m×n cells; each step iterates over a set of canonical states S(n). With bracket/non-crossing encodings, S(n) is roughly the n-th Catalan number , giving time O(m × n × ) and space O(). With generic labeled plugs (component IDs) and hash maps, a safe working bound often cited is O(2^n × × m): 2^n accounts for which slots are occupied, for potential label merges/normalizations per transition, and m for the number of layers. Each transition may perform operations proportional to frontier width: (a) test and update up to O(1) entries (left and current column), (b) possibly merge two labels by scanning the n-slot frontier (O(n)), and (c) normalize labels to their first-appearance order (another O(n)). Thus, the per-transition overhead is O(n). Since the number of transitions from a state per cell is bounded by a small constant (valid local degree patterns), total time per state per cell is O(n), yielding O(m × S(n) × n). Space usage is dominated by storing the current frontier hash map of size with packed keys (e.g., 4 bits per slot) and small payloads (boolean or 64-bit counts). Practical limits are around with careful pruning (for Hamiltonian-type constraints). Using bracket encodings and forbidding early closures substantially shrinks S(n). Engineering improvements—compact key packing, custom open-addressing hash tables, and memory reuse—often change constant factors enough to solve 2300–2700-rated tasks within time limits.

Code Examples

Broken-profile DP (bitmask) for counting domino tilings with obstacles
1#include <bits/stdc++.h>
2using namespace std;
3
4// Count the number of domino tilings (2x1 or 1x2) of an m x n grid with obstacles '#'.
5// Classic broken-profile DP over rows; shown here as a warm-up to Plug DP.
6// Complexity: O(m * n * 2^n) transitions in practice; space O(2^n).
7
8int m, n; // rows, cols
9vector<string> G;
10
11// Recursively fill row r using bitmask 'mask' for current row occupancy;
12// 'nextMask' accumulates vertical dominos that occupy the next row.
13long long dfs_row(int c, int curMask, int nextMask, int r) {
14    if (c == n) {
15        // move to next row with nextMask as the starting occupation
16        return (curMask == 0) ? (long long)nextMask : 0LL; // trick: return nextMask to carry to caller
17    }
18    // If current cell is already occupied (by horizontal from left or vertical from above)
19    if (curMask & (1 << c)) {
20        return dfs_row(c + 1, curMask & ~(1 << c), nextMask, r);
21    }
22    // If obstacle, must remain empty
23    if (G[r][c] == '#') {
24        return dfs_row(c + 1, curMask, nextMask, r);
25    }
26    long long ways = 0;
27    // Try place horizontal domino to the right
28    if (c + 1 < n && !(curMask & (1 << (c + 1))) && G[r][c + 1] != '#') {
29        ways += dfs_row(c + 1, curMask | (1 << (c + 1)), nextMask, r);
30    }
31    // Try place vertical domino downward: occupies (r+1, c) in next row
32    if (r + 1 < m && G[r + 1][c] != '#') {
33        ways += dfs_row(c + 1, curMask, nextMask | (1 << c), r);
34    }
35    // If we cannot place anything, leave cell empty (invalid for full tiling), but keep DP consistent
36    return ways;
37}
38
39int main() {
40    ios::sync_with_stdio(false);
41    cin.tie(nullptr);
42
43    cin >> m >> n;
44    G.resize(m);
45    for (int i = 0; i < m; ++i) cin >> G[i];
46
47    // DP over rows: dp[mask] = number of ways to reach row r with this mask of pending vertical dominos
48    vector<long long> dp(1 << n, 0), ndp(1 << n, 0);
49    dp[0] = 1;
50
51    for (int r = 0; r < m; ++r) {
52        fill(ndp.begin(), ndp.end(), 0);
53        for (int mask = 0; mask < (1 << n); ++mask) if (dp[mask]) {
54            // Expand this row from left to right
55            // We run dfs_row, but we need to accumulate counts into ndp[nextMask]
56            // We'll implement dfs as a stack lambda capturing dp[mask]
57            struct Frame { int c, curMask, nextMask; long long mul; };
58            vector<Frame> st; st.push_back({0, mask, 0, dp[mask]});
59            while (!st.empty()) {
60                auto [c, curMask, nextMask, mul] = st.back(); st.pop_back();
61                if (c == n) {
62                    if (curMask == 0) ndp[nextMask] += mul;
63                    continue;
64                }
65                if (curMask & (1 << c)) {
66                    st.push_back({c + 1, curMask & ~(1 << c), nextMask, mul});
67                    continue;
68                }
69                if (G[r][c] == '#') {
70                    st.push_back({c + 1, curMask, nextMask, mul});
71                    continue;
72                }
73                // Horizontal
74                if (c + 1 < n && !(curMask & (1 << (c + 1))) && G[r][c + 1] != '#') {
75                    st.push_back({c + 1, curMask | (1 << (c + 1)), nextMask, mul});
76                }
77                // Vertical
78                if (r + 1 < m && G[r + 1][c] != '#') {
79                    st.push_back({c + 1, curMask, nextMask | (1 << c), mul});
80                }
81            }
82        }
83        dp.swap(ndp);
84    }
85
86    cout << dp[0] << "\n";
87    return 0;
88}
89

This classic broken-profile DP counts domino tilings with obstacles. We sweep row by row, maintaining a bitmask that marks which cells in the current row are already occupied—either by horizontal dominos from the left or vertical dominos from the row above. At each cell, we place a horizontal or vertical domino if possible and push the resulting state. While not a full plug DP, it illustrates the sweep-line idea and prepares for adding connectivity (plugs) later.

Time: O(m * n * 2^n) in practice (each row expands 2^n masks with O(n) transitions).Space: O(2^n) for the DP over masks.
Plug DP (labeled) for Hamiltonian path existence from S to T through all free cells
1#include <bits/stdc++.h>
2using namespace std;
3
4// Hamiltonian Path on a grid with obstacles using Plug DP with labeled components.
5// - Every free cell must be visited exactly once.
6// - S and T are endpoints (degree 1), all other free cells degree 2.
7// - We sweep row-major, keep a frontier of down-plugs (n columns) with small labels, and a left-plug.
8// - We forbid closing a cycle early: only allowed if this is the last free cell and no other plugs remain.
9// Notes:
10//   This is an existence (boolean) solver, practical for widths up to ~8..10 with pruning.
11
12struct Key {
13    uint64_t pack; // 4 bits per column encode label at that column (0..15)
14    uint16_t left; // 4 bits label of pending horizontal plug to the right of previous cell
15    bool operator==(const Key& o) const { return pack==o.pack && left==o.left; }
16};
17
18struct KeyHasher {
19    size_t operator()(const Key& k) const noexcept {
20        return (size_t)k.pack ^ (size_t)(k.left * 0x9e3779b1u);
21    }
22};
23
24static inline uint64_t set_nibble(uint64_t x, int pos, int val) {
25    uint64_t mask = 0xFULL << (pos*4);
26    x &= ~mask;
27    x |= (uint64_t)(val & 0xF) << (pos*4);
28    return x;
29}
30
31static inline int get_nibble(uint64_t x, int pos) {
32    return (int)((x >> (pos*4)) & 0xF);
33}
34
35// Normalize labels in (pack, left) to 1..k by first appearance (scan columns, then left)
36static inline void normalize(uint64_t &pack, uint16_t &left, int W) {
37    int maplbl[16];
38    for (int i=0;i<16;++i) maplbl[i]=0;
39    int nxt=1;
40    // scan columns left-to-right
41    for (int c=0;c<W;++c) {
42        int v = get_nibble(pack,c);
43        if (v && !maplbl[v]) maplbl[v]=nxt++;
44    }
45    // include left after columns for determinism
46    if (left && !maplbl[left]) maplbl[left]=nxt++;
47    // rewrite
48    for (int c=0;c<W;++c) {
49        int v = get_nibble(pack,c);
50        if (v) pack = set_nibble(pack,c,maplbl[v]);
51    }
52    if (left) left = maplbl[left];
53}
54
55// Replace all occurrences of label 'b' with 'a' across pack and left
56static inline void merge_labels(uint64_t &pack, uint16_t &left, int W, int a, int b) {
57    if (a==b || b==0) return;
58    for (int c=0;c<W;++c) {
59        int v = get_nibble(pack,c);
60        if (v==b) pack = set_nibble(pack,c,a);
61    }
62    if (left==b) left=a;
63}
64
65int main(){
66    ios::sync_with_stdio(false);
67    cin.tie(nullptr);
68
69    int H,W; cin>>H>>W;
70    vector<string> G(H);
71    for(int i=0;i<H;++i) cin>>G[i];
72
73    pair<int,int> S={-1,-1}, T={-1,-1};
74    int freeCells=0;
75    for(int i=0;i<H;++i){
76        for(int j=0;j<W;++j){
77            if(G[i][j]=='.') freeCells++;
78            else if(G[i][j]=='S'){ S={i,j}; freeCells++; }
79            else if(G[i][j]=='T'){ T={i,j}; freeCells++; }
80        }
81    }
82    if (S.first==-1 || T.first==-1){ cout<<"NO\n"; return 0; }
83
84    unordered_map<Key,char,KeyHasher> cur, nxt;
85    cur.reserve(1<<16); nxt.reserve(1<<16);
86
87    Key init{0ULL, 0};
88    cur[init]=1;
89
90    int processedFree=0;
91
92    for(int i=0;i<H;++i){
93        for(int j=0;j<W;++j){
94            nxt.clear();
95            bool isFree = (G[i][j] != '#');
96            bool isS = (i==S.first && j==S.second);
97            bool isT = (i==T.first && j==T.second);
98            int degReq = isFree ? ((isS||isT)?1:2) : 0;
99            bool lastFreeAfter = isFree && (processedFree+1==freeCells);
100
101            for (auto &it : cur){
102                Key k = it.first;
103                uint64_t pack = k.pack; uint16_t left = k.left;
104                int up = get_nibble(pack, j);
105                int lft = left; // incoming from left
106
107                if (!isFree){
108                    // Blocked: must have no incoming; propagate zeros
109                    if (up==0 && lft==0){
110                        uint64_t p2 = set_nibble(pack,j,0);
111                        uint16_t l2 = 0;
112                        normalize(p2,l2,W);
113                        nxt[{p2,l2}] = 1;
114                    }
115                    continue;
116                }
117
118                // Helper to emit a state
119                auto push_state = [&](uint64_t p2, uint16_t l2){
120                    normalize(p2,l2,W);
121                    nxt[{p2,l2}] = 1;
122                };
123
124                // Degree 2 (regular cells)
125                if (degReq==2){
126                    // Case A: connect L and U (no outgoing)
127                    if (lft && up){
128                        uint64_t p2 = set_nibble(pack,j,0);
129                        uint16_t l2 = 0;
130                        if (lft != up){
131                            int a=min(lft,up), b=max(lft,up);
132                            merge_labels(p2,l2,W,a,b);
133                            push_state(p2,l2);
134                        } else {
135                            // Closing a cycle – only allow if it's the final closure
136                            bool anyOther=false;
137                            for (int c=0;c<W;++c){ if (c==j) continue; if (get_nibble(pack,c)) { anyOther=true; break; } }
138                            if (!anyOther && lastFreeAfter){
139                                push_state(p2,l2); // accept final closure
140                            }
141                        }
142                    }
143                    // Case B: one incoming, one outgoing
144                    // L -> R
145                    if (lft && !up && j+1<W){
146                        uint64_t p2 = set_nibble(pack,j,0); // no vertical here
147                        uint16_t l2 = lft; // propagate to right as left plug for next cell
148                        push_state(p2,l2);
149                    }
150                    // L -> D
151                    if (lft && !up && i+1<H){
152                        uint64_t p2 = set_nibble(pack,j,lft); // continue down
153                        uint16_t l2 = 0;
154                        push_state(p2,l2);
155                    }
156                    // U -> R
157                    if (up && !lft && j+1<W){
158                        uint64_t p2 = set_nibble(pack,j,0);
159                        uint16_t l2 = up;
160                        push_state(p2,l2);
161                    }
162                    // U -> D
163                    if (up && !lft && i+1<H){
164                        uint64_t p2 = pack; // keep same label going down
165                        uint16_t l2 = 0;
166                        push_state(p2,l2);
167                    }
168                    // Case C: no incoming, create two outgoing (R and D)
169                    if (!lft && !up && j+1<W && i+1<H){
170                        // assign new label id = maxLabel+1
171                        int mx=0; for (int c=0;c<W;++c) mx=max(mx,get_nibble(pack,c)); mx=max<int>(mx,lft);
172                        int nid = min(mx+1, 15); // limit to 4-bit labels
173                        if (nid<=15){
174                            uint64_t p2 = set_nibble(pack,j,nid); // down
175                            uint16_t l2 = nid; // right
176                            push_state(p2,l2);
177                        }
178                    }
179                } else { // degReq==1 (S or T)
180                    // Exactly one incident edge
181                    // Terminate L here
182                    if (lft && !up){
183                        uint64_t p2 = set_nibble(pack,j,0);
184                        uint16_t l2 = 0;
185                        push_state(p2,l2);
186                    }
187                    // Terminate U here
188                    if (up && !lft){
189                        uint64_t p2 = set_nibble(pack,j,0);
190                        uint16_t l2 = 0;
191                        push_state(p2,l2);
192                    }
193                    // Start to the right
194                    if (!lft && !up && j+1<W){
195                        int mx=0; for (int c=0;c<W;++c) mx=max(mx,get_nibble(pack,c)); mx=max<int>(mx,lft);
196                        int nid = min(mx+1, 15);
197                        uint64_t p2 = set_nibble(pack,j,0);
198                        uint16_t l2 = nid;
199                        push_state(p2,l2);
200                    }
201                    // Start downward
202                    if (!lft && !up && i+1<H){
203                        int mx=0; for (int c=0;c<W;++c) mx=max(mx,get_nibble(pack,c)); mx=max<int>(mx,lft);
204                        int nid = min(mx+1, 15);
205                        uint64_t p2 = set_nibble(pack,j,nid);
206                        uint16_t l2 = 0;
207                        push_state(p2,l2);
208                    }
209                }
210            }
211
212            if (isFree) processedFree++;
213            cur.swap(nxt);
214        }
215        // At end of row, left plug must be 0 for all states (we already enforce by transitions)
216    }
217
218    // Accept if frontier empty and all free processed
219    bool ok=false;
220    for (auto &it: cur){ if (it.first.pack==0ULL && it.first.left==0) { ok=true; break; } }
221    cout<<(ok?"YES":"NO")<<"\n";
222    return 0;
223}
224

We encode the frontier as n 4-bit labels (downward plugs) plus a single left plug for the horizontal edge to the right of the previous cell. At each free cell, we enforce local degree: 2 for regular cells, 1 for S or T. Transitions either connect left and up (merging components), propagate one incoming to right/down, or create two new plugs (right and down) for degree-2 cells with no incoming. For S/T, we allow exactly one incident edge, either terminating an incoming plug or starting a new one. If connecting two plugs of the same component would form a cycle, we only allow it at the final free cell when no other plugs remain. After processing all cells, a valid Hamiltonian path exists if and only if the final frontier is empty (no pending plugs) and all cells obeyed degree constraints.

Time: Roughly O(H * W * S(W) * W), where S(W) is the number of normalized states for width W; in practice feasible for W ≤ 8–10 with pruning.Space: O(S(W)) states in the frontier hash map; each state packs W 4-bit labels plus one 4-bit left plug.