USACO Silver 2019 January - Mountain View

Authors: Jesse Choe, Sofia Yang, Juheon Rhee

Edit This Page

Table of Contents

ExplanationImplementation

Official Analysis (C++)

Explanation

Notice that a mountain is obscured by another mountain iff the base of the mountain (the area the mountain takes up on the ground) is contained within the base of the other mountain.

However, going through all pairs of mountains and checking if one is obscured by another takes O(N2)\mathcal{O}(N^2) time and is too slow given the input size.

To speed things up, let's sort the mountains by their left end first and then iterate through all of them, keeping track of the rightmost right end we've seen. Then, if the right side of the current mountain is less than the current highest right end, we know that that mountain is obscured by another.

Implementation

Time Complexity: O(nlog⁡n)\mathcal{O}(n\log n)

C++

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


struct Mountain {
	int start, end;
};


bool operator<(const Mountain &m1, const Mountain &m2) {
	// sort by start and tiebreak by putting the larger mountains first
	if (m1.start == m2.start) { return m1.end > m2.end; }

Java

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Mountains {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("mountains.in"));
		int mountainNum = Integer.parseInt(br.readLine());


		Mountain[] mountains = new Mountain[mountainNum];

Python

class Mountain:
	def __init__(self, start: int, end: int):
		self.start = start
		self.end = end


	def __lt__(self, other: "Mountain"):
		# sort by start and tiebreak by putting the larger mountains first
		if self.start == other.start:
			return self.end > other.end
		return self.start < other.start

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!

Join Forum