TopCoder problem "ConnectTheCities" used in SRM 370 (Division I Level Two)



Problem Statement

    

A and B are two cities distance units away from each other. Several transmitters have been placed along the straight road connecting them. The transmission range can be set to any positive integer value, but it must be the same for all transmitters. Any two transmitters can communicate directly if the distance between them is not greater than the transmission range. Each transmitter can communicate with city A or city B if the distance between the transmitter and the city is not greater than the transmission range.

You have been assigned to set up a connection between the cities. You are allowed to move any number of transmitters, but moving a transmitter for k units costs you k dollars and the budget does not allow you to spend more than funds dollars in total. You can move the transmitters into points with integer coordinates only.

You will be given a int[] position, with the i-th element of position representing the initial distance between the i-th transmitter and city A. You will be also given funds, the maximal total cost you are allowed to spend when moving transmitters. Return the minimal transmission range which still allows you to establish a connection between the cities. See notes for the formal definition of the connection.

 

Definition

    
Class:ConnectTheCities
Method:minimalRange
Parameters:int, int, int[]
Returns:int
Method signature:int minimalRange(int distance, int funds, int[] position)
(be sure your method is public)
    
 

Notes

-Cities A and B are connected if there exists a sequence of transmitters t1, t2, ..., tn such that transmitter t1 can communicate directly with city A, transmitter tn can communicate directly with city B and, for every i between 1 and n-1, inclusive, transmitters ti and ti+1 can communicate directly.
 

Constraints

-distance will be between 1 and 100, inclusive.
-position will contain between 1 and 50 elements, inclusive.
-Each element of position will be between 0 and distance, inclusive.
-funds will be between 0 and 100000, inclusive.
 

Examples

0)
    
10
5
{ 3, 7, 9 }
Returns: 3
We can move the second transmitter one unit left and the range of 3 units will be enough for a connection.
1)
    
20
100
{ 0, 0, 0, 0 }
Returns: 4
We have enough money to place transmitters at positions 4, 8, 12 and 16.
2)
    
63
19
{ 34, 48, 19, 61, 24 }
Returns: 12

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10786&pm=8185

Writer:

mateuszek

Testers:

PabloGilberto , Olexiy , lovro , ivan_metelsky

Problem categories:

Dynamic Programming, Search