USACO 2016 January Contest Silver Division - Angry Cows

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

This problem can be solved using a binary search on the answer, as the bigger the power is, the easier it is for us to detonate every single haybale.

In order to implement this, we will fix the size we are going to test and at a certain step, instead of trying to find the central place of a strike, we will greedily select the leftmost place where our strike happens and then reserve a range of size \(2 \cdot mid\), where \(mid\) is the power of our strikes.

At the end, the smallest value which allowed us to finish the process with at most \(k\) strikes is going to be our answer.

Source code

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

#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

int main() {
    ifstream cin("angry.in");
    ofstream cout("angry.out");

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

    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    sort(v.begin() + 1, v.begin() + n + 1);
    int L = 0;
    int R = 1000000000;
    int ans = R;
    while (L <= R) {
        int mid = (L + R) / 2;
        int cnt = 0;
        for (int i = 1; i <= n;) {
            cnt++;
            int j = i;
            while (j <= n && v[j] - v[i] <= 2 * mid) {
                j++;
            }
            i = j;
        }
        if (cnt <= k) {
            ans = mid;
            R = mid - 1;
        }
        else {
            L = mid + 1;
        }
    }
    cout << ans;
    return 0;
}