December 2005 Problem 'clean' Analysis

We use a technique that is somewhat based on dynamic programming, although we do not directly incorporate previous results. For each point in time during the day in turn, we compute the minimum total salary. We also keep a sorted list (actually a C++ multiset) of potential totals. We sweep through the events (start and stop work) in chronological order, doing the following:

• Set the total for the current point in time to the lowest potential
• If this is the start of a cow's working hours, add a potential
total. The potential total is a current minimum total, plus the salary demanded by that cow. The intent is that this potential total is a valid total at any point from now until the cow stops work (since the first term takes care of all points up until now).
• If this is the end of a cow's working hours, remove the associated potential total.

There are a few issues to be catered for related to the possibility that the barn cannot be swept (this will happen if the potential set is empty). Running time is O(N.log N), both from the initial sort and from the multiset operations. Pascal users would probably wish to use a heap rather than a multiset, as it is easier to implement from scratch (C++ priority-queue wouldn't work as it doesn't support arbitrary deletion).

Here is Bruce's solution:

#include <fstream>
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <set>

using namespace std;

struct cow {
    int A, B;
    int S;
    int value;
};

struct event {
    bool start;
    int id;
    int time;

    event() {}
    event(bool s, int i, int t) : start(s), id(i), time(t) {}
    bool operator <(const event &b) const {
        if (time != b.time) return time < b.time;
        else return start && !b.start;
    }
};

static void done(int ans) {
    ofstream out("clean.out");
    out << ans << "\n";
    out.flush();
    out.close();
    exit(0);
}

int main() {
    ifstream in("clean.in");
    int N, A, B, ans = INT_MAX;
    multiset<int> values;

    in >> N >> A >> B;
    B++;

    cow cows[N];
    event events[2 * N];
    int dp;
    for (int i = 0; i < N; i++) {
        in >> cows[i].A >> cows[i].B >> cows[i].S;
        cows[i].B++;
        cows[i].A >?= A;
        cows[i].B <?= B;
        events[2 * i] = event(true, i, cows[i].A);
        events[2 * i + 1] = event(false, i, cows[i].B);
    }

    sort(events, events + 2 * N);
    if (events[0].time > A || events[2 * N - 1].time < B) done(-1);

    for (int i = 0; i < 2 * N; i++) {
        if (events[i].time == A) dp = 0;
        else if (values.empty()) done(-1);
        else dp = *values.begin();
        if (events[i].start)
        {
            cows[events[i].id].value = dp + cows[events[i].id].S;
            values.insert(cows[events[i].id].value);
        }
        else
            values.erase(values.find(cows[events[i].id].value));
        if (events[i].time == B)
            ans <?= dp;
    }

    done(ans);
    return 0;
}