USACO NOV08 Problem 'auction' Analysis

by Rob Kolstad

The goal is to maximize the total revenue of haybales sold -- bestrevenue = bestprice * nbuyers. In case of ties, we want the smallest bestprice (which presumably has a larger nbuyers).

The general approach is brute force: for each price, calculate the total revenue -- and choose the largest revenue from the lot. The simplest approach would be:

    maxrevenue = 0;
    for (price = 1; price <= 1000000; price++) {
                                        /* check all prices */
        nbuyers = 0;
        for (i = 0; i < M; i++) {
                                        /* check all farmers */
            if (farmer i's limit >= price) nbuyers++;
                                        /* count farmer if price is OK */
        }
        if (nbuyers > N) nbuyers = N;   /* have only N bales to sell */
        totalrevenue = nbuyers * price;
        if (totalrevenue > maxrevenue) {
                                        /* remember best revenue, price */
            maxrevenue = totalrevenue;
            bestprice = price;
        }
    }

The program above has a problem -- the two nested loops require 1,000,000 * M trips through the farmer-checking statement. Since M can be 1,000, that might make for one billion trips -- too many to solve in 1 cpu second (which can generally do a one to a few hundred million simple operations).

There is no need, however, to check all the prices. Suppose four farmers are willing to pay these prices: {2, 4, 6, 900}. We need only check those values for the haybale, since a farmer who will pay 5 for a haybale will pay 6 or 900. There's no reason to check 7, 8, 10, ..., 898, 899 since we know farmer 4 will pay even more.

This yields a much faster program:

    maxrevenue = 0;
    for (j = 0; j < N; j++) {
        price = farmer (j+1)'s limit;   /* check all reasonable prices */
        nbuyers = 0;
        for (i = 0; i < M; i++) {
                                        /* check all farmers */
            if (farmer (i+1)'s limit >= price) nbuyers++;
                                        /* count farmer if price is OK */
        }
        if (nbuyers > N) nbuyers = N;   /* have only N bales to sell */
        totalrevenue = nbuyers * price;
        if (totalrevenue > maxrevenue) {
                                        /* remember best revenue, price */
            maxrevenue = totalrevenue;
            bestprice = price;
        }
    }

And, indeed, this program makes only N*M trips through the innermost loop (max N*M = 1,000,000) -- 1,000 times faster than the previous program.

Can we do better?

The inner loop compares each farmer's limit to the price -- and checks every farmer's limit every time we get a new price. If the list of farmer's price limits were sorted, we could just advance through that list with a counter that told us how many farmers' limits were smaller than the current limit! By paying an extra sorting cost of O(N log N) up front, we reduce the number of checks to N for a total runtime of N + NlogN (vs. the old (M*M) and (N*M) from the previous two examples). Numerically, since the logs in this approach are known to be log base 2, this shows a dramatic speedup at the largest limits of the program:

Choosing a better algorithm results in a speed of up about ~100,000x!

The example below illustrates this speedy approach:

#include <stdio.h>
#include <stdlib.h>

int compare (a, b) int *a, *b; { return *b - *a; }

int price[1000];

main () {
    FILE *fin = fopen ("auction.in", "r");
    FILE *fout = fopen ("auction.out", "w");
    int n, m, i, sum, maxrevenue, p, thisprice, bestprice, nbuyers;

    fscanf (fin, "%d %d", &n, &m);
    for (i = 0; i < m; i++)
        fscanf (fin, "%d", &price[i]);
    qsort(price, m, sizeof(int), compare);
    /*for (i = 0; i < m; i++) printf(">%d\n", price[i]);*/

    bestprice = price[0];
    maxrevenue = price[0];
    for (p = 0; p < m; p++) {
        thisprice = price[p];
        nbuyers = p+1;
        if (nbuyers > n) nbuyers = n;
        sum = nbuyers * thisprice;
        if (sum > maxrevenue) {
            maxrevenue = sum;
            bestprice = thisprice;
        }
    }
    fprintf (fout, "%d %d\n", bestprice, maxrevenue);
    exit (0);
}