# USACO 2014 December Contest, Gold Problem 3. Cow Jog

USACO2014-DEC-G3

(Analysis by Mark Gordon)

Two cows must be in different lanes if one cow overtakes the other at some point (or at the very end) in the jog. Viewed this way we can greedily assign all cows that are not overtaken by another cow during the jog to lane 1. We can then remove these cows and repeat the algorithm to assign cows to the remaining lanes.

To prove this is optimal suppose we assign k lanes in total; then there is some cow, ck, in lane k that is overtaken during the jog by a cow in lane k1, ck1 (otherwise we would have assigned it to lane k1(instead). We can repeat this and find ck2 as the cow that overtakes ck−1 in lane k-2 all the way down to c1. Crucially, because the overtakes relation is transitive, it follows that ci overtakes cj for i<j. Therefore none of these cows can be in the same lane and k lanes are therefore required (and the greedy algorithm mentioned achieves this).

Efficiently implementing a solution based on this can be done in a number of ways. One way is to realize that the end positions of the cows in cc are non-increasing while the start positions are increasing. Therefore we can simply compute the longest non-increasing subsequence of the array. This is a small adaptation of the well known Longest Increasing Subsequence algorithm.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
int N, T;
cin >> N >> T;

vector<long long> A;
for (int i = 0; i < N; i++) {
long long x, s;
cin >> x >> s;
x = -(x + s * T);

if (A.empty() || x >= A.back()) {
A.push_back(x);
} else {
*upper_bound(A.begin(), A.end(), x) = x;
}
}

cout << A.size() << endl;
return 0;
}