Connection Status:
Competition Arena > ConnectTheCities

ConnectTheCities

SRM 370 · 2007-10-09 · by mateuszek

SRM 370 · 2007-10-09 · by mateuszek · Dynamic Programming, Search
Class Name: ConnectTheCities
Return Type: int
Method Name: minimalRange
Arg Types: (int, int, vector<int>)
Problem Statement

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.

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
3)
100
0
{ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 }
Returns: 100
4)
89
2271
{86,40,78,9,18,73,42,58,8,60,14,72,57,56,44,21,42,86,4,84,69,82,30,60,10,49,83,79,31,9,30,27,49,18,36,67,53,40,88,24,63,64,6,30,30}
Returns: 2

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

Coding Area

Language: C++17 · define a public class ConnectTheCities with a public method int minimalRange(int distance, int funds, vector<int> position) · 86 test cases · 2 s / 256 MB per case

Submitting as anonymous