Can someone explain the O(2^N * NM) solution for the "Parquet" problem? (DP on Broken Profile)

Problems and Contests
#1

The well-known Parquet Problem asks the following: Given an N x M board, find the number of ways to tile it using only 1 x 2 or 2 x 1 tiles. I’m interested in the DP approach that calculates the answer in O(2^N * NM), as shown on this USACO Guide page, but I can’t understand the DP state that is used.

My understanding of their DP-state is that dp[i][j][mask] = the number of ways to tile the grid so that basically columns 0 to j−2 are all completely filled. Meanwhile, column j−1 may not be completely filled, but must be filled from rows 0 to ii. And mask represents whether or not rows 0 to i in column j, and rows i+1 to N−1 in column j−1, are filled.

Here’s the explanation that appears on the USACO Guide article:

image
image768×377 82.6 KB

(For the 3rd bullet point, I think the k-th bit should correspond to the k-th row, not the k-th column. Additionally, I think the bitmask should be reversed, because 1 << i represents row i, so if we go from the top row to the bottom we should actually be reading 10100_2 backwards I think)

This explanation fits with the picture. But, when I actually run the provided program, I get DP-values that don’t seem to agree with my understanding. Mainly, I don’t understand what the DP-state means conceptually when j=0 . For instance, one value we get is that dp[1][0][0011]=1. Based on my understanding, this basically represents the number of ways to tile only the leftmost-column, and only the bottommost two cells, so 1 does make sense here.

But if we look further, we see that dp[1][0][1100]=0, not 1! Shouldn’t this just equal 1 as well, since it represents the number of ways to tile only the top two squares of the leftmost column?

Overall, I feel that my current confusion stems from an overall misunderstanding of the DP state used. If someone could give an explanation of the DP-state, I would greatly appreciate it!

1 Like
#2

You’re right about both of these. 10100 actually refers to the DP state 2^0+2^2.

dp[i][0][k], where k<2^i, corresponds to only considering cells (0,0) through (i,0), and leaving the cell (i',0) empty if the i'-th bit of k is set. When k\ge 2^i, dp[i][0][k]=0.

For example, for (i,j)=(1,0), we have dp[i][j][0000_2]=1, corresponding to leaving neither of (0,0) and (1,0) empty, and dp[i][j][0011_2]=1, corresponding to leaving both of (0,0) and (1,0) empty. Does that answer your question?

Your understanding seems correct for the most part. Though I’m not sure why you are expecting dp[1][0][1100_2] to equal 1.

(relevant code)

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int dp[1 << 10][2];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	dp[0][0] = 1;
	for (int j = 0; j < m; j++) for (int i = 0; i < n; i++) {
		for (int mask = 0; mask < (1 << n); mask++) {
			dp[mask][1] = dp[mask ^ (1 << i)][0]; // Vertical/no tile
			if (i && !(mask & (1 << i)) && !(mask & (1 << i - 1))) // Horizontal tile
				dp[mask][1] += dp[mask ^ (1 << i - 1)][0];

			if (dp[mask][1] >= MOD) dp[mask][1] -= MOD;
		}
		if (i == 1 && j == 0) {
			for (int mask = 0; mask < (1 << n); mask++) {
				cout << mask << " " << dp[mask][1] << "\n";
			}
			exit(0);
		}
		for (int mask = 0; mask < (1 << n); mask++) dp[mask][0] = dp[mask][1];
	}
	cout << dp[0][0];
	return 0;
}
dp[1][0][0] = 1
dp[1][0][1] = 0
dp[1][0][2] = 0
dp[1][0][3] = 1
dp[1][0][4] = 0
dp[1][0][5] = 0
dp[1][0][6] = 0
dp[1][0][7] = 0
dp[1][0][8] = 0
dp[1][0][9] = 0
dp[1][0][10] = 0
dp[1][0][11] = 0
dp[1][0][12] = 0
dp[1][0][13] = 0
dp[1][0][14] = 0
dp[1][0][15] = 0
#3

By the way, I opened a PR fixing the issues you mentioned:

Let me know if anything else should be changed.