USACO NOV08 Problem 'mixup2' Analysis

by Spencer Liang

This problem is solved with dynamic programming. The state space is (T, i) where T is a set of cows and i is the index of a cow in T. Let f(T, i) represent the number of "Mixed Up" sequences using the cows in T such that the last cow in every sequence is i. Then f(T, i) equals the sum of f(T-i, k) over all k such that k is in T-i and |S[k]-S[i]| > K. This follows from the observation that the only restrictions on the index of the final cow in a "Mixed Up" sequence come from the index of the second-to-last cow in the sequence.

To implement this algorithm, use a bitmask b of length N to represent T: the i-th bit of b is set if and only if the cow with index i is in T. Then testing to see if cow i is in T is equivalent to testing if (b&(1<<i) == 1), and adding cow i to T is equivalent to (b = b|(1<<i)). There are O(2NN) states, each taking O(N) time to solve, for a total running time of O(2NN2).

/*
LANG: C++
*/

#include <stdio.h>
#include <iostream>
#define MAX 16
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
typedef long long LL;

int S[MAX];
LL ways[1<<MAX][MAX];

int main() {
    FILE *fin = fopen("mixup2.in", "r"), *fout = fopen("mixup2.out", "w");
    int N, K; fscanf(fin, "%d %d", &N, &K);
    REP(i, N) fscanf(fin, "%d", &S[i]);
    REP(last, N) ways[1<<last][last] = 1;

    REP(mask, 1<<N) REP(last, N) if (mask&(1<<last))
        REP(next, N) if ((mask&(1<<next)) == 0 && abs(S[next]-S[last]) > K)
            ways[mask|(1<<next)][next] += ways[mask][last];

    LL res = 0; REP(last, N) res += ways[(1<<N)-1][last];
    fprintf(fout, "%lld\n", res);
    return 0;
}