TopCoder problem "RadarGuns" used in SRM 372 (Division I Level Three)



Problem Statement

    

You are in a bit of a jam. The head of the local police force has been ordered to discover the number of people who have been speeding on a local road. He set up two radar guns at each end of the road, and recorded the times that the vehicles entered the road, and the times at which they exited the road. Thus, he could easily determine how many people were speeding and collect fines from them.

The police chief's plan fell through, though, when he was fired for illegal gambling involving squirrels. On his way out the door, he scrambled the times so that you no longer know which entering time belongs to which exit time.

You need to solve this issue so that you can plan this year's budget. You have enterTimes and exitTimes, which correspond to times (in seconds) in which cars entered and exited the road, respectively. You also know speedTime; a car is considered speeding if it takes less than speedTime seconds to travel down the road. No matter how quickly the cars are speeding, it always takes at least 1 second for a car to travel down the road.

You must select a matching of enterTimes and exitTimes, such that each car exits the road at a time later than when it enters, and each element of enterTimes and exitTimes is used exactly once. Once you have done this, you will collect fines from those cars that were speeding. If a speeding car took T seconds to travel on the road, then you will collect (speedTime-T)^2 dollars from the car (up to a maximum of fineCap dollars); if a car was not speeding (i.e., it took at least speedTime seconds to travel on the road), you can collect no fine from that car.

Since you can't exactly determine the total amount of money that you should collect from all of the cars, you instead want to determine the minimum and maximum sums of money that you can collect. You will return a int[] containing two elements, the first being the minimum sum that can be collected, and the second containing the maximum sum. If the data could not be obtained by the radar guns, you are to return an empty int[].

 

Definition

    
Class:RadarGuns
Method:getRange
Parameters:int[], int[], int, int
Returns:int[]
Method signature:int[] getRange(int[] enterTimes, int[] exitTimes, int speedTime, int fineCap)
(be sure your method is public)
    
 

Constraints

-enterTimes will contain between 1 and 50 elements, inclusive.
-Each element of enterTimes will be between 0 and 1000, inclusive.
-exitTimes will contain the same number of elements as enterTimes.
-Each element of exitTimes will be between 0 and 1000, inclusive.
-speedTime will be between 1 and 1000, inclusive.
-fineCap will be between 0 and 10000, inclusive.
 

Examples

0)
    
{1, 2}
{4, 5}
3
100
Returns: {0, 1 }
In this case, we have two possible pairs:

1) (1,4) and (2,5). Here, both cars took 3 seconds, so no fines are collected.

2) (1,5) and (2,4). Here, the second car took only 2 seconds, and so must be fined (3-2)^2 = 1 dollar.
1)
    
{2,1}
{60,40}
100
100
Returns: {200, 200 }
It doesn't matter how we arrange the cars here. Each one receives the maximum fine of $100.
2)
    
{1000, 584, 390, 392, 109}
{987, 724, 814, 597, 422}
1
30
Returns: { }
3)
    
{1,2,3}
{4,5,6}
7
42
Returns: {48, 56 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8143

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10789&pm=8143

Writer:

connect4

Testers:

PabloGilberto , radeye , Olexiy , Andrew_Lazarev

Problem categories:

Dynamic Programming, Search