(Broken) Profile Dynamic Programming

Publish Date

April 28, 2024

There's a simple floor with a $N \times M$ grid in Bob's house. He owns some pet snakes that like to pretend they are ouroboros. That is, they bite their own tails, creating a circular pattern. There are some electric outlets installed onto the ground, so snakes have to avoid them. Bob wants you to find the number of the combinations of his snakes occupying all the tiles of his floor.

- a228, Zero Judge

We can't brute-force this problem due to its complexity; thus, we need something else.

Applicable Context

For broken profile DP to be usable, the context must satisfy the followings

1. Low dimension state space
2. Low state enumeration (one to two bit)
3. State has to be dependent only on adjacent units

Breaking the Problem Down

To solve this problem, we can think of smaller sub problems that can be solved more easily. First of all, we need to find states that depend on previous ones to create a bottom-up solution. Since this is a 2D grid, we can think of it as scanning through the grid column by column. We represent the state space with $DP[i][j][s]$ where $i, j$ are the coordinates of our current target for the snakes to go through and $s$ is an integer (profile) whose $y$-th bit represents whether there's a snake coming through it. To understand this, please take a look at the image below. The $P$ and $Q$ are respectively previous and next profiles. Think of them as borders of truth. Everything before $P$ has to be filled with snakes, and everything before $Q$ will be filled with snakes. Now, our task is to transform $P$ into $Q$.

While phrased like we use $P$ to deduce $Q$, due to the nature of iterative solutions, we need to do the opposite.

State Transition

In DP, sometimes you have to manipulate the indices themselves. We want to see how to transform the current profile to the next profile when we fill our current block with a snake. In this chapter, we'll focus on all the possible cases. We'll call a snake coming through a profile's certain unit "penetration."

Black lines represent the current penetration, whereas blue lines represent the possible penetration.

Outlet

This is the most straightforward one. If $Q[j+1]=Q[j]=0$, meaning there are no snakes coming through outlets, the configuration is valid; therefore, it directly inherits the possibility from the previous state. Otherwise, it would be invalid and set to zero.

$P = Q$ $DP[i][j][Q] = DP[i][j-1][P]$

No Penetration

If no snakes will come through ($Q[j+1] = Q[j] = 0$), it means we must have an L-shaped penetration of the same snake.

$P=Q + 2^j + 2^{j+1}$

$DP[i][j][Q] = DP[i][j-1][P]$

L-shaped Penetration

If a snake will come through both sides ($Q[j+1] = Q[j] = 1$), it means no penetration should occur previously.

$P = Q - 2^j - 2^{j+1}$

$DP[i][j][Q] = DP[i][j-1][P]$

Single Penetration

This part is a little bit more complex, but overall trivial. If there will only be one coming through ($Q[j+1] \oplus Q[j] = 1$), it means there has to be one penetration in the previous state. Notice that there can be two possibilities, so we need to add them up.

$P_1 = Q, P_2 = Q \oplus (2^{j} + 2^{j + 1})$

$DP[i][j][Q] = DP[i][j-1][P_1] + DP[i][j-1][P_2]$

Implementation in C

Here you go with some comments.

/**
 * 就少一個插座很不方便
 * 插頭DP
 */

#include <stdio.h>
#include <string.h>

#define MODULO 1000000007U

unsigned int n, m;
unsigned int map[12][12];
unsigned int combs[12][12][1 << 12];

unsigned int solve()
{
    memset(combs, 0, sizeof(combs));

    combs[0][m][0] = 1;
    // set the basic step
    // non-existent block (0, m) with blank state (zero plugs) has one solution

    for (size_t i = 1; i <= n; i++)
    {
        for (size_t s = 0; s < (size_t)(1 << m); s++)
        {
            combs[i][0][s << 1] = combs[i - 1][m][s];
            // copy from last column's accumulated solutions
            // we only copy s till 1 << m because one byte has
            // to be open (the first part is always non-plugged)
        }

        for (size_t j = 1; j <= m; j++)
        {
            // get snake penetration in s (this part is confusing)
            size_t up = 1 << (j - 1);
            size_t left = 1 << (j + 1 - 1);
            // in the blog post, the bits are a 1-based array, but in real programming, it is 0-based
            // combined with our 1-based array for i,j, we get a 1-off problem, so need to minus one.
            for (size_t s = 0; s < (size_t)(1 << (m + 1)); s++)
            {
                if (map[i][j]) // safe, doesn't have outlet
                {
                    if ((up & s) && (left & s))
                    {
                        // two plugs, transfer from no plugs
                        combs[i][j][s] = combs[i][j - 1][s - up - left];
                    }
                    else if ((up & s) || (left & s))
                    {
                        // one of them up or left (exclusive or)
                        combs[i][j][s] = (combs[i][j - 1][s] + combs[i][j - 1][s ^ (up | left)]) % MODULO;
                        // s ^ (up | left)
                        // if the state has up, then we choose the state with left
                        // if the state has left, then we choose the state with up
                        // add the original solutions as well
                        // (remember the s does not represent the same thing in the last (i, j-1) tile!!!)
                    }
                    else
                    { // zero plugs
                        combs[i][j][s] = combs[i][j - 1][s + up + left];
                        // just add the one with plugs (make it valid)
                    }
                }
                else // outlet
                {
                    if (!(up & s) && !(left & s))
                    {
                        // valid config for outlet (zero plug)
                        combs[i][j][s] = combs[i][j - 1][s];
                    }
                    else
                    {
                        // invalid config, 0 ways
                        // no way there are plugs coming out of outlets smh
                        combs[i][j][s] = 0;
                    }
                }
            }
        }
    }
    // final accumulation happens at combs[n][m][0]

    return combs[n][m][0] % MODULO;
}

int main()
{
    unsigned int C;
    scanf("%u", &C);
    for (unsigned int i = 1; i <= C; i++)
    {
        scanf("%u %u", &n, &m);
        for (size_t i = 1; i <= n; i++)
            for (size_t j = 1; j <= m; j++)
                scanf("%u", &map[i][j]);

        printf("Case %u: %u\n", i, solve());
    }
    return 0;
}

References

• Example Problem: https://zerojudge.tw/ShowProblem?problemid=a228
• USACO Broken Profile DP: https://usaco.guide/adv/dp-more?lang=cpp#dp-on-broken-profile
• Awesome Video: https://youtu.be/0bnMHlFUM_o