USACO 2016 US Open Contest Silver Division - Diamond Collector

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Unlike the bronze version, the input is much larger and we can't get this done using brute force anymore.

Given that we have two boxes at our disposal, we can think at using one of them for a group of diamonds on one side of the array and of using the other box on the other side of the array. Therefore, we can use two pointers and prefix maximums to find out for each position, how much we can expand to the left and to the right in order to avoid the difference become greater than \(k\) and with this information, we can rely on prefix maximums to store the largest such length on both ends of the array.

All we now have to do is to compute the maximum by fixing the divide point and taking the best on the left and the best on the right and summing them up.

Source code

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

#include <fstream>
#include <algorithm>
using namespace std;

int n, k, v[100001], maxL[100001], maxR[100001];

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

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    sort(v + 1, v + n + 1);

    int pos = 1;    
    for (int i = 1; i <= n; i++) {
        while (pos < i && v[i] - v[pos] > k) {
            pos++;
        }
        maxL[i] = max(maxL[i-1], i - pos + 1);
    }

    pos = n;
    for (int i = n; i >= 1; i--) {
        while (pos > i && v[pos] - v[i] > k) {
            pos--;
        }
        maxR[i] = max(maxR[i+1], pos - i + 1);
    }

    int ans = 0;
    for (int i = 0; i <= n; i++) {
        ans = max(ans, maxL[i] + maxR[i+1]);
    }

    cout << ans;
    return 0;
}