Statistics

Problem Statement for "ConnectTheCities"

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

  1. 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.

  2. 20

    100

    { 0, 0, 0, 0 }

    Returns: 4

    We have enough money to place transmitters at positions 4, 8, 12 and 16.

  3. 63

    19

    { 34, 48, 19, 61, 24 }

    Returns: 12

  4. 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

  5. 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

  6. 95

    4723

    {32,12,44,70,20,69,10,22,4,55,17,15,10,29,84,76,63,94,81,80,57,85,62,82,95,43,40,76,55,90,2,56,70,47,30,90,84,8,16,56,31,1,71,9,30,27,85}

    Returns: 2

  7. 81

    3609

    {54,22,12,72,32,20,57,23,0,81,1,46,79,16,75,47,76,69,59,15,41,72,6,30,39,17,61,5,14,51,54,70,73,68,61,26,8,36,49,8,35,50,57,32,68,50}

    Returns: 2

  8. 85

    241

    {23,1,39,80,54,33,51,64,68,76,79,48,51,73,70,32,58,40,15,26,16,34,69,64,75,46,24}

    Returns: 4

  9. 85

    231

    {49,36,80,3,30,41,28,74,19,2,56,4,42,13,77,26,45,49,58,53,67,74,79,51,52,69,3,77,79,17,62}

    Returns: 3

  10. 85

    90

    {30,76,11,58,64,22,52,26,18,8,39,9,26,77,50,84}

    Returns: 5

  11. 90

    475

    {12,67,86,39,73,19,84,3,74,10,35,83,81,46,29,18,56,27,88,37,37,12,87,64,48,1,73,74,46,64,23,59,3,18,61,76,0,17,43,74,27,41,67}

    Returns: 3

  12. 88

    287

    {50,42,57,20,82,44,11,21,37,74,54,23,72,39,16,16,47,74,53,5,6,19,76,33,20,42,66,82,60,16,53,44,80,22,64,73,88,76,28,36,83,82,59}

    Returns: 2

  13. 89

    397

    {64,64,66,64,76,42,71,45,23,29,65,22,25,89,28,21,41,18,76,12,25,27,44,1,40,54,51,86,48,57,56,74,83,84,10,69,36,82,76,22,73,14,6,8,65,34,81,68,52,29}

    Returns: 2

  14. 91

    285

    {27,75,59,77,1,7,9,66,73,43,91,2,53,90,8,37,12,26,26,12,18,63,9,27,32,41,27,2,44,19,65,19,3,32,4,44,79,53,58,9,4,5}

    Returns: 3

  15. 94

    463

    {10,78,87,43,17,75,36,12,0,12,54,81,53,77,72,33,44,70,83,35,79,30,71,59,79,90,63,12,2,74,28,10,57,18,50,75,93,86,84,90,1,40,73,51,22,47,84}

    Returns: 2

  16. 98

    196

    {22,62,57,54,54,89,90,92,10,88,28,78,41,61,77,93,53}

    Returns: 6

  17. 99

    495

    {83,51,33,27,67,63,69,14,36,54,62,30,40,7,99,70,4,16,62,34,33,39,27,77,76,67,26,9,50,29,12,33,32,46,60,52,9,82,66,97,36,80}

    Returns: 3

  18. 100

    49

    {28,78,37,67,90,45,34,70,28,5,63,51,2}

    Returns: 8

  19. 100

    220

    {85,5,9,68,70,67,25,58,61,73,94,78,60,48,18,81,76,96,84,9,51,95,43,20,23,48,49,40,16,5,62,0,10,38,68,47,4,59,4}

    Returns: 3

  20. 100

    44

    {98,75,92,11,93,38,54,88,88,63}

    Returns: 14

  21. 100

    66

    {58,54,63,14,17,13,39,14,67,63,92,57,79,7,68,13,40,42,5,37,27,2,22,96,53,44,67,27,7,65,6,65,85,69,45,2,83}

    Returns: 4

  22. 100

    66

    {49,12,40,73,57,47,40,70,53,48,41,56,75,43,78,37,63,88}

    Returns: 8

  23. 100

    93

    {95,34,62,59,85,31,3,53,13,53,1,28,32,41,0,55,54,41,25,6,89,32,63,30,42,6,67,4,95,36,60,89,36,22}

    Returns: 4

  24. 100

    90

    {53,84,40,66,3,41,94,1,83,95,56,2,1,47,9,56,80,38,86,88,10,18,92,71,54,51,26,56,39,40,77,92,90,16,23,93,23,84,94,5}

    Returns: 3

  25. 100

    96

    {75,45,63,84,0,8,88,53,96,98,71,87,35,92}

    Returns: 9

  26. 100

    60

    {6,43,43,10,6,10,87,43,10,6,20,10,87,6,43,6,10,3,43,20,10,6,20,20,6,43,20,10,20,10,87}

    Returns: 11

  27. 100

    80

    {42,76,99,77,42,77,16,8,42,16,8,77,76,99,99,77,42,76,16,8,8,42,77,16,16,16,77,77,76,81,8,8,53,8,77,16,42}

    Returns: 7

  28. 100

    64

    {20,20,42,30,47,8,82,30,10,20,20,30,20,42,30,30,30,20,20,42,42,20,47,82,42,42,47,8,10}

    Returns: 10

  29. 100

    84

    {44,58,58,58,44,26,26,26,4,26,4,44,4,26,4,16,26,44,44,4,4,58,44,4,58,16,44,26,16,4,16,26,44}

    Returns: 10

  30. 100

    91

    {69,96,15,15,18,18,96,69,69,85,15,96,18,15,85,85,15,85,69,18,85,18,15,1,96,1,18,85,85,18,69,85,15,1,69,15,18,96,96}

    Returns: 9

  31. 100

    27

    {9,88,17,87,17,17,9,87,80,9,87,88,88,87,88,9,9,87,17}

    Returns: 36

  32. 100

    31

    {93,59,59,59,73,34,73,75,75,87,34,59,59,34,87,87,87,34,93,73,59,87,87,59,59,87,34,87,93}

    Returns: 16

  33. 100

    16

    {35,11,57,2,11,35,57,57,11,2,57,2,11,11,11,57,11,57,57,57,11}

    Returns: 27

  34. 100

    32

    {58,81,81,58,81,13,13,81,58,13,13,58,81,13,13,13,13,13,58,58,58,81}

    Returns: 19

  35. 100

    35

    {20,32,32,20,20,73,20,20,32,73,20,57,73,73,57,57,73,20,73,20,32,20,32,73,32}

    Returns: 14

  36. 4

    4

    {2,0,2,0,4,4,4,4,3}

    Returns: 1

  37. 8

    5

    {0,0,0,0,0,8,8,8,8,8}

    Returns: 3

  38. 1

    0

    {0}

    Returns: 1

  39. 1

    0

    {0,0,0,0,0,0,0,0,0,0}

    Returns: 1

  40. 2

    0

    {2,2,0,0}

    Returns: 2

  41. 2

    1

    {2,0,2,0}

    Returns: 1

  42. 3

    0

    {0,3}

    Returns: 3

  43. 3

    1

    {0,3}

    Returns: 2

  44. 3

    2

    {0,3}

    Returns: 1

  45. 1

    0

    { 0, 1, 0, 1, 1, 1, 0, 1, 0 }

    Returns: 1

  46. 4

    39031

    { 2, 0, 1, 4, 0, 4, 2, 1, 3, 1 }

    Returns: 1

  47. 1

    1

    { 1, 0, 1 }

    Returns: 1

  48. 5

    0

    { 2, 3, 0, 1, 3, 0, 2, 0 }

    Returns: 2

  49. 6

    4

    { 4, 2, 0, 0, 6, 2, 6, 4, 6 }

    Returns: 1

  50. 72

    16

    { 38, 53, 35, 37, 43, 37 }

    Returns: 19

  51. 27

    3

    { 18, 3, 10, 27, 12, 25, 22, 24 }

    Returns: 5

  52. 69

    71

    { 55, 36, 37 }

    Returns: 18

  53. 6

    6

    {2, 2, 4 }

    Returns: 2

  54. 100

    2

    {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: 98

  55. 1

    1000

    {0, 1 }

    Returns: 1

  56. 100

    0

    {0 }

    Returns: 100

  57. 20

    20

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 11, 16 }

    Returns: 4

  58. 7

    0

    {2, 3, 5 }

    Returns: 2

  59. 4

    0

    {1 }

    Returns: 3

  60. 11

    1

    {3, 4, 8 }

    Returns: 3

  61. 10

    3

    {1, 2, 3 }

    Returns: 4

  62. 16

    8

    {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: 8

  63. 100

    139

    {50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11 }

    Returns: 10

  64. 100

    0

    {1, 10, 40, 90 }

    Returns: 50

  65. 10

    1

    {1, 3, 5, 7, 9 }

    Returns: 2

  66. 100

    5000

    {50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50 }

    Returns: 2

  67. 1

    0

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 1

  68. 2

    0

    {1, 1, 1, 1 }

    Returns: 1

  69. 10

    2

    {3, 4, 5, 6, 7, 8, 9 }

    Returns: 2

  70. 5

    1

    {1 }

    Returns: 3

  71. 5

    0

    {0, 1, 1, 2, 2, 3, 3, 4, 4, 5 }

    Returns: 1

  72. 10

    0

    {3, 7, 9 }

    Returns: 4

  73. 100

    17

    {51, 32, 86, 42, 98, 14 }

    Returns: 19

  74. 100

    220

    {1, 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, 100, 100 }

    Returns: 13

  75. 7

    0

    {0, 4 }

    Returns: 4

  76. 100

    2

    {56, 43 }

    Returns: 43

  77. 2

    0

    {2 }

    Returns: 2

  78. 30

    1

    {5, 15, 25 }

    Returns: 10

  79. 8

    0

    {2, 7, 5, 6, 4, 5, 0, 2, 3, 4, 7, 6, 3, 5, 8, 5, 6, 2, 4, 4, 0, 1, 4, 3, 7, 8, 8, 2, 3, 4, 6, 1, 5, 0 }

    Returns: 1

  80. 20

    0

    {3, 7, 11, 15, 16 }

    Returns: 4

  81. 19

    1

    {4, 10, 15 }

    Returns: 5

  82. 100

    0

    {0, 0, 0, 0, 0 }

    Returns: 100

  83. 10

    2

    {2, 5 }

    Returns: 4

  84. 100

    0

    {0, 50, 100 }

    Returns: 50

  85. 100

    6

    {2, 56, 7, 9, 11, 79, 96, 1, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 8, 9, 11, 87, 87, 87, 66, 62 }

    Returns: 39

  86. 100

    0

    {50, 100 }

    Returns: 50

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: