USACO 2016 January Contest Gold Division - Angry Cows

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

This problem can be done using various approaches, such as greedy, dp or binary search.

The solution below relies on a binary search on the size of the first explosion. To test if a particular initial explosion size works, it then does a binary search for the location of the initial explosion.

Source code

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

#include <algorithm>
#include <cmath>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

int getLowIndex(const vector<long long> &vals, double x) {
    int i = 0;
    while (i < (int)vals.size() && vals[i] < x)
        i++;
    return i - 1;
}

double binSearch(const vector<long long> &arr, double value, int index) {
    double low = 0.5, high = fabs(arr[0] - value);

    while (high - low > 0.001) {
        double mid = (low + high) / 2.0;
        double saveMid = mid, cur = value;
        int i = index;

        while (i > 0) {
            int j = i;
            while (j >= 0 && fabs(arr[j] - cur) <= mid + 1e-9)
                j--;
            if (j == i)
                break;

            i = j + 1;
            mid = mid - 1;
            cur = arr[i];
            i--;
        }

        if (i <= 0)
            high = saveMid;
        else
            low = saveMid;
    }
    return high;
}

void solve() {
    ifstream fin("angry.in");
    int n;
    fin >> n;
    vector<long long> vals(n);
    for (int i = 0; i < n; i++)
        fin >> vals[i];
    fin.close();

    sort(vals.begin(), vals.end());

    vector<long long> rev(n);
    for (int i = 0; i < n; i++)
        rev[i] = vals[n - 1 - i];

    double low = vals[0], high = vals[n - 1];
    double res = vals[n - 1] - vals[0];

    while (high - low > 0.001) {
        double mid = (low + high) / 2.0;

        int lowIndex = getLowIndex(vals, mid);
        double left = binSearch(vals, mid, lowIndex);
        double right = binSearch(rev, mid, n - 2 - lowIndex);

        res = min(max(left, right), res);

        if (left < right)
            low = mid;
        else
            high = mid;
    }

    long newRes = (long)(100 * res);
    long whole = (long)res;
    int tens = (int)(newRes % 100 - newRes % 10) / 10;
    if (newRes % 10 >= 5)
        tens++;
    if (tens == 10) {
        whole = whole + 1;
        tens = 0;
    }

    ofstream fout("angry.out");
    fout << (newRes / 100) << "." << tens << "\n";
    fout.close();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}