USACO 2017 February Contest Silver Division - Why Did the Cow Cross the Road II

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

First, we can store the position of the broken signals in a vector as we care about the segment of \(k\) signals with the biggest amount of working lights. Then, we can run a sliding window algorithm to find the segment with the highest sum.

At the end, we print the minimal answer, thus obtaining a linear time algorithm. Alternatively, we can use prefix sums and do the same thing with the same time complexity.

Source code

The source code in C++ can be seen below.

#include <fstream>
#include <vector>

using namespace std;

int main() {

    ifstream cin("maxcross.in");
    ofstream cout("maxcross.out");

    int n, k, b;
    cin >> n >> k >> b;

    vector<int> broken(n+1);
    for (int i = 1; i <= b; i++) {
        int x;
        cin >> x;

        broken[x] = 1;
    }

    int cnt = 0, mini = b;
    for (int i = 1; i <= n; i++) {
        cnt += (1 - broken[i]);
        if (i > k) {
            cnt -= (1 - broken[i - k]);
        }
        if (i >= k) {
            mini = min(mini, k - cnt);
        }
    }

    cout << mini << '\n';
    return 0;
}