Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

4fecta's blog

By 4fecta, history, 4 years ago, In English

So I realized that there are literally 0 resources written in English on Plug DP, which is one of my favourite DP tricks/techniques that I know of so far. Thus, I hope this serves as a soft introduction for English speakers to this technique, and maybe sheds some light on how powerful it can be. Before we start, I would recommend having a solid understanding of bitmask DP in general in order to get the most out of this blog. Now, let's begin.

What is Plug DP?

In short, Plug DP is a bitmasking technique that allows us to solve complicated problems with relatively simple states and transitions. To illustrate Plug DP in its most primitive form, let's visit a rather classical problem: How many ways can we fully tile an $$$N \times M$$$ grid with $$$1 \times 2$$$ dominoes?

This problem can be solved with a standard row-by-row bitmasking approach, but the transitions for that DP state is annoying and unclear at best. Instead, let's investigate an approach that uses a slightly different state. Our state, $$$dp[i][j][mask]$$$, will represent the number of possible full tilings of all cells in rows $$$i-1$$$ and earlier, and the first $$$j$$$ cells in row $$$i$$$, with a plug mask of $$$mask$$$. The first two dimensions are relatively straightforward, but what do I mean by "plug mask"?

The Plug Mask

Let's consider a concrete example to understand the concept of plug masks. Consider the diagram above, where the first two dimensions $$$(i, j) = (3, 4)$$$. The red line denotes the line which separates the cells we've already processed and the cells we have yet to consider. This line can be split into $$$M+1$$$ segments of length 1, and each of the arrows on these segments represent a plug. The plug itself can represent a variety of things, but for our purposes here it represents whether we have placed a domino that crosses the plug (i.e. the two halves of the domino lie on separate sides of the plug). The plug will be $$$1$$$ (toggled) if there is a domino laid over it, and $$$0$$$ otherwise. For example, the diagram below depicts one of the tilings that has the plugs with states $$$[1, 0, 1, 0, 1, 0, 0, 1, 0]$$$ from left to right. We can obviously represent the set of states of the plugs using a bitmask of length $$$M+1$$$, so the DP state which the tiling below belongs to is $$$dp[3][4][101010010_2]$$$ (I've written the binary number in reverse here for readability. Just to be clear, the decimal equivalent of this mask is $$$149$$$ and not $$$338$$$).

Transitions

In general, we want to transition from cell $$$(i, j - 1)$$$ to cell $$$(i, j)$$$ (i.e. across each row). Notice that only 2 plugs change locations when we move horizontally, which is the main reason why Plug DP ends up being so powerful. If we number the plugs from $$$0$$$ to $$$M$$$, then only plugs $$$j-1$$$ and $$$j$$$ change locations. Specifically, $$$j-1$$$ goes from the vertical plug in the previous state to a horizontal plug in the next, while $$$j$$$ goes from a horizontal plug to the vertical plug. For example, the diagram below depicts the differences between the set of plugs for a state at $$$(3, 3)$$$ versus the set of plugs for a state at $$$(3, 4)$$$. The orange plugs are all shared and do not change during the transition, so we only need to consider how plugs $$$3$$$ and $$$4$$$ change in our transition from $$$(3, 3)$$$ to $$$(3, 4)$$$. It is convenient to note that if we $$$1$$$-index the columns and $$$0$$$-index the plugs, then plug $$$j$$$ will always be the vertical plug when considering a state at column $$$j$$$.

So how do we transition? First, we notice that if both plugs $$$j-1$$$ and $$$j$$$ are toggled from the previous state then it leads to an overlap of 2 dominoes on cell $$$(i, j)$$$, so we don't need to consider this case. Let's handle the other 3 cases separately.

Case 1: none of plugs $$$j-1$$$ and $$$j$$$ are toggled.

This means that $$$(i, j)$$$ does not have anything covering it, so we must place one end of a domino there to cover. We can either place a horizontal domino going from $$$(i, j)$$$ to $$$(i, j+1)$$$ toggling plug $$$j$$$, or we can place a vertical domino going from $$$(i, j)$$$ to $$$(i+1, j)$$$ toggling plug $$$j-1$$$. Note that we cannot place a domino going to $$$(i, j-1)$$$ or $$$(i-1, j)$$$ since these cells are already occupied by the definition of our state.

Case 2: only plug $$$j-1$$$ is toggled.

This means that $$$(i, j)$$$ is already covered (by a domino going from $$$(i, j-1)$$$ to $$$(i, j)$$$), so all we have to do is untoggle plug $$$j-1$$$ and move on.

Case 3: only plug $$$j$$$ is toggled.

Extemely similar to the previous case, This means that $$$(i, j)$$$ is already covered (by a domino going from $$$(i-1, j)$$$ to $$$(i, j)$$$), so all we have to do is untoggle plug $$$j$$$ and move on.

And that's really all there is! Now we just need to handle some special procedures and we are good to go.

Going from row $$$i-1$$$ to row $$$i$$$

If you've been following along, you may be wondering how we go from one row to the next. It turns out that all we need to do is move some values from one place to another. Specifically, when we first process row $$$i$$$, we will transfer all the values stored in $$$dp[i - 1][M][mask]$$$ to $$$dp[i][0][mask « 1]$$$. It may be confusing as to why we are shifting all bits to the left by 1, but the following diagram should clear things up.

As you may notice, the vertical plug $$$0$$$ on the next row shifts all the plug indices by 1, so we must shift all bits in the mask by 1 to compensate. Also, the vertical plugs here $$$0$$$ and $$$M$$$ should never be toggled since having a domino go outside the grid would be absurd, so we don't have to worry about the bit we lose from shifting or the new bit introduced.

Final details

Our base case will be $$$dp[0][M][0] = 1$$$, and you can see how this easily fits in from the previous section. The final answer will be stored in $$$dp[N][M][0]$$$, since having any plugs toggled at that point would mean having a domino go outside of the grid.

Implementation

Here, you can find my implementation for the procedure described above. I take all values modulo MOD since the number of tilings grows rapidly for larger $$$N$$$ and $$$M$$$. The time complexity is $$$\mathcal{O}(NM2^{M+1})$$$, which means we can solve the problem for $$$N, M \le 20$$$ with ease.

cin >> n >> m;
int full = (1 << (m + 1)) - 1; //the maximum possible mask with all m+1 bits set
dp[0][m][0] = 1; //base case
for (int i = 1; i <= n; i++) {
    for (int msk = 0; msk <= full; msk++) dp[i][0][msk << 1] += dp[i - 1][m][msk]; //transfer data from row i-1 to i
    for (int j = 1; j <= m; j++) {
        for (int msk = 0; msk <= full; msk++) {
            int rit = msk & (1 << (j - 1)), dwn = msk & (1 << j); //right and down plug from (i, j-1) respectively
            if (!rit && !dwn) { //case 1
                dp[i][j][msk ^ (1 << j)] += dp[i][j - 1][msk] % MOD; //place right domino
                dp[i][j][msk ^ (1 << (j - 1))] += dp[i][j - 1][msk] % MOD; //place down domino
            } else if (rit && !dwn) dp[i][j][msk ^ (1 << (j - 1))] += dp[i][j - 1][msk] % MOD; //case 2
            else if (!rit && dwn) dp[i][j][msk ^ (1 << j)] += dp[i][j - 1][msk] % MOD; //case 3
        }
    }
}
printf("%d\n", dp[n][m][0] % MOD); //final answer

Closing Remarks

And that was a quick overview of Plug DP! With a firm grasp on the concepts we can easily extend this to a variety of other small grid problems, whether it be about domino tilings or counting circuits in a grid. As a small exercise, try solving the problem above when some of the given cells are blocked, or try solving it for when it does not have to be a full tiling. For extra practice, there are a plethora of practice problems given here: https://oi-wiki.org/dp/plug/ (the site is written in Chinese, but the problems are in English)

  • Vote: I like it
  • +428
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +79 Vote: I do not like it

It's also known as DP on Broken Profile.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Thanks for finding this, it seems like we are describing similar techniques here. One distinction is that the article there describes a technique where the mask stores the state of the last $$$M$$$ cells (covered or not), whereas the mask here stores the state of the plug mask (red line). It's definitely a good idea to be familiar with both techniques though, so that it boils down to choosing whichever one is more appropriate for the task at hand.

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Great tutorial! I have wanted to learn about this dp technique for a while now. Finally got to doing it!

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

orz

»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, this is exactly the problem we solved in the blog, so it's perfect for practice. If anyone is interested, I've linked an accepted source code here, which is just the code given in the blog but with variables declared and MOD handled more precisely (I also read in $$$M$$$ before $$$N$$$ so that the complexity becomes $$$\mathcal{O}(MN2^{N+1})$$$).

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i just solved it 2 days ago , found it pretty awesome.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice blog. But shouldn't this line produce a segmentation fault?

for (int msk = 0; msk <= full; msk++) dp[i][0][msk << 1] += dp[i - 1][m][msk]; //transfer data from row i-1 to i

specifically, when msk==full, msk<<1 equals to 2*full which is out of range.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You are right, this is why I usually declare the last dimension to be a little larger than necessary as an accommodation for that (you may refer to the code I linked above this comment as an example).

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, I see. Those states don't matter. Thanks!

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Know this is old, but didn't realize this technique had a name. A good example problem is USACO 2019 Open — Compound Escape.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I follow the to read the problem in https://oi-wiki.org/dp/plug/ . However, I still do not understand the idea for the explanation (I tried to google translate) for "「Andrew Stankevich Contest 16 — Problem F」Pipe Layout". Could anyone help me to explain the approach to that problem? How does the state present, what does encode and decode do?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If we were allowed to have multiple circuits on the board, then the solution could be adapted quite similarly from the code for dominoes presented in the blog — the state is still a bitmask where a bit in the plug mask is set if and only if a pipe is laid over the plug. The only difference is that we need to consider more cases for each of the six different types of blocks during transitions.

    However, the requirement of all the pipes being connected presents us a challenge. Now, we also need to pay attention that all of the incomplete paths of pipes are joined together in one big circuit when we finish running our algorithm. In order to do this, we must maintain which plugs are part of the same connected component in our plug mask. This means that our array can't just be a binary array like before. Instead, we need an array of integers, where $$$0$$$ represents that no pipe crosses the plug and any pair of identical positive integers represents two ends of the same connected component. For example, the array of plug states $$$[5, 0, 3, 8, 8, 5, 3]$$$ represents that plugs $$$0$$$ and $$$5$$$ are part of the same component, plugs $$$2$$$ and $$$6$$$ are part of the same component, plugs $$$3$$$ and $$$4$$$ are part of the same component, and plug $$$1$$$ doesn't have a pipe crossing it.

    This is great and all, but there is still an issue: two arrays may represent the exact same state. For example, $$$[2, 0, 6, 5, 5, 2, 6]$$$ represents the exact same state as the array presented in the previous paragraph. To avoid this issue, we must assign the positive integers of the array such that it is always the lexicographically smallest possible array that represents the state. For example, the array representing the state above should be $$$[1, 0, 2, 3, 3, 1, 2]$$$. In this way, we guarantee that each possible state has a unique array that represents it, and we avoid overcounting the answer.

    It still remains to find an efficient way to store this array. One may notice that the maximum possible number of components at any point is not large due to the tiny constraints on the grid. So, we can still use a bitmask, except we allocate blocks of $$$3$$$ bits to represent each number of the array. For example, the binary number $$$010\,001\;011\;011\;010\;000\;001$$$ can be used to represent the array $$$[1, 0, 2, 3, 3, 1, 2]$$$. The encode function in the wiki page simply converts an array to binary, and decode does the exact opposite. Now that we have a way to properly represent the state again, the transitions shouldn't be much different from before. We only need to take care that we don't complete any circuits until the very last cell.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in the second figure, shouldn't the mask is 101011010? because the 4th and 5th bit is being occupied by the same domino?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How do you determine the shape of the red line? Or is it always in that horizontal-up-horizontal shape?