USACO Bronze February 2019 - Measuring Traffic

Authors: Brad Ma, Kevin Sheng, Jay Fu

Edit This Page

Official Analysis (C++)

Warning!

The model solution in the editorial is actually wrong on a couple of test cases. For example, for the following input:

2
on 5 5
none 3 10

The solution outputs the following:

0 5
3 10

However, the actual answer is

0 5
5 10

This is because the starting range in the solution was initialized as (−∞-\infty, ∞\infty) when in reality it should be [0, ∞\infty).

Implementation

Time Complexity O(N)\mathcal{O}(N)

C++

Warning!

Using INT32_MAX and INT32_MIN for the initial bounds will cause integer overflow because the max and min will not necessarily execute first.

#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>


using std::cout;
using std::endl;
using std::vector;

Java

Warning!

Using Integer.MIN_VALUE and INTEGER.MAX_VALUE for the initial bounds will cause integer overflow because the max and min will not necessarily execute first.

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


public class MeasuringTraffic {
	// An arbitrary number that's large compared to the ones in the problem.
	static final int LARGE = (int)1e9;


	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("traffic");
		int numMiles = io.nextInt();

Python

with open("traffic.in") as read:
	num_miles = int(read.readline())


	segment_type = []
	start = []
	end = []


	for m in range(num_miles):
		curr_type, s, e = read.readline().split()
		segment_type.append(curr_type)

Video Solution

By Jay Fu

Video Solution Code

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