October 2005 Problem 'flight' Analysis

The first observation is that having two flights is a red herring. The problem can be separated into cows attempting to travel south and those attempting to travel north, and kept completely separate (a minute's thought should convince you that there are no benefits to staying on the plane during turnaround). We'll only consider the south-bound flight.

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 plane? The obvious objection is that it matters which cows are taken - taking a cow from city 3 to city 5 is obviously better than taking a cow from city 1 to city 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 city.

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 flight 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 city 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 Turkey's junior Ridvan Duran's solution:

#include <stdio.h>
#include <stdlib.h>
#define MAXN 10002
#define MAXK 50002
#define MIN(x,y) ((x)<(y)?(x):(y))
typedef struct is {
	int s,e,m;
} is;
FILE *f,*g;

int N , K , C , used[2*MAXN];

is ar[MAXK];
int comp(const void *pa, const void *pb) {
    is *a = (is *)pa;
    is *b = (is *)pb;
    if (a->e == b->e)
        return ((a->s > b->s) - (a->s < b->s));
    return (a->e > b->e) - (a->e < b->e);
}

void oku() {
    int i, a, b;
    fscanf(f, " %d %d %d", &K, &N, &C);
    for(i = 0; i < K; i++) {
        fscanf(f, " %d %d %d", &a, &b, &ar[i].m);
        if (b > a) {
	    ar[i].s=a;
	    ar[i].e=b;
	}
        else {
	    ar[i].s=2*N-a,ar[i].e=2*N-b;
	}
    }
}

int bosmu (int s,int e) {
    int i, x;
    for (i = s, x = 0; i < e && x != C; i++)
        if (x < used[i]) x = used[i];
    return C - x;
}

void doldur (int s, int e, int x) {
    int i;
    if (!x) return;
    for (i = s; i < e; i++)
        used[i] += x;
}

void islem() {
    int i, x, sum;
    qsort (ar, K, sizeof(is), comp);
    for (i = 0, sum = 0; i < K; i++) {
        x = bosmu (ar[i].s, ar[i].e);
        x = MIN(x, ar[i].m);
        doldur(ar[i].s, ar[i].e,x);
        sum += x;
    }
    fprintf (g, "%d\n", sum);
}

int main() {
    f = fopen ("flight.in" ,"r");
    g = fopen("flight.out", "w");
    oku ();
    islem ();
    fclose (f);
    fclose (g);
    return 0;
}