USACO DEC08 Problem 'patheads' Analysis

by Neal Wu

The simplest solution to this problem would be to loop over every pair of cows, counting the number of pats as we go. However, for N <= 100,000, the number of operations performed could be up to 100,000 * 100,000 = 10 billion, which is far too many!

Since the maximum number a cow can have is 1,000,000, we can instead use an algorithm similar to a sieve on an array of size 1,000,000 to keep track of the number of pats that occur, as in the following solution:

#include <cstdio>
using namespace std;

FILE *in = fopen ("patheads.in", "r"), *out = fopen ("patheads.out", "w");

const int MAXN = 100005, MAXA = 1000005;

int N, A [MAXN], occur [MAXA], pat [MAXA];

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

    for (int i = 0; i < N; i++) {
        fscanf (in, "%d", A + i);
        occur [A [i]]++;
    }

    for (int i = 1; i < MAXA; i++)
        if (occur [i] > 0)
            for (int j = i; j < MAXA; j += i)
                pat [j] += occur [i];

    for (int i = 0; i < N; i++)
        fprintf (out, "%d\n", pat [A [i]] - 1);

    return 0;
}