USACO Bronze 2016 Open - Diamond Collector

Authors: Danh Ta Chi Thanh, Ryan Chou, Rameez Parwez

Appears In

Bronze - Basic Complete Search

Explanation

For each diamond $x$ , we check how many other diamonds can be displayed alongside it in the case, i.e. how many other diamonds falls in the range $[x, x + k]$ . Our answer will be the maximum count we find for any diamond.

Implementation

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

C++

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

int main() {
	freopen("diamond.in", "r", stdin);
	int n, k;

Java

import java.io.*;
import java.util.*;

public class Diamond {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("diamond.in"));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int n = Integer.parseInt(initial.nextToken());
		int k = Integer.parseInt(initial.nextToken());
		int[] diamonds = new int[n];

Python

with open("diamond.in") as fin:
	n, k = map(int, fin.readline().split())
	diamonds = [int(fin.readline()) for _ in range(n)]

most = 0
"""
Iterate through all diamonds and test setting them
as the smallest diamond in the case.
"""
for x in diamonds:

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!