Connection Status:
Competition Arena > RoadWork

RoadWork

TCCC '03 NE/SE Regional · 2003-02-18 · by dgoodman

TCCC '03 NE/SE Regional · 2003-02-18 · by dgoodman · Math, Sorting
Class Name: RoadWork
Return Type: int
Method Name: fraudFeet
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

Federal repaving contracts have been awarded to various contractors to fix a number of sections of the nation's highway system. Each contract specifies a single section, giving its starting and ending location. The number of feet of highway in that section is the ending location minus the starting location. For example, a section whose start is 2000 and whose end is 2001 is just one foot long. We need software to protect the public from the possibility that contracts might be granted for overlapping sections, leaving the government to pay multiple times for fixing that part.

We want a program that will examine the contracts and will tell us how many feet of highway have been included in more than one contract. Create a class RoadWork that contains a method fraudFeet that takes int[] start and int[] end as input and returns the number of feet of highway that are included in more than one contract. Corresponding elements of start and end give the starting and ending location of a contract.

Notes

  • Keep in mind that the highways can potentially be very long (2,000,000,000 feet) and that your program must run in 8 seconds, and use less than 64 MB of memory.

Constraints

  • start contains between 1 and 50 elements inclusive
  • end contains the same number of elements as start
  • each element of end is greater than the corresponding element of start
  • each element of start and end is between 0 and 2,000,000,000 inclusive
Examples
0)
{50,50,50}
{58,58,60}
Returns: 8

All three contracts cover the section from 50 to 58

1)
{171234,12,20,30}
{171236,20,30,40}
Returns: 0
2)
{12,32,92}
{991,161,1093}
Returns: 959

32 to 92 is covered by the first 2 contracts, 92 to 161 is covered by all the contracts, and 161 to 991 is covered by the first and last contract. The answer is (92-32) + (161-92) + (991-161)

3)
{2,1,3}
{3,3,7}
Returns: 1
4)
{75,175,275}
{180,178,1000}
Returns: 3

Submissions are judged against all 82 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RoadWork with a public method int fraudFeet(vector<int> start, vector<int> end) · 82 test cases · 2 s / 256 MB per case

Submitting as anonymous