USACO 2018 December Contest Silver Division - Convention

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We do a binary search on the answer and for each value, we run it through a function that sees if its valid, it repeats until it finds the min wait time.

Source code

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

#include <bits/stdc++.h>
using namespace std;
ifstream f("convention.in");
ofstream g("convention.out");
int n, m, c;
int v[100002];
bool check(int mid) {
    int countt = 0;
    int psm = 0;
    for (int i = 1; i <= n; ++i)
        if (i == 1 || i - psm == c || v[i] - v[psm] > mid) {
            ++countt;
            psm = i;
        }
    if (countt <= m) {
        return 1;
    }
    return 0;
}
int main() {
    f >> n >> m >> c;
    for (int i = 1; i <= n; ++i) {
        f >> v[i];
    }
    sort(v + 1, v + n + 1);
    int b = 1;
    int e = 1000000000;
    int ans = 0;
    while (b <= e) {
        int mid = (b + e) / 2;
        if (check(mid)) {
            ans = mid;
            e = mid - 1;
        } 
        else {
            b = mid + 1;
        }
    }
    g << ans;
    return 0;
}