AIOJ

Definition

Some state-compression DP problems require us to record connectivity information in the state. Such problems are often called plug DP or connectivity state-compression DP. Examples include counting Hamiltonian paths in grid graphs, counting black-and-white colorings of a board in which cells of each color form a connected component, and counting spanning trees of a particular graph. These problems generally require us to encode state connectivity and discuss how connectivity changes during state transitions.

Introduction

Domino Tiling and Profile DP

Before learning plug DP, let us first review a classic problem.

Example Problem “HDU 1400” Mondriaan’s Dream

Problem statement: Completely tile an $N\times M$ board with $1\times 2$ or $2\times 1$ dominoes, and find the number of ways.

When $n$ or $m$ are not large, this type of problem can be solved using state-compression DP. Divide the process into stages by row, and let $dp(i,s)$ denote the number of ways after the first $i$ rows have been considered, with the state of row $i$ equal to $s$ . Each bit of the state $s$ can indicate whether the corresponding position has already been covered by the previous row.

domino

Another way to divide the process into stages is cell-by-cell DP, also called profile DP. $dp(i,j,s)$ denotes the number of ways after considering row $i$ , column $j$ , with state $s$ on the current contour line.

Although the state in cell-by-cell DP gains one extra dimension, the transition time complexity is reduced to $O(1)$ , so the overall time complexity is unchanged. Let $f_0$ represent the state at the current stage and $f_1$ the state at the next stage. If $u = f_0(s)$ is the function value for the state currently being enumerated, the state transition equations are:

if (s >> j & 1) {       // if already covered
  f1[s ^ 1 << j] += u;  // do not place
} else {                // if not covered
  if (j != m - 1 && (!(s >> j + 1 & 1))) f1[s ^ 1 << j + 1] += u;  // place horizontally
  f1[s ^ 1 << j] += u;                                             // place vertically
}

We can observe that the equations for not placing and placing vertically here can be merged.

Implementation

#include <algorithm>
#include <iostream>
using namespace std;
constexpr int N = 11;
long long f[2][1 << N], *f0, *f1;
int n, m;

int main() {
  while (cin >> n >> m && n) {
    f0 = f[0];
    f1 = f[1];
    fill(f1, f1 + (1 << m), 0);
    f1[0] = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        swap(f0, f1);
        fill(f1, f1 + (1 << m), 0);
#define u f0[s]
        for (int s = 0; s < 1 << m; ++s)
          if (u) {
            if (j != m - 1 && (!(s >> j & 3))) f1[s ^ 1 << j + 1] += u;  // place horizontally
            f1[s ^ 1 << j] += u;  // place vertically or do not place
          }
      }
    }
    cout << f1[0] << endl;
  }
}

Exercise “SRM 671. Div 1 900” BearDestroys

Problem statement: Given an $n\times m$ matrix, each cell contains E or S. A scoring rule is defined for a matrix. Scan the cells in row-major order; if a cell has already been occupied by a domino, skip it. Otherwise, try to place a domino. If the placement direction goes outside the matrix or the target cells are occupied by other dominoes, placement fails; switch to the other option or skip. If it is E, first try to place a $1\times 2$ domino, and if it is S, first try to place a $2\times 1$ domino. The score of a matrix is the final number of dominoes placed. Find the sum of the scores over all $2^{nm}$ matrices.

Terminology

Stage: the order in which dynamic programming is executed; the result of a later stage depends only on results from preceding stages (the no-aftereffect property). Many DP problems can be divided into stages in multiple ways. For example, in knapsack problems, stages can usually be divided by items or by knapsack capacity (that is, by what the outer loop enumerates). In domino problems, stages can be divided according to rows, columns, cells, diagonals, and other features.

Contour line: the boundary between decided and undecided states.

contour line

Plug: the presence of a plug of a cell in a given direction indicates that the cell is connected to its neighboring cell in that direction.

plug

Path Model

Multiple Cycles

Examples

Example Problem “HDU 1693” Eat the Trees

Problem statement: Count the number of ways to cover an $N\times M$ board with several cycles; some positions are obstacles.

Strictly speaking, the multiple-cycle problem is not a plug DP problem, because, as in the domino tiling problem above, we only need to record whether plugs exist, then merge and create plugs in pairs.

For a board of width $m$ , the contour line has width $m+1$ , because it contains $m$ upward plugs and $1$ left plug. Notice that after iterating through a row, the rightmost left plug is usually an invalid state, while we need to add the first left plug of the next row. This requires adjusting the current contour-line state. Usually, all states are shifted left; we call this operation rolling roll().

Example code

#include <iostream>
using namespace std;
constexpr int N = 11;
long long f[2][1 << (N + 1)], *f0, *f1;
int n, m;

int main() {
  int T;
  cin >> T;
  for (int Case = 1; Case <= T; ++Case) {
    cin >> n >> m;
    f0 = f[0];
    f1 = f[1];
    fill(f1, f1 + (1 << (m + 1)), 0);
    f1[0] = 1;  // initialize
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        bool bad;
        cin >> bad;
        bad ^= 1;
        swap(f0, f1);
        fill(f1, f1 + (1 << (m + 1)), 0);
        for (int s = 0; s < 1 << (m + 1); ++s)  // the specific DP transitions; everything above is initialization
          if (f0[s]) {
            bool lt = s >> j & 1, up = s >> (j + 1) & 1;
            if (bad) {
              if (!lt && !up) f1[s] += f0[s];
            } else {
              f1[s ^ 3 << j] += f0[s];
              if (lt != up) f1[s] += f0[s];
            }
          }
      }
      swap(f0, f1);
      fill(f1, f1 + (1 << (m + 1)), 0);
      for (int s = 0; s < 1 << m; ++s) f1[s << 1] = f0[s];
    }
    cout << "Case " << Case << ": There are " << f1[0]
         << " ways to eat the trees.\n";
  }
}

Exercises

Exercise “ZOJ 3466” The Hive II

Problem statement: Same as the previous problem, but the cells are hexagonal.

A Single Cycle

Examples

Example Problem “Andrew Stankevich Contest 16 - Problem F” Pipe Layout

Problem statement: Count the number of ways to cover an $N\times M$ board with a single cycle.

In the state representation above, every time we merge a group of connected plugs, we create an independent cycle. Therefore, in this problem, we also need to distinguish connectivity between plugs (here it appears!). This requires additional encoding of the state.

State Encoding

The usual encoding schemes include bracket representations and minimal representations; here we focus on the more generally applicable minimal representation. We use an integer array of length $m+1$ to record the state of each plug on the contour line. $0$ indicates no plug, and connected plugs are marked with the same number.

Thus, the following two encodings represent the same state:

0 3 1 0 1 3
0 1 2 0 2 1

We map equivalent states to the lexicographically smallest representation; for example, 0 1 2 0 2 1 above is a minimal representation.

We use the array b[] to represent the states of plugs on the contour line. bb[] records the smallest number to which each number is mapped during encoding into the minimal representation. Note that $0$ means no plug and cannot be mapped to another value.

Implementation

int b[M + 1], bb[M + 1];

int encode() {
  int s = 0;
  memset(bb, -1, sizeof(bb));
  int bn = 1;
  bb[0] = 0;
  for (int i = m; i >= 0; --i) {
#define bi bb[b[i]]
    if (!~bi) bi = bn++;
    s <<= offset;
    s |= bi;
  }
  return s;
}

void decode(int s) {
  REP(i, m + 1) {
    b[i] = s & mask;
    s >>= offset;
  }
}

We note that plugs always appear and disappear in pairs. Therefore, a state such as 0 1 2 0 1 2 is invalid. Valid states form a bracket sequence; in practice, valid states may be very sparse.

Handwritten Hash

In some state-compression DP problems, valid states may be sparse (as in this problem). To optimize time and space, we can use a hash table to store valid DP states. For C++ contestants, we can use std::unordered_map; alternatively, we can implement it by hand, which lets us flexibly encapsulate the state transition function as well.

Implementation

constexpr int MaxSZ = 16796, Prime = 9973;

struct hashTable {
  int head[Prime], next[MaxSZ], sz;
  int state[MaxSZ];
  long long key[MaxSZ];

  void clear() {
    sz = 0;
    memset(head, -1, sizeof(head));
  }

  void push(int s) {
    int x = s % Prime;
    for (int i = head[x]; ~i; i = next[i]) {
      if (state[i] == s) {
        key[i] += d;
        return;
      }
    }
    state[sz] = s, key[sz] = d;
    next[sz] = head[x];
    head[x] = sz++;
  }

  void roll() { REP(i, sz) state[i] <<= offset; }
} H[2], *H0, *H1;

The code above uses:

MaxSZ denotes the upper bound on the number of valid states; it can be estimated or precomputed more precisely.
Prime is a large prime smaller than MaxSZ.
head[] is the pointer to the head node.
next[] is the pointer to the next state.
state[] stores the state of a node.
key[] is the key of a node, which in this problem is the number of ways.
clear() is the initialization function. As with a handwritten adjacency list, we only need to initialize the pointers to the head nodes.
push() is the state transition function. Here d is a global variable (to save effort), representing the increment contributed by each state transition. If the state is found, add with +=; otherwise, create a new node whose state is s and whose key is d.
roll() rolls the contour line after a complete row has been iterated.

For complexity analysis of hash tables, and the differences between open hashing and closed hashing, see the chapters on hash tables in Introduction to Algorithms.

State Transitions

Implementation

REP(ii, H0->sz) {
  decode(H0->state[ii]);                  // retrieve and decode the state
  d = H0->key[ii];                        // get the increment delta
  int lt = b[j], up = b[j + 1];           // left plug, upper plug
  bool dn = i != n - 1, rt = j != m - 1;  // downward plug, right plug
  if (lt && up) {                         // if both left and upper plugs exist
    if (lt == up) {                       // from the same connected component
      if (i == n - 1 &&
          j == m - 1) {  // only the last cell may merge them and close the cycle.
        push(j, 0, 0);
      }
    } else {  // otherwise, these two connected components must be merged, because this problem requires cycle coverage
      REP(i, m + 1) if (b[i] == lt) b[i] = up;
      push(j, 0, 0);
    }
  } else if (lt || up) {  // if exactly one of the left and upper positions has a plug
    int t = lt | up;      // get that plug
    if (dn) {             // if it can extend downward
      push(j, t, 0);
    }
    if (rt) {  // if it can extend rightward
      push(j, 0, t);
    }
  } else {           // if neither left nor upper position has a plug
    if (dn && rt) {  // create a new pair of plugs
      push(j, m, m);
    }
  }
}

Example code

#include <cassert>
#include <cstring>
#include <iostream>
using namespace std;
constexpr int M = 10;
constexpr int offset = 3, mask = (1 << offset) - 1;
int n, m;
long long ans, d;
constexpr int MaxSZ = 16796, Prime = 9973;

struct hashTable {
  int head[Prime], next[MaxSZ], sz;
  int state[MaxSZ];
  long long key[MaxSZ];

  void clear() {
    sz = 0;
    memset(head, -1, sizeof(head));
  }

  void push(int s) {
    int x = s % Prime;
    for (int i = head[x]; ~i; i = next[i]) {
      if (state[i] == s) {
        key[i] += d;
        return;
      }
    }
    state[sz] = s, key[sz] = d;
    next[sz] = head[x];
    head[x] = sz++;
  }

  void roll() {
    for (int i = 0; i < sz; i++) state[i] <<= offset;
  }
} H[2], *H0, *H1;

int b[M + 1], bb[M + 1];

int encode() {
  int s = 0;
  memset(bb, -1, sizeof(bb));
  int bn = 1;
  bb[0] = 0;
  for (int i = m; i >= 0; --i) {
    if (!~bb[b[i]]) bb[b[i]] = bn++;
    s <<= offset;
    s |= bb[b[i]];
  }
  return s;
}

void decode(int s) {
  for (int i = 0; i < m + 1; i++) {
    b[i] = s & mask;
    s >>= offset;
  }
}

void push(int j, int dn, int rt) {
  b[j] = dn;
  b[j + 1] = rt;
  H1->push(encode());
}

int main() {
  cin >> n >> m;
  if (m > n) swap(n, m);
  H0 = H, H1 = H + 1;
  H1->clear();
  d = 1;
  H1->push(0);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      swap(H0, H1);
      H1->clear();
      for (int ii = 0; ii < (H0->sz); ii++) {
        decode(H0->state[ii]);
        d = H0->key[ii];
        int lt = b[j], up = b[j + 1];
        bool dn = i != n - 1, rt = j != m - 1;
        if (lt && up) {
          if (lt == up) {
            if (i == n - 1 && j == m - 1) {
              push(j, 0, 0);
            }
          } else {
            for (int i = 0; i < m + 1; i++)
              if (b[i] == lt) b[i] = up;
            push(j, 0, 0);
          }
        } else if (lt || up) {
          int t = lt | up;
          if (dn) {
            push(j, t, 0);
          }
          if (rt) {
            push(j, 0, t);
          }
        } else {
          if (dn && rt) {
            push(j, m, m);
          }
        }
      }
    }
    H1->roll();
  }
  assert(H1->sz <= 1);
  cout << (H1->sz == 1 ? H1->key[0] : 0) << endl;
}

Exercises

Exercise “Ural 1519” Formula 1

Problem statement: Count the number of ways to cover an $N\times M$ board with a single cycle; some positions are obstacles.

Exercise “USACO 5.4.4” Betsy’s Tours

Problem statement: Given an $N\times N$ square matrix ( $N\le 7$ ), count the paths that start at the upper-left corner, end at the lower-left corner, and visit every cell. Although this is a path, the fixed endpoints allow it to be converted into a cycle problem.

Exercise “POJ 1739” Tony’s Tour

Problem statement: Given an $N\times M$ board, count the paths that start at the lower-left corner, end at the lower-right corner, and visit every cell; some positions are obstacles.

Exercise “USACO 6.1.1” Postal Vans

Problem statement: Count the ways to cover a $4\times N$ board with one directed cycle; high-precision arithmetic is required.

Exercise “HNOI 2007” Magical Amusement Park

Problem statement: Given an $n\times m$ grid graph with a weight in each cell, find any cycle that maximizes the sum of the weights of the cells it visits.

Exercise “ProjectEuler 393” Migrating ants

Problem statement: Cover an $n\times n$ square with multiple cycles. Each solution with $m$ cycles contributes $2^m$ to the answer; find the sum of the contributions of all solutions.

A Single Path

Examples

Example Problem “ZOJ 3213” Beautiful Meadow

Problem statement: Given an $N\times M$ square matrix ( $N,M\le 8$ ) with a weight at every grid point, find a path that maximizes the sum of the weights of the grid points it covers.

This is a standard single-path problem. In a single-path problem, the encoded state may also contain unmatched independent plugs. The state transition function must additionally handle the generation, merging, and disappearance of independent plugs. The generation and disappearance of an independent plug correspond to one endpoint of the path; consequently, such events occur no more than twice (once for a generation and once for a disappearance, or two generations and one merge), otherwise the final result necessarily contains multiple connected components.

We need to record the total number of occurrences of these events in the state. This information can be encoded into the state (note that extra information of this kind does not need to roll when adjusting the contour line), or we can add a dimension outside the hashTable array. The example program below uses the latter.

State Transitions

Implementation

REP(i, n) {
  REP(j, m) {
    checkMax(ans, A[i][j]);  // the single-cell case needs to be handled separately
    if (!A[i][j]) continue;  // if it is an obstacle, skip it; note that the state array does not need to roll here
    swap(H0, H1);
    REP(c, 3)
    H1[c].clear();  // c is the total number of generation and disappearance events, at most 2
    REP(c, 3) REP(ii, H0[c].sz) {
      decode(H0[c].state[ii]);
      d = H0[c].key[ii] + A[i][j];
      int lt = b[j], up = b[j + 1];
      bool dn = A[i + 1][j], rt = A[i][j + 1];
      if (lt && up) {
        if (lt == up) {  // in a single-path problem, we cannot merge identical plugs.
          // Cannot deploy here...
        } else {  // one of the two being merged may be an independent plug, but the same code fragment handles it
          REP(i, m + 1) if (b[i] == lt) b[i] = up;
          push(c, j, 0, 0);
        }
      } else if (lt || up) {
        int t = lt | up;
        if (dn) {
          push(c, j, t, 0);
        }
        if (rt) {
          push(c, j, 0, t);
        }
        // when a plug disappears: for an independent plug this means disappearance, while for a pair of plugs it is equivalent to generating an independent plug,
        // either kind of event requires increasing c by 1.
        if (c < 2) {
          push(c + 1, j, 0, 0);
        }
      } else {
        d -= A[i][j];
        H1[c].push(H0[c].state[ii]);
        d += A[i][j];    // skip generating plugs; this problem does not require complete coverage
        if (dn && rt) {  // create a pair of plugs
          push(c, j, m, m);
        }
        if (c < 2) {  // create an independent plug
          if (dn) {
            push(c + 1, j, m, 0);
          }
          if (rt) {
            push(c + 1, j, 0, m);
          }
        }
      }
    }
  }
  REP(c, 3) H1[c].roll();  // end of a row; adjust the contour line
}

Example code

#include <cstring>
#include <iostream>
using namespace std;

template <class T>
bool checkMax(T &a, const T b) {
  return a < b ? a = b, true : false;
}

constexpr int N = 8, M = 8;
constexpr int offset = 3, mask = (1 << offset) - 1;
int A[N + 1][M + 1];
int n, m;
int ans, d;
constexpr int MaxSZ = 16796, Prime = 9973;

struct hashTable {
  int head[Prime], next[MaxSZ], sz;
  int state[MaxSZ];
  int key[MaxSZ];

  void clear() {
    sz = 0;
    memset(head, -1, sizeof(head));
  }

  void push(int s) {
    int x = s % Prime;
    for (int i = head[x]; ~i; i = next[i]) {
      if (state[i] == s) {
        checkMax(key[i], d);
        return;
      }
    }
    state[sz] = s, key[sz] = d;
    next[sz] = head[x];
    head[x] = sz++;
  }

  void roll() {
    for (int i = 0; i < sz; i++) state[i] <<= offset;
  }
} H[2][3], *H0, *H1;

int b[M + 1], bb[M + 1];

int encode() {
  int s = 0;
  memset(bb, -1, sizeof(bb));
  int bn = 1;
  bb[0] = 0;
  for (int i = m; i >= 0; --i) {
    if (!~bb[b[i]]) bb[b[i]] = bn++;
    s <<= offset;
    s |= bb[b[i]];
  }
  return s;
}

void decode(int s) {
  for (int i = 0; i < m + 1; i++) {
    b[i] = s & mask;
    s >>= offset;
  }
}

void push(int c, int j, int dn, int rt) {
  b[j] = dn;
  b[j + 1] = rt;
  H1[c].push(encode());
}

void init() {
  cin >> n >> m;
  H0 = H[0], H1 = H[1];
  for (int c = 0; c < 3; c++) H1[c].clear();
  d = 0;
  H1[0].push(0);
  memset(A, 0, sizeof(A));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) cin >> A[i][j];
}

void solve() {
  ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      checkMax(ans, A[i][j]);  // the single-cell case needs to be handled separately
      if (!A[i][j]) continue;  // if it is an obstacle, skip it; note that the state array does not need to roll here
      swap(H0, H1);
      for (int c = 0; c < 3; c++)
        H1[c].clear();  // c is the total number of generation and disappearance events, at most 2
      for (int c = 0; c < 3; c++)
        for (int ii = 0; ii < H0[c].sz; ii++) {
          decode(H0[c].state[ii]);
          d = H0[c].key[ii] + A[i][j];
          int lt = b[j], up = b[j + 1];
          bool dn = A[i + 1][j], rt = A[i][j + 1];
          if (lt && up) {
            if (lt == up) {  // in a single-path problem, we cannot merge identical plugs.
              // Cannot deploy here...
            } else {  // one of the two being merged may be an independent plug, but the same code fragment handles it
              for (int i = 0; i < m + 1; i++)
                if (b[i] == lt) b[i] = up;
              push(c, j, 0, 0);
            }
          } else if (lt || up) {
            int t = lt | up;
            if (dn) {
              push(c, j, t, 0);
            }
            if (rt) {
              push(c, j, 0, t);
            }
            // when a plug disappears: for an independent plug this means disappearance, while for a pair of plugs it is equivalent to generating an independent plug,
            // either kind of event requires increasing c by 1.
            if (c < 2) {
              push(c + 1, j, 0, 0);
            }
          } else {
            d -= A[i][j];
            H1[c].push(H0[c].state[ii]);
            d += A[i][j];  // skip generating plugs; this problem does not require complete coverage
            if (dn && rt) {  // create a pair of plugs
              push(c, j, m, m);
            }
            if (c < 2) {  // create an independent plug
              if (dn) {
                push(c + 1, j, m, 0);
              }
              if (rt) {
                push(c + 1, j, 0, m);
              }
            }
          }
        }
    }
    for (int c = 0; c < 3; c++) H1[c].roll();  // end of a row; adjust the contour line
  }
  for (int ii = 0; ii < H1[2].sz; ii++) checkMax(ans, H1[2].key[ii]);
  cout << ans << endl;
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    init();
    solve();
  }
}

Exercises

Exercise “BZOJ 2310” ParkII

Problem statement: Given an $m\times n$ board with a weight at every grid point, find a path cover that maximizes the sum of the weights of the points visited by the path.

Exercise “NOI 2010 Day2” Travel Route

Problem statement: Given an $n\times m$ board in which each cell has a 0–1 weight T[x][y], find a path cover such that:

The i-th visited grid point (x, y) satisfies T[x][y] = L[i].
One endpoint of the path lies on the boundary of the board.

Find the number of feasible solutions.

Coloring Model

Besides path models, another common class of models colors a board, with adjacent nodes of the same color regarded as connected. In path problems, state transitions enumerate the direction of the current path; in coloring problems, they enumerate the color assigned to the current node. In the coloring model, more than two nodes in the state may have the same connectivity. Overall, however, the ideas are still largely the same. Let us look at a classic example.

Example “UVa 10572” Black & White

Example Problem “UVa 10572” Black & White

Problem statement: Color the uncolored grid points of an $N\times M$ board black or white so that all black regions and all white regions are connected, and the colors in every $2\times 2$ subrectangle are not all identical (the situation shown below is invalid). Count the valid colorings and construct one valid solution.

black_and_white1

State Encoding

We first consider state encoding. Ignoring connectivity, this is SGU 197. Nice Patterns Strike Back, which can be solved directly with state-compression DP. Now the state must represent both color and connectivity. Consider the state at each position on the contour line: every Offset bits in the binary representation describes one position on the contour line. Since there are only two colors, we use the parity of the least significant bit to represent color, while the remaining bits represent connectivity.

For the nodes above the first row and to the left of the first column, we could introduce a third color to distinguish them and avoid special cases. Here we observe that the connectivity information of these boundary states is always 0, so no additional encoding is needed for the third color.

In the path problem, our contour line consists of $m$ upper plugs and $1$ left plug. In this problem, because we also need to determine whether the $2\times 2$ subrectangle whose lower-right corner is the current grid point is valid, we need to record the color of the upper-left cell, so the contour line still has length $m+1$ .

This encoding scheme still retains a great deal of redundant information (the colors of connected regions must be the same, and the upper-left cell needs only color information, not connectivity), but since we already use a hash table and a minimal representation, the impact on time complexity is small. To reduce programming effort, we do not refine the encoding further.

In the worst case (for example, when the first row alternates black and white), the connectivity information of every plug is different. Therefore, we need $4$ binary bits to record connectivity, plus the color information; the Offset in this problem is $5$ bits.

Implementation

constexpr int Offset = 5, Mask = (1 << Offset) - 1;
int c[N + 2];
int b[N + 2], bb[N + 3];

T_state encode() {
  T_state s = 0;
  memset(bb, -1, sizeof(bb));
  int bn = 1;
  bb[0] = 0;
  for (int i = m; i >= 0; --i) {
#define bi bb[b[i]]
    if (!~bi) bi = bn++;
    s <<= Offset;
    s |= (bi << 1) | c[i];
  }
  return s;
}

void decode(T_state s) {
  REP(i, m + 1) {
    b[i] = s & Mask;
    c[i] = b[i] & 1;
    b[i] >>= 1;
    s >>= Offset;
  }
}

Handwritten Hash

Because we need to construct an arbitrary valid solution, we add a field pre[] to the hash table to record any predecessor of each state in the previous stage.

Implementation

constexpr int Prime = 9979, MaxSZ = 1 << 20;

template <class T_state, class T_key>
struct hashTable {
  int head[Prime];
  int next[MaxSZ], sz;
  T_state state[MaxSZ];
  T_key key[MaxSZ];
  int pre[MaxSZ];

  void clear() {
    sz = 0;
    memset(head, -1, sizeof(head));
  }

  void push(T_state s, T_key d, T_state u) {
    int x = s % Prime;
    for (int i = head[x]; ~i; i = next[i]) {
      if (state[i] == s) {
        key[i] += d;
        return;
      }
    }
    state[sz] = s, key[sz] = d, pre[sz] = u;
    next[sz] = head[x], head[x] = sz++;
  }

  void roll() { REP(ii, sz) state[ii] <<= Offset; }
};

hashTable<T_state, T_key> _H, H[N][N], *H0, *H1;

Solution Construction

With the information above, we can easily construct a solution. First traverse the states in the current hash table. If the number of connected components is no more than $2$ , include the state in the solution count. If the count is not $0$ , construct a solution backward using the pre array. Note that at the end of each row, because we perform the Roll() operation, the color must be taken from c[j+1].

Implementation

void print() {
  T_key z = 0;
  int u;
  REP(i, H1->sz) {
    decode(H1->state[i]);
    if (*max_element(b + 1, b + m + 1) <= 2) {
      z += H1->key[i];
      u = i;
    }
  }
  cout << z << endl;
  if (z) {
    DWN(i, n, 0) {
      B[i][m] = 0;
      DWN(j, m, 0) {
        decode(H[i][j].state[u]);
        int cc = j == m - 1 ? c[j + 1] : c[j];
        B[i][j] = cc ? 'o' : '#';
        u = H[i][j].pre[u];
      }
    }
    REP(i, n) puts(B[i]);
  }
  puts("");
}

State Transitions

We use the following notation:

cc is the color of the cell currently being colored
lf is the color of the cell on the left
up is the color of the cell above
lu is the color of the upper-left cell

We use $-1$ to indicate that a color does not exist. We now discuss the state transitions; there are three cases: merging, inheriting, and generating.

State transitions - code

void trans(int i, int j, int u, int cc) {
  decode(H0->state[u]);
  int lf = j ? c[j - 1] : -1, lu = b[j] ? c[j] : -1,
      up = b[j + 1] ? c[j + 1] : -1;  // no color is also a kind of color!
  if (lf == cc && up == cc) {         // merge
    if (lu == cc) return;             // the case where the 2x2 subrectangle has identical colors
    int lf_b = b[j - 1], up_b = b[j + 1];
    REP(i, m + 1) if (b[i] == up_b) { b[i] = lf_b; }
    b[j] = lf_b;
  } else if (lf == cc || up == cc) {  // inherit
    if (lf == cc)
      b[j] = b[j - 1];
    else
      b[j] = b[j + 1];
  } else {                                             // generate
    if (i == n - 1 && j == m - 1 && lu == cc) return;  // special case
    b[j] = m + 2;
  }
  c[j] = cc;
  if (!ok(i, j, cc)) return;  // check whether generating a closed connected component would make the state invalid
  H1->push(encode(), H0->key[u], u);
}

For the last case, note that once a closed connected region has been created, we must not color another cell with its color; otherwise, that color would have two connected components. It seems that we need to record this event. We can follow “ZOJ 3213” Beautiful Meadow and add another dimension to record it. However, because of this problem’s special properties, we can also handle it with a special case.

Special case - code

bool ok(int i, int j, int cc) {
  if (cc == c[j + 1]) return true;
  int up = b[j + 1];
  if (!up) return true;
  int c1 = 0, c2 = 0;
  REP(i, m + 1) if (i != j + 1) {
    if (b[i] == b[j + 1]) {  // same connectivity implies same color
      assert(c[i] == c[j + 1]);
    }
    if (c[i] == c[j + 1] && b[i] == b[j + 1]) ++c1;
    if (c[i] == c[j + 1]) ++c2;
  }
  if (!c1) {               // if a new closed connected component would be formed
    if (c2) return false;  // if the same color still exists on the contour line
    if (i < n - 1 || j < m - 2) return false;
  }
  return true;
}

Let us further discuss the disappearance of connected components. Whenever we color a cell, if no other cell is connected to the cell above it, a closed connected component is formed. This event can occur only in the last two columns of the last row; otherwise, to avoid a monochromatic $2\times 2$ connected block later, this color must appear again, except in the following case:

2 2
o#
#o

We handle this case specially, so in this problem we can take the shortcut of not recording whether a closed connected component has already been created.

Example code

#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
using namespace std;
using T_state = long long;
using T_key = int;
constexpr int N = 8;
int n, m;
char A[N + 1][N + 1], B[N + 1][N + 1];
constexpr int Offset = 5, Mask = (1 << Offset) - 1;
int c[N + 2];
int b[N + 2], bb[N + 3];

T_state encode() {
  T_state s = 0;
  memset(bb, -1, sizeof(bb));
  int bn = 1;
  bb[0] = 0;
  for (int i = m; i >= 0; --i) {
    if (!~bb[b[i]]) bb[b[i]] = bn++;
    s <<= Offset;
    s |= (bb[b[i]] << 1) | c[i];
  }
  return s;
}

void decode(T_state s) {
  for (int i = 0; i < m + 1; i++) {
    b[i] = s & Mask;
    c[i] = b[i] & 1;
    b[i] >>= 1;
    s >>= Offset;
  }
}

constexpr int Prime = 9979, MaxSZ = 1 << 20;

template <class T_state, class T_key>
struct hashTable {
  int head[Prime];
  int next[MaxSZ], sz;
  T_state state[MaxSZ];
  T_key key[MaxSZ];
  int pre[MaxSZ];

  void clear() {
    sz = 0;
    memset(head, -1, sizeof(head));
  }

  void push(T_state s, T_key d, T_state u) {
    int x = s % Prime;
    for (int i = head[x]; ~i; i = next[i]) {
      if (state[i] == s) {
        key[i] += d;
        return;
      }
    }
    state[sz] = s, key[sz] = d, pre[sz] = u;
    next[sz] = head[x], head[x] = sz++;
  }

  void roll() {
    for (int ii = 0; ii < sz; ii++) state[ii] <<= Offset;
  }
};

hashTable<T_state, T_key> _H, H[N][N], *H0, *H1;

bool ok(int i, int j, int cc) {
  if (cc == c[j + 1]) return true;
  int up = b[j + 1];
  if (!up) return true;
  int c1 = 0, c2 = 0;
  for (int i = 0; i < m + 1; i++)
    if (i != j + 1) {
      if (b[i] == b[j + 1]) {  // Equal connectivity implies equal colors
        assert(c[i] == c[j + 1]);
      }
      if (c[i] == c[j + 1] && b[i] == b[j + 1]) ++c1;
      if (c[i] == c[j + 1]) ++c2;
    }
  if (!c1) {               // If this creates a new closed component
    if (c2) return false;  // If the same color still occurs on the contour
    if (i < n - 1 || j < m - 2) return false;
  }
  return true;
}

void trans(int i, int j, int u, int cc) {
  decode(H0->state[u]);
  int lf = j ? c[j - 1] : -1, lu = b[j] ? c[j] : -1,
      up = b[j + 1] ? c[j + 1] : -1;  // No color is also a color
  if (lf == cc && up == cc) {         // Merge
    if (lu == cc) return;             // The 2x2 subrectangle has one color
    int lf_b = b[j - 1], up_b = b[j + 1];
    for (int i = 0; i < m + 1; i++)
      if (b[i] == up_b) {
        b[i] = lf_b;
      }
    b[j] = lf_b;
  } else if (lf == cc || up == cc) {  // Inherit
    if (lf == cc)
      b[j] = b[j - 1];
    else
      b[j] = b[j + 1];
  } else {                                             // Create
    if (i == n - 1 && j == m - 1 && lu == cc) return;  // Special case
    b[j] = m + 2;
  }
  c[j] = cc;
  if (!ok(i, j, cc)) return;  // Check whether creating a closed component makes the state invalid
  H1->push(encode(), H0->key[u], u);
}

void init() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> A[i];
}

void solve() {
  H1 = &_H, H1->clear(), H1->push(0, 1, 0);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      H0 = H1, H1 = &H[i][j], H1->clear();
      for (int u = 0; u < H0->sz; u++) {
        if (A[i][j] == '.' || A[i][j] == '#') trans(i, j, u, 0);
        if (A[i][j] == '.' || A[i][j] == 'o') trans(i, j, u, 1);
      }
    }
    H1->roll();
  }
}

void print() {
  T_key z = 0;
  int u;
  for (int i = 0; i < H1->sz; i++) {
    decode(H1->state[i]);
    if (*max_element(b + 1, b + m + 1) <= 2) {
      z += H1->key[i];
      u = i;
    }
  }
  cout << z << endl;
  if (z) {
    for (int i = n - 1; i >= 0; i--) {
      B[i][m] = 0;
      for (int j = m - 1; j >= 0; j--) {
        decode(H[i][j].state[u]);
        int cc = j == m - 1 ? c[j + 1] : c[j];
        B[i][j] = cc ? 'o' : '#';
        u = H[i][j].pre[u];
      }
    }
    for (int i = 0; i < n; i++) cout << B[i] << '\n';
  }
  cout << '\n';
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) {
    init();
    solve();
    print();
  }
}

Exercises

Exercise: “Topcoder SRM 312. Div1 Hard” CheapestIsland

Problem: Given a grid graph with a weight on each cell, find the connected component with minimum total weight.

Exercise: “JLOI 2009” Mysterious Creature

Problem: Given a grid graph with a weight on each cell, find the connected component with maximum total weight.

Exercise: “AtCoder Beginner Contest 211. Problem E” Red Polyomino

Problem: Given an $N\times N$ grid whose cells are initially black or white, choose exactly $K$ white cells and paint them red. Count the colorings in which the red cells form one connected component.

Graph model

Example: “NOI 2007 Day 2” Counting spanning trees

Problem: Count spanning trees of a special graph in which every vertex is connected to exactly its previous $k$ vertices.

Example: “2015 ACM-ICPC Asia Shenyang Regional Contest - Problem E” Efficient Tree

Problem: Given an $N\times M$ grid graph and weights on edges between orthogonally adjacent cells. For a spanning tree, the score of each vertex is 1+[an upward edge]+[a leftward edge]. The score of a spanning tree is the product of the scores of all vertices.

Find the total edge weight of a minimum spanning tree and the sum of the scores of all minimum spanning trees. ( $n\le 800,m\le 7$ )

In practice

Example

Example: “HDU 4113” Construct the Great Wall

Problem: Construct a set of cycles inside an $N\times M$ board that separates all x and o cells.

Some plug-DP problems ask us to construct walls on a board to separate certain elements. We call these wall-construction problems; they can be viewed either as coloring models or as path models.

greatwall

If this problem is viewed as a coloring model, we must not only handle the perimeter of the colored regions but also reject configurations that touch at a corner (Figure 2). Unlike “UVa 10572” Black & White, this problem requires the wall to be a simple polygon, so the nested rectangular configuration below is invalid.

3 3
ooo
oxo
ooo

We therefore use the path model and reduce it to a single cycle.

Run DP along the grid intersections (so both dimensions increase by $1$ ). At each transition, ensure that every x lies outside the cycle and every o lies inside it. We must therefore track whether the current position is inside the cycle. This can be an extra dimension, or we can use the ray method and count the parity of the number of downward plugs encountered on the contour before the current position.

Example code

#include <cstring>
#include <iostream>
using namespace std;
#define REP(i, n) for (int i = 0; i < n; ++i)

template <class T>
bool checkMin(T &a, const T b) {
  return b < a ? a = b, true : false;
}

constexpr int N = 10, M = N;
constexpr int offset = 3, mask = (1 << offset) - 1;
int n, m;
int d;
constexpr int INF = 0x3f3f3f3f;
int b[M + 1], bb[M + 1];

int encode() {
  int s = 0;
  memset(bb, -1, sizeof(bb));
  int bn = 1;
  bb[0] = 0;
  for (int i = m; i >= 0; --i) {
#define bi bb[b[i]]
    if (!~bi) bi = bn++;
    s <<= offset;
    s |= bi;
  }
  return s;
}

void decode(int s) {
  REP(i, m + 1) {
    b[i] = s & mask;
    s >>= offset;
  }
}

constexpr int MaxSZ = 16796, Prime = 9973;

struct hashTable {
  int head[Prime], next[MaxSZ], sz;
  int state[MaxSZ];
  int key[MaxSZ];

  void clear() {
    sz = 0;
    memset(head, -1, sizeof(head));
  }

  void push(int s) {
    int x = s % Prime;
    for (int i = head[x]; ~i; i = next[i]) {
      if (state[i] == s) {
        checkMin(key[i], d);
        return;
      }
    }
    state[sz] = s, key[sz] = d;
    next[sz] = head[x];
    head[x] = sz++;
  }

  void roll() { REP(i, sz) state[i] <<= offset; }
} H[2], *H0, *H1;

char A[N + 1][M + 1];

void push(int i, int j, int dn, int rt) {
  b[j] = dn;
  b[j + 1] = rt;
  if (A[i][j] != '.') {
    bool bad = A[i][j] == 'o';
    REP(jj, j + 1) if (b[jj]) bad ^= 1;
    if (bad) return;
  }
  H1->push(encode());
}

int solve() {
  cin >> n >> m;
  int ti, tj;
  REP(i, n) {
    scanf("%s", A[i]);
    REP(j, m) if (A[i][j] == 'o') ti = i, tj = j;
    A[i][m] = '.';
  }
  REP(j, m + 1) A[n][j] = '.';
  ++n, ++m, ++ti, ++tj;
  H0 = H, H1 = H + 1;
  H1->clear();
  d = 0;
  H1->push(0);
  int z = INF;
  REP(i, n) {
    REP(j, m) {
      swap(H0, H1);
      H1->clear();
      REP(ii, H0->sz) {
        decode(H0->state[ii]);
        d = H0->key[ii] + 1;
        int lt = b[j], up = b[j + 1];
        bool dn = i != n - 1, rt = j != m - 1;
        if (lt && up) {
          if (lt == up) {
            int cnt = 0;
            REP(i, m + 1) if (b[i])++ cnt;
            if (cnt == 2 && i == ti && j == tj) {
              checkMin(z, d);
            }
          } else {
            REP(i, m + 1) if (b[i] == lt) b[i] = up;
            push(i, j, 0, 0);
          }
        } else if (lt || up) {
          int t = lt | up;
          if (dn) {
            push(i, j, t, 0);
          }
          if (rt) {
            push(i, j, 0, t);
          }
        } else {
          --d;
          push(i, j, 0, 0);
          ++d;
          if (dn && rt) {
            push(i, j, m, m);
          }
        }
      }
    }
    H1->roll();
  }
  if (z == INF) z = -1;
  return z;
}

int main() {
  int T;
  cin >> T;
  for (int Case = 1; Case <= T; ++Case) {
    printf("Case #%d: %d\n", Case, solve());
  }
}

Exercises

Exercise: “SCOI 2011” Floor

Problem: An $r\times c$ board contains blocked cells. Count the ways to cover every unblocked cell with L-shaped tiles.

Exercise: “HDU 4796” Winter's Coming

Problem: Color uncolored cells of an $N\times M$ board black, white, or gray. Require the black and white regions to be connected, each to connect to the corresponding top or bottom boundary, and black and white regions not to be adjacent. Each cell has a cost; find a coloring minimizing the cost of the gray region.

4796

Exercise: “ZOJ 2125” Rocket Mania

Problem: Each cell of a $9\times6$ map contains a pipe (-,T,L,+, or empty). Pipes may be rotated by 0°, 90°, 180°, or 270°. Find the maximum number of rows whose right boundary is connected through pipes to the left boundary of row X.

Exercise: “ZOJ 2126” Rocket Mania Plus

Problem: Each cell of a $9\times6$ map contains a pipe (-,T,L,+, or empty), rotatable by 0°, 90°, 180°, or 270°. Find the maximum number of rows whose right boundary is connected through pipes to the left boundary.

Exercise: “World Finals 2009/2010 Harbin” Channel

Problem: In a grid map, . denotes empty ground and # denotes rock. Find the longest path such that:

The start is the upper-left corner and the end is the lower-right corner.
The path does not pass through rocks.
The path does not form a cycle under 8-connectivity (it may not touch itself even at corners).

Exercise: “HDU 3958” Tower Defence

Problem: This can be reduced to finding the longest non-touching path from $\mathit{S}$ to $\mathit{T}$ ; touching at corners is allowed.

Exercise: “UVa 10531” Maze Statistics

Problem: In an $N\times M$ grid, each cell independently becomes an obstacle with probability $\mathit{p}$ . Starting at the upper-left corner, reach the lower-right corner. Find the probability that each cell is an obstacle in a solvable maze (that is, the start and end are 4-connected). ( $N \le 5$ , $M \le 6$ )

Exercise: “Aizu 2452” Pipeline Plans

Problem: There are 12 types of patterned tiles, with the quantity of each type given. Tile an $R\times C$ rectangular floor, viewed as a grid graph, with one tile per cell, so that the centers of the upper-left and lower-right cells are connected by lines in the tile patterns. $(2 \le R \times C \le 15)$

plug2

Exercise: “SDOI 2014” Circuit Board

Problem: An $N\times M$ circuit board has blocked cells through which wires cannot pass. Given $K$ pairs of cells, connect every pair by wires with no crossings; a wire may enter the current cell from the top and leave through the left, while another may enter from the bottom and leave through the right. Treat wires as undirected edges; find the minimum total wire length and the number of solutions.

Exercise: “SPOJ CAKE3” Delicious Cake

Problem: A cake viewed as an $N\times M$ grid is cut along grid lines into pieces. Count distinct cuts, where two cuts are the same exactly when all pieces have the same shapes in the same positions. ( $\min(N,M) \le 5, \max(N,M) \le 130$ )

Notes on this chapter

Plug-DP problems are usually difficult to encode and discuss, so they are a relatively specialized topic in OI and ACM. The classic reference is Chen Danqi's 2008 training-team paper Dynamic Programming Based on Connectivity State Compression and its mirror. Another valuable resource is the pair of introductory-to-advanced articles that notonlysuccess wrote on his blog in 2011, though they now require archaeological work in the Web Archive.

Domino tiling

“HDU 1400” Mondriaan’s Dream also appears in A Guide to Competitive Programming as an example in the “Dynamic Programming on a Contour” section. Domino tiling is a classic family of mathematical problems; changing the limits produces variants of different difficulty that require different algorithms.

When $m=2$ , domino tiling is equivalent to the Fibonacci sequence. Concrete Mathematics uses this problem to introduce Fibonacci numbers and derives their closed form in several ways.

When $m\le 10,n\le 10^9$ , preprocess the transition into matrix form and use matrix multiplication for acceleration.

domino_v2_transform_matrix

When $n,m\le 100$ , the number of perfect matchings of the corresponding planar graph can be computed with the FKT Algorithm.

A single path

“A single path” is a special case of the Hamiltonian Path problem on a Grid Graph. The decision problem for Hamiltonian paths is an important member of the NP-complete family.

Plug DP

Definition

Introduction

Domino Tiling and Profile DP

Terminology

Path Model

Multiple Cycles

Examples

Exercises

A Single Cycle

Examples

State Encoding

Handwritten Hash

State Transitions

Exercises

A Single Path

Examples

State Transitions

Exercises

Coloring Model

Example “UVa 10572” Black & White

State Encoding

Handwritten Hash

Solution Construction

State Transitions

Exercises

Graph model

In practice

Example

Exercises

Notes on this chapter

Domino tiling

A single path