USACO FEB09 Problem 'bullcow' Analysis

by Neal Wu

The solution to this problem uses a technique called dynamic programming, also known as DP. Let f_n be the number of ways we can have a sequence of n animals so that no two bulls have fewer than K cows between them. We first note that f₀ = 1. We then try to find a recurrence to compute f_n in general by considering two cases for the first animal in the sequence:

• If it is a cow, then we have no restrictions on how we may place the other n - 1 animals, so we have f_{n - 1} ways to finish the sequence.
• If it is a bull, then the next K animals must be cows, but after that we have no more restrictions, so the number of ways to finish the sequence is f_{n - K - 1}. (Note that when n < 0, we define f_n to be 1.)

Thus, combining our two cases together, we have the recurrence f_n = f_{n - 1} + f_{n - K - 1}. This gives us a simple solution:

#include <cstdio>
using namespace std;

FILE *fin = fopen ("bullcow.in", "r"), *fout = fopen ("bullcow.out", "w");

const int MAXN = 100005, MOD = 5000011;

int N, K, dp [MAXN];

int main ()
{
    fscanf (fin, "%d %d", &N, &K);

    for (int n = 0; n <= N; n++)
        if (n <= K)
            dp [n] = n + 1;
        else
            dp [n] = (dp [n - 1] + dp [n - K - 1]) % MOD;

    fprintf (fout, "%d\n", dp [N]);

    return 0;
}