USACO 2016 US Open Contest Bronze Division - Diamond Collector

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can solve this by sorting the input and running brute force on the set of diamonds we want to collect.

Source codes

The source codes in C++ and Python can be seen below.

#include <bits/stdc++.h>
using namespace std;

int n, k, v[1001];

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 ans = 0;

    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++) 
            if(v[j] - v[i] <= k)
                ans = max(ans, j - i + 1);

    cout << ans;
    return 0;
}

with open("diamond.in", "r") as fin:
    data = fin.read().split()
n = int(data[0])
k = int(data[1])
v = [0] + list(map(int, data[2:2+n]))
v[1:] = sorted(v[1:])

ans = 0
for i in range(1, n+1):
    for j in range(i, n+1):
        if v[j] - v[i] <= k:
            ans = max(ans, j - i + 1)

with open("diamond.out", "w") as fout:
    fout.write(str(ans))