USACO FEB09 Problem 'shuttle' Analysis

by Bruce Merry

Clearly, any brute-force solution is going to be too slow, and something more subtle is required. Dynamic programming looks more promising, but it seems that there are too many variables to keep track of (we would need to keep a history of how many seats were available at what times). How about just a greedy algorithm, taking more and more cows until no more will fit on the shuttle? The obvious objection is that it matters which cows are taken - taking a cow from stop 3 to stop 5 is obviously better than taking a cow from stop 1 to stop 10. So what about prioritising the groups? Let's say that Bessy is going from A to B (A < B) and Claire is going from C to D (C < D). Obviously if A > C and B < D then Bessie should have higher priority. It's not clear what to do when the routes are not nested like this, but let's see what happens if we prioritise cows by their target stop.

First, try it out on the sample test case. You'll find that it gets the right answer. At this point you should try to prove that this algorithm is correct. This is an important step for any greedy algorithm, because in many cases what looks correct can and will be foiled by carefully constructed test cases. In this case the proof is quite subtle, and will be left as an exercise for the reader.

Finally, we must find a way to quickly determine whether each cow can be added to the driving plan. A simple approach is just to keep track of how many free seats there are on each leg of the journey (a leg being a hop from one stop to the next). This is unfortunately a little too slow, so some optimisations are required. A first optimisation is to keep track of the maximum number of groups that can start a journey at each given position and continue to the current point; this makes each query (for the number of cows to take from each group) O(1). Some further implementation tricks reduce the total cost of updates to O(Klog K + NC) rather than O(Klog K + N).

Here is Bruce Merry's solution:

/*
PROG: shuttle
LANG: C++
*/

#include <fstream>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;

struct group
{
    int M;
    int S;
    int E;

    bool operator<(const group &b) const
    {
        return S < b.S;
    }
};

int main()
{
    ifstream in("shuttle.in");
    ofstream out("shuttle.out");
    int K, N, C;
    int ans = 0;

    in >> K >> N >> C;
    vector groups(K);
    for (int i = 0; i < K; i++)
        in >> groups[i].S >> groups[i].E >> groups[i].M;

    sort(groups.begin(), groups.end());

    map<int, int> off;      // number getting off at time t
    int total = 0;          // number on shuttle
    for (int i = 0; i < K; i++)
    {
        int pos = groups[i].S;
        map<int, int>::iterator p = off.begin();
        while (p != off.end() && p->first <= pos)
        {
            ans += p->second;
            total -= p->second;
            off.erase(p++);
        }

        off[groups[i].E] += groups[i].M;
        total += groups[i].M;
        p = off.end();
        --p;
        while (total > C)
        {
            if (total - p->second >= C)
            {
                total -= p->second;
                off.erase(p--);
            }
            else
            {
                p->second -= total - C;
                total = C;
            }
        }
    }
    ans += total;
    out << ans << "\n";
    return 0;
}