Core Logic and Mathematical Principles
In the realm of state compression dynamic programming (DP), ordinary binary states (17.1, 17.2) and quaternary plug DP (17.3) are both based on the Fixed-radix Number System. However, when faced with certain non-standard grid constraints, graph coloring problems, or combinatorial optimization problems with dynamic capacity limits, fixed binary or quaternary representations can lead to a large amount of illegal state redundancy (for example: using quaternary to represent at most three states can result in a significant amount of space that can never be effectively mapped, unnecessarily amplifying constants).
To break free from the constraints of fixed bases, we must introduce ternary state compression and a more advanced Minimal Representation based on connected component mapping.
1. Algebraic Isomorphism of Minimal Representation
In Section 17.3, we used bracket matching (left bracket = 1, right bracket = 2) to solve the single loop problem. However, if the problem requires the ability to draw multiple independent loops or to compute merging of connected components in standard graph coloring (such as counting the spanning trees of a tree or connecting multi-colored connected components in a grid), the bracket representation will completely fail. This is because brackets can only express nesting and cannot represent cross-connected topologies such as "plug 1 and plug 3 belong to the same connected component, while plug 2 and plug 4 belong to another connected component".
To eliminate the aftereffect, we must record the specific connected component number to which each plug on the contour line belongs. Suppose there are four plugs on the contour line from left to right, with the actual connectivity being: plugs 0 and 2 are connected, and plugs 1 and 3 are connected. If we directly record this as (1, 2, 1, 2) or (3, 7, 3, 7), it will lead to essentially the same topology being counted as different states due to different numbering.
Core Definition of Minimal Representation:
All positions with plugs on the contour line are renumbered continuously from 1 in the order of first appearance from left to right. Positions without plugs are all recorded as 0.
For the above example, regardless of what the real IDs of the underlying connected components are, after remapping via minimal representation, the state mask uniquely fixes to (1, 2, 1, 2). This geometric dimensionality reduction compresses the explosive set partition number (Bell Number) into an extremely sparse scalar space without loss.
2. Dynamic Number System and State Encoding/Decoding Operators
Since the upper limit of states in minimal representation depends on the number of columns (for example, when $M=6$, at most 3 independent connected components can be produced, with a maximum state value of 3), the most perfect mapping number system at this time is ternary (Base-3) or quinary (Base-5).
To achieve $O(1)$ access in any base during the exam, we need to manually construct a state encoding/decoding operator network beyond bit manipulation:
- Decoding (Decode): Decomposes a decimal integer $S$ into a row/column state array
code[i]. - Encoding (Encode): Normalizes a state array
code[i]via minimal representation and packs it back into the decimal integer $S$.
State Design and Algorithm Derivation
Taking the classic high-difficulty problem "Minimum Spanning Tree (or Multi-loop Grid Skeleton) Based on Connectivity" as an example.
1. State Space and Encoding/Decoding Operator Design
Let the number of columns be $M$. There are $M+1$ positions on the contour line. Define the length of the code array as $M+1$.
-
Decoding Operator `decode(st, code)`:
for (int i = 0; i <= m; ++i) { code[i] = st % 3; // Example in base 3 st /= 3; } -
Encoding and Minimal Representation Normalization Operator `encode(code)`:
int id[10], cnt = 0; memset(id, 0, sizeof(id)); int st = 0; // Reverse packing to ensure spatial symmetry for (int i = m; i >= 0; --i) { if (code[i] > 0) { if (!id[code[i]]) id[code[i]] = ++cnt; // Renumbering from 1 continuously code[i] = id[code[i]]; } st = st * 3 + code[i]; // Packing into base 3 } return st; }
2. Reorganization of Connected Components in State Transition (Reconnection Operator)
When progressing through each cell $(i, j)$, extract the left plug $L = code[j-1]$ and the upper plug $U = code[j]$:
- If $L > 0$ and $U > 0$ and $L eq U$: This indicates that two originally independent connected components are connected at this point. Perform **global coloring merge**: Traverse the entire `code` array and forcibly rewrite all plugs equal to $U$ to $L$.
- If at any moment a connected component is completely erased from the
codearray (i.e., no contour line plug carries this number anymore): It is essential to strictly verify if this is the last connected component of the entire graph. If it is, it belongs to a legitimate conclusion; if the graph has not finished yet, this connected component has already disappeared on the contour line prematurely, indicating it can no longer connect in the future, and the entire spanning tree will break into a forest. This state must be forcibly pruned and discarded immediately.
C++ Standard Source Code (NOIP/Provincial Selection Ultimate State Compression General Template)
The following source code demonstrates the standard industrial implementation of using minimal representation and dynamic ternary for grid full connected component path coverage (skeleton extraction), supporting large constant squeezing optimizations.
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int HASH_SIZE = 30007; // Choose a large prime to resist collisions
const int MAX_STATES = 200005;
int n, m;
int maze[12][12];
int code[15], temp_code[15];
struct HashTable {
int head[HASH_SIZE], next[MAX_STATES], size;
int state[MAX_STATES];
long long value[MAX_STATES];
void clear() {
size = 0;
memset(head, -1, sizeof(head));
}
void insert(int st, long long val) {
int key = st % HASH_SIZE;
for (int i = head[key]; i != -1; i = next[i]) {
if (state[i] == st) {
value[i] = max(value[i], val); // Here we take the maximum weight/value as an example
return;
}
}
state[size] = st;
value[size] = val;
next[size] = head[key];
head[key] = size++;
}
} ht[2];
// Core Operator: Decoding
void decode(int st) {
for (int i = 0; i <= m; ++i) {
code[i] = st % 3;
st /= 3;
}
}
// Core Operator: Normalize and Encode using Minimal Representation
int encode() {
int id[15], cnt = 0;
memset(id, 0, sizeof(id));
int st = 0;
for (int i = m; i >= 0; --i) {
if (code[i] > 0) {
if (!id[code[i]]) id[code[i]] = ++cnt;
code[i] = id[code[i]];
}
st = st * 3 + code[i];
}
return st;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> n >> m)) return 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> maze[i][j]; // 1 indicates empty space, 0 indicates obstacle
}
}
int cur = 0;
ht[cur].clear();
ht[cur].insert(0, 0); // Initial all 0 state
for (int i = 1; i <= n; ++i) {
// When crossing rows, shift the contour line: all plugs move one cell to the right, with 0 added on the left
for (int k = 0; k < ht[cur].size; ++k) {
decode(ht[cur].state[k]);
for (int l = m; l >= 1; --l) code[l] = code[l - 1];
code[0] = 0;
ht[cur].state[k] = encode();
}
for (int j = 1; j <= m; ++j) {
int nxt = cur ^ 1;
ht[nxt].clear();
for (int k = 0; k < ht[cur].size; ++k) {
int st = ht[cur].state[k];
long long val = ht[cur].value[k];
decode(st);
int p_left = code[j - 1]; // Left plug
int p_up = code[j]; // Upper plug
if (!maze[i][j]) {
// Obstacle cell: both plugs must be 0 to pass
if (p_left == 0 && p_up == 0) {
ht[nxt].insert(st, val);
}
continue;
}
// Core Branch A: No plugs on both sides -> Create a new independent connected component out of thin air
if (p_left == 0 && p_up == 0) {
if (maze[i][j + 1] && maze[i + 1][j]) {
code[j - 1] = code[j] = 2; // Temporarily assign an unused independent large number
ht[nxt].insert(encode(), val + 1); // Assume weight is the number of edges
}
}
// Core Branch B: Single plug inflow -> Continue topology
else if (p_left == 0 || p_up == 0) {
int p_val = p_left ? p_left : p_up;
if (maze[i][j + 1]) { // Continue to the right
code[j - 1] = 0; code[j] = p_val;
ht[nxt].insert(encode(), val + 1);
}
decode(st); // Reset state array for the second branch decision
if (maze[i + 1][j]) { // Continue downwards
code[j - 1] = p_val; code[j] = 0;
ht[nxt].insert(encode(), val + 1);
}
}
// Core Branch C: Two plugs inflow and belong to different connected components -> Perform strong connected component coloring merge
else if (p_left > 0 && p_up > 0 && p_left != p_up) {
int src = p_up, dst = p_left;
for (int l = 0; l <= m; ++l) {
if (code[l] == src) code[l] = dst; // Batch coloring
}
code[j - 1] = code[j] = 0; // Current cell merges and disappears
ht[nxt].insert(encode(), val + 1);
}
// Core Branch D: Two plugs inflow and are already in the same connected component -> Close loop determination
else if (p_left > 0 && p_up > 0 && p_left == p_up) {
code[j - 1] = code[j] = 0;
int remaining_blocks = 0;
int check_st = encode();
// Check if there are other residual plugs on the contour line
if (check_st == 0) {
// Completely closed and no other connected components in the entire graph, belongs to a perfect ending solution
ht[nxt].insert(0, val + 1);
}
}
}
cur = nxt;
}
}
// Collect the maximum benefit from the final completely closed single connected component (state 0)
long long ans = 0;
for (int k = 0; k < ht[cur].size; ++k) {
if (ht[cur].state[k] == 0) {
ans = max(ans, ht[cur].value[k]);
}
}
cout << ans << "\n";
return 0;
}NOIP/Provincial Selection Practical Pitfall Guide
1. Omitting the Clearing and Restructuring of code Array During Encoding (Dirty Data Residue Pollution)
- Phenomenon: In the branching decision, contestants directly modify
code[j-1]andcode[j], but when entering the next loop iteration or inserting new states, due to not completely reshuffling the entire contour line for renumbering, the old connected component numbers after the last large coloring merge remain in memory as dirty data. This can lead to widespread misjudgments in state conflict checks, directly resulting in WA (Wrong Answer). - Avoidance Method: Before executing
encode()after each state decision, it is essential to strictly renormalize the numbering (as implemented in the source code using theidarray to relabel from 1).
2. Ignoring the Early Abnormal Demise of Isolated Connected Components (Forest Breakage Vulnerability)
- Phenomenon: In the branch transfer, two paths converge, causing a connected component number to be completely cleared from the contour line. If no checks are added and this state is directly thrown into the hash table, it can lead to the tragedy of "an independent closed loop being formed in the middle while external places are still continuing to draw lines". For problems requiring "the entire graph must form a single connected graph (such as a spanning tree)", this vulnerability can cause the computed results to be far greater than the correct answer.
- Avoidance Method: Whenever a number disappears, it is necessary to immediately scan the
codearray horizontally to check if there are any elements greater than 0. If other elements exist, it indicates that this disappearance is an illegal premature disconnection, and it must directlycontinueto prune.