USACO 2011 Nov Silver

Problem 2. Cow Lineup

Cow Lineup
Problem 2: Cow Lineup [Brian Dean]

Farmer John has hired a professional photographer to take a picture of some of his cows. Since FJ’s cows represent a variety of different breeds, he would like the photo to contain at least one cow from each distinct breed present in his herd.

FJ’s N cows are all standing at various positions along a line, each described by an integer position (i.e., its x coordinate) as well as an integer breed ID. FJ plans to take a photograph of a contiguous range of cows along the line. The cost of this photograph is equal its size – that is, the difference between the maximum and minimum x coordinates of the cows in the range of the photograph.

Please help FJ by computing the minimum cost of a photograph in which there is at least one cow of each distinct breed appearing in FJ’s herd.

PROBLEM NAME: lineup

INPUT FORMAT:

  • Line 1: The number of cows, N (1 <= N <= 50,000).

  • Lines 2..1+N: Each line contains two space-separated positive integers specifying the x coordinate and breed ID of a single cow. Both numbers are at most 1 billion.

SAMPLE INPUT (file lineup.in):

6
25 7
26 1
15 1
22 3
20 1
30 1

INPUT DETAILS:

There are 6 cows, at positions 25,26,15,22,20,30, with respective breed IDs 7,1,1,3,1,1.

OUTPUT FORMAT:

  • Line 1: The smallest cost of a photograph containing each distinct breed ID.

SAMPLE OUTPUT (file lineup.out):

4

OUTPUT DETAILS:

The range from x=22 up through x=26 (of total size 4) contains each of the distinct breed IDs 1, 3, and 7 represented in FJ’s herd.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

ll N, K;

int main() {
    setIO("lineup");

    cin >> N >> K;

    vector<int> cows(N);
    F0R(i, N) {
        cin >> cows[i];
    }

    int amt = 0;
    int ans = 0;
    map<int, int> count;
    int l = 0, r = 0;
    while (r < N) {
        while (amt > K + 1) {
            count[cows[l]]--;
            if (count[cows[l]] == 0) {
                amt--;
            }
            l++;
        }
        if (count[cows[r]] == 0) {
            amt++;
        }
        count[cows[r]]++;
        ans = max(count[cows[r]], ans);
        r++;
    }

    cout << ans;
}