USACO Silver 2016 Open - Diamond Collector

Authors: Nathan Wang, Albert Ye, David Guo

Appears In

Silver - Two Pointers

Explanation

We first sort the diamonds by size, which allows us to consider groups of diamonds in order. For each diamond, we determine the maximum number of diamonds that can be grouped with it without exceeding the allowed size difference.

We precompute the best grouping possible from every starting point so that once we fix a group for one case, we can quickly identify the optimal group for the second case from the remaining larger diamonds.

Finally, we combine the two groups to determine the maximum total number of diamonds that can be showcased across both cases.

Implementation

Time Complexity: $\mathcal{O} (N \log{N})$

C++

#include <algorithm>
#include <fstream>
#include <iostream>

int main() {
	std::ifstream cin("diamond.in");

	int n, k;
	cin >> n >> k;
	int arr[n];

Java

Source: Nick Wu, from the official USACO editorial

import java.io.*;
import java.util.*;
public class diamondS {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("diamond.in"));
		PrintWriter pw =
		    new PrintWriter(new BufferedWriter(new FileWriter("diamond.out")));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

Python

import sys

sys.stdin = open("diamond.in", "r")
sys.stdout = open("diamond.out", "w")

n, k = map(int, input().split())
arr = sorted([int(input()) for i in range(n)])

# maximum number of diamonds assuming i is the smallest diamond
max_diamond = [0] * (n + 1)

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!