November 2005 Problem 'acrobat' Analysis

This is actually a sorting problem, but in disguise. We first make a simple transformation to make the problem more accessible. The problem statement tells us that the risk of a cow falling depends on the weight of those above her, excluding her weight. For reasons that we will become apparent, it would be better if the risk depended on the weight including her own. We can in fact force the problem into this form by modifying each cow's strength: specifically, adding her own weight to her strength to cancel out the increase we have made in risk.

Now logically, it would make sense to put strong cows on the bottom, to hold the greater weight of those above them. Before making the transformation, this heuristic might have lead us to put a weak but extremely heavy cow on top, but because each cow now has the strength to support her own weight, very heavy cows will naturally be strong and so likely to be near the bottom.

Of course, this is all so much woolly thinking unless we can prove that this is optimal. A good way to prove that sorting optimises a problem is to consider the actions of some sorting algorithm and show that they always improve matters (or at least make them no worse). In this case we will use bubble-sort, as it is particularly simple. Consider an arrangement where two cows, Alice and Bessie, are our of order. Specifically, Alice is directly top of Bessie, but is stronger than her. If they are swapped then the risk to other cows of course does not change, since their combined weight is a constant. The risk of Alice collapsing increases, but it is still lower than that of Bessie collapsing previously (since the weight carried by the bottom cow is the same, but Alice is stronger). The risk of Bessie collapsing has also been reduced, since Bessie no longer has to carry Alice. So the maximum risk does not increase and is most likely reduced. Thus, from any given configuration, a bubble-sort will eventually have the cows sorted by strength at no increase in risk.

The actual implementation thus consists of the transformation, a call to sort(), and a walk of the pile to determine the maximum risk.

Here is Bruce's solution:

#include <iostream>
#include <fstream>
#include <algorithm>
#include <utility>
#include <vector>
#include <cstddef>
#include <climits>

using namespace std;

typedef pair<int, int> cow;

int main() {
    vector<cow> cows;
    int N;
    ifstream in("acrobat.in");

    in >> N;
    for (int i = 0; i < N; i++) {
        int wgt, str;
        in >> wgt >> str;
        cows.push_back(cow(str + wgt, wgt));
    }
    sort(cows.begin(), cows.end());

    int risk = INT_MIN;
    int sum = 0;
    for (int i = 0; i < N; i++) {
        sum += cows[i].second;
        risk = max(risk, sum - cows[i].first);
    }
    ofstream out("acrobat.out");
    out << risk << endl;
    in.close();
    out.close();
    return 0;
}