Arrange the Bulls (POJ 2441)

We use state compressed dynamic programming method to solve this problem. To compress the barn occupying state, we use an int integer in which a bit position is 1 if that position is free. Then we start from the first cow and every time we get the number of ways to arrange the first i cows. When it comes the next cow, we try to calculate the total number of ways for adding this cow into previous state.

Let $DP[i][state]$ stands we the number of ways for every barn occupying state if have arranged i cows. Then:

$$DP[i + 1][a] = \sum_{a \& b \neq 0} DP[i][b]$$

Where b stands for every state representing that if we put this cow to one of its desired barn. Note that as to pass the test we have to reduced the dynamic programming matrix to two rows when implementing the solution.

import java.io.*;
import java.util.*;

public class ArrangeTheBulls {
    private static void solve(int N, int M, int[] bulls) {
        int[] dplast = new int[1 << M];
        int[] dpcur = new int[1 << M];
        int W = (1 << M) - 1;

        dplast[W] = 1;
        for (int i = 1; i <= N; i++) {
            int bull = bulls[i - 1];
            for (int j = W; j > 0; j--) {
                if (dplast[j] == 0) continue;

                int mask = j & bull;
                while (mask > 0) {
                    dpcur[j & ~(mask & -mask)] += dplast[j];
                    mask &= mask - 1;
                }
            }

            int[] tmp = dplast;
            dplast = dpcur;
            dpcur = tmp;
            Arrays.fill(dpcur, 0);
        }
        int res = 0;
        for (int i = 0; i <= W; i++) {
            res += dplast[i];
        }
        System.out.println(res);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int N = in.nextInt(), M = in.nextInt();
            int[] bulls = new int[N];
            for (int i = 0; i < N; i++) {
                int P = in.nextInt();
                for (int j = 0; j < P; j++) {
                    int b = in.nextInt() - 1;
                    bulls[i] |= (1 << b);
                }
            }

            solve(N, M, bulls);
        }
    }
}