USACO NOV06 Problem 'cowfood' Analysis

by Richard Peng

This problem is a classical state compression DP problem. Since the forbidden component has length 2, only the configuration of the previous row and determines whether the current row is valid. There are 2^n, which is worst case 4096 possible configurations per each row (the total is much lower as no two neighboring grids on the same row can both be planted) and its possible to transfer from one row to another if and only if there does not exist a column where both rows have occupied squares. Clever usage of bit operators can help reduce the amount of code.

The runtime of the code is O(2^(2n)*n) although in practice it's much less. In the original version of the problem, the exact result rather than the answer mod 10^8 was required, which would have made the problem a bit more difficult to code.
Code (by Bruce Merry):


#include <fstream>
#include <algorithm>
#include <vector>
#include <iterator>

using namespace std;

#define MAXR 12
#define MAXC 12
#define MAX2C (1 << MAXC)
#define MOD 100000000

int main() {
    ifstream in("cowfood.in");
    ofstream out("cowfood.out");
    int infertile[MAXR + 1] = {0};
    int dp[MAXR + 1][MAX2C];
    int R, C, C2;
    vector<int> valid;

    in >> R >> C;
    C2 = 1 << C;
    fill(infertile, infertile + R, 0);
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++) {
            int x;
            in >> x;
            if (!x) infertile[i + 1] |= 1 << j;
        }

    for (int i = 0; i < C2; i++)
        if (!(i & (i << 1))) valid.push_back(i);

    fill(dp[0], dp[0] + C2, 1);
    for (int i = 1; i <= R; i++) {
        fill(dp[i], dp[i] + C2, 0);
        for (int j = 0; j < C2; j++) {
            if (~j & infertile[i]) continue;
            for (size_t k = 0; k < valid.size(); k++) {
                int u = valid[k];
                if (u & j) continue;
                dp[i][j] += dp[i - 1][u | infertile[i - 1]];
                dp[i][j] %= MOD;
            }
        }
    }

    out << dp[R][infertile[R]] << "\n";
    return 0;
}