Statistics

Problem Statement for "WeatherCommunications"

Problem Statement

You're attempting to secure communication lines between a collection of weather outposts on islands in the Pacific. The cost of running the line is expensive and you wish to minimize the length of line that must be run. Enough connections must be made so that even if one of the outposts loses power in a storm and communication is disabled at that outpost, the remaining outposts will still be able to reroute and resume communication. In other words, there must be two distinct paths between any two outposts, such that those paths don't share a common outpost save for the starting and ending outposts. You also want to take advantage of the communication lines that already connect some of the outposts.

You'll need to write a method lowestCostToSecure that will take an int[] of the x-coordinates of the island outposts (xcoord), an int[] of the y-coordinates of the islands outposts (ycoord), and a String[] of island outpost pairs that are already connected by communication line (alreadyConnected), and return an integer that represents the minimum amount of line that must be run in order to provide secure communications between the island outposts, rounded down.

The inputs are in the following format:

  • The outposts are numbered from 0 to the length of xcoord minus one, inclusive.
  • xcoord[i] represents the x-coordinate of outpost i
  • ycoord[i] represents the y-coordinate of outpost i
  • alreadyConnected is a String[], where each element is two legal outpost numbers separated by a single space (0x20)

Definition

Class:
WeatherCommunications
Method:
lowestCostToSecure
Parameters:
int[], int[], String[]
Returns:
int
Method signature:
int lowestCostToSecure(int[] xcoord, int[] ycoord, String[] alreadyConnected)
(be sure your method is public)

Notes

  • All coordinates are given in standard cartesian space.
  • All lines between outposts are bidirectional.
  • You should truncate the total distance, not each individual distance.

Constraints

  • xcoord will contain between 2 and 6 elements inclusive.
  • Each element in xcoord will be between -100 and 100 inclusive.
  • ycoord will contain the same number of elements as xcoord.
  • Each element in ycoord will be between -100 and 100 inclusive.
  • Every outpost will have a unique (x-coordinate,y-coordinate) location.
  • alreadyConnected will contain between 0 and 20 elements, inclusive.
  • All elements of alreadyConnected will represent distinct lines (i.e. {"0 1","1 0"} will not be allowed).
  • Each element in alreadyConnected will be of the form " ".
  • and will be integers between 0 and the length of xcoord minus one inclusive.
  • and will not be equal.
  • The actual number of miles (untruncated) will never be within .0000005 of an integer.

Examples

  1. {0,1}

    {0,5}

    {}

    Returns: 5

    Two islands: one at 0,0 and the other at 1,5. There is only one way to do it, which takes sqrt(26) miles of line, which truncates to 5.

  2. {0,0,4}

    {0,3,1}

    {}

    Returns: 11

    A simple triangle. The only way to secure it is to create a ring from outpost 0 to outpost 1 to outpost 2 back to outpost 0, taking 3+sqrt(20)+sqrt(17) or about 11.59524158 miles. You will truncate the answer and thus return 11.

  3. {0,3,0,3}

    {0,1,7,6}

    {}

    Returns: 18

    Note that going around the trapezoid is easier than traversing the diagonals of the trapezoid.

  4. {0,3,0,3}

    {0,1,7,6}

    {"0 3"}

    Returns: 13

    Same trapezoid, this time the line 0-3 is already established, giving an advantage to using the already established diagonal.

  5. {30,-100,1,100,-100,100}

    {40,-100,1,-100,100,100}

    {}

    Returns: 882

  6. {-100,100,-100,100,-99}

    {-100,-100,100,100,0}

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

    Returns: 100

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

    {6,4,2,1,7,3}

    {}

    Returns: 16

    Note how lbackstrom's solution takes more than 3 seconds to solve this test case with a floyd's algorithm for checking for biconnectedness, where the writer's solution using a much-improved biconnectedness checker can solve it in under 2 tenths of a second. :) I'm pretty sure I won't time out now.

  8. {1,7,2,3}

    {8,9,11,-17}

    {"0 1","1 2"}

    Returns: 53

  9. {0,-1,2,3,1}

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

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

    Returns: 1

    This (rhombus?) broke the writer's original solution, and may catch other coders trying the same technique. If you just check for a hamiltonian loop as your biconnectedness check, this will find most solutions, but it won't find biconnectedness on graphs that have no hamiltonian path in the optimal solution, which I guess this example does. Either that or there was some other flaw in the writer's own solution. The new implementation finds the optimal solution of at least 1 mile of line(connecting outpost 4 to outpost 2), because it actually checks for biconnectedness. It turns out that this check is a lot faster as well.

  10. {-4,0,4,-4,7,-7}

    {-4,7,-4,4,0,0}

    {"0 1"}

    Returns: 36

  11. {-6,-4,-2,-2,4,6}

    {0,1,6,-8,9,3}

    {"0 3","4 5"}

    Returns: 27

  12. {-6,-4,-2,-2,4,6}

    {0,1,6,-8,9,3}

    {"0 3","3 5","5 0"}

    Returns: 20

  13. {42,-58,-82,-80,8,-33}

    {-89,-41,-77,-77,-76,-83}

    {}

    Returns: 278

  14. {-20,-70,-49,-46,-70,-59}

    {-53,-68,-25,-64,-64,-96}

    {}

    Returns: 181

  15. {-23,-57,-36,-99,-39,-33}

    {-95,-89,-63,-71,-21,-67}

    {}

    Returns: 235

  16. {-57,-88,77,-96,-21,-62}

    {-50,-60,-95,-61,-42,-31}

    {}

    Returns: 381

  17. {-50,-19,-84,-34,-42,73}

    {-47,-47,-98,-33,-50,41}

    {}

    Returns: 426

  18. {-30,-25,-27,-28,-74,-33}

    {-29,-20,-29,-30,-46,-49}

    {}

    Returns: 128

  19. {-31,-44,-26,-73,-52,-37}

    {-26,-96,-97,-87,-84,-74}

    {}

    Returns: 201

  20. {-64,-82,-78,-53,-56,-47}

    {-20,-88,-92,-72,-65,-86}

    {}

    Returns: 176

  21. {-86,11,-82,-89,-75,-88}

    {-88,-33,-77,-76,-72,-77}

    {}

    Returns: 234

  22. {19,-82,-57,39,-89,72}

    {-96,-98,-39,-25,-26,49}

    {}

    Returns: 518

  23. {-55,87,58,-69,-91,-66}

    {-55,25,-81,40,-38,-63}

    {"0 1"}

    Returns: 415

  24. {-1,4,72,81,62,-23}

    {-18,65,-65,82,68,40}

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

    Returns: 58

  25. {36,-6,-9,-20,-22,1}

    {81,42,100,47,100,-97}

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

    Returns: 57

  26. {-46,-66,56,-68,-22,94}

    {48,21,85,43,72,13}

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

    Returns: 56

  27. {18,-36,-40,-33,13,-7}

    {-66,-82,-36,30,70,-47}

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

    Returns: 31

  28. {-68,62,21,-38,58,-6}

    {-84,-64,19,5,48,9}

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

    Returns: 32

  29. {-13,1,56,-47,-49,-93}

    {-26,-64,-87,40,17,-20}

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

    Returns: 40

  30. {-74,30,57,-34,-23,60}

    {7,41,-95,2,63,-44}

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

    Returns: 40

  31. {-88,-92,20,-60,-44,35}

    {-98,-99,64,-28,-43,-25}

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

    Returns: 158

  32. {57,-5,10,-83,10,0}

    {55,-72,48,15,21,71}

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

    Returns: 99

  33. {1,-67,83,86,-36,-68}

    {25,-98,74,-76,-29,96}

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

    Returns: 65

  34. {3,77,-23,29,33,-2}

    {45,52,-92,-8,42,-66}

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

    Returns: 76

  35. {59,-88,-9,5,-68,-65}

    {-62,-80,80,-86,78,-46}

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

    Returns: 262

  36. {92,77,-20,-1,-24,-52}

    {7,-67,-45,59,-12,54}

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

    Returns: 157

  37. {-34,51,36,27,68,-90}

    {-6,12,-35,33,41,-21}

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

    Returns: 163

  38. {92,-96,77,-37,63,-25}

    {44,-67,-60,-7,-15,25}

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

    Returns: 221

  39. {-92,15,49,-54,-39,-22}

    {25,99,30,93,29,16}

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

    Returns: 130

  40. {81,70,-12,34,49,-55}

    {-15,22,-47,-48,66,37}

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

    Returns: 140

  41. {-81,17,27,-95,26,58}

    {42,-92,32,77,-70,-82}

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

    Returns: 210

  42. {47,18,-69,9,79,5}

    {-2,-39,-54,-58,57,-62}

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

    Returns: 100

  43. {12,-64,-88,65,58,-41}

    {46,-4,-35,45,99,34}

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

    Returns: 83

  44. {39,-26,90,-86,82,25}

    {19,49,75,33,84,-33}

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

    Returns: 12

  45. {61,-57,-41,-10,-47,-95}

    {-69,73,-94,7,-92,16}

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

    Returns: 192

  46. {-46,-13,14,-57,68,26}

    {90,89,47,18,-14,11}

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

    Returns: 76

  47. {-15,62,-52,65,81,-17}

    {65,-65,99,14,-54,31}

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

    Returns: 34

  48. {-13,73,26,11,29,88}

    {-12,-74,-81,6,40,20}

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

    Returns: 66

  49. {-10,-86,-18,42,-7,-21}

    {64,42,35,91,1,46}

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

    Returns: 11

  50. {-46,-36,-21,63,-64,57}

    {-1,-59,71,-60,-35,71}

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

    Returns: 290

  51. {-50,-74,-47,-63,-85,4}

    {-58,46,-5,-98,-19,-58}

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

    Returns: 42

  52. {-21,2,75,54,62,-85}

    {2,53,4,0,21,34}

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

    Returns: 71

  53. {-24,-20,-91,-20,-64,84}

    {19,-90,-5,89,97,69}

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

    Returns: 110

  54. {29,-43,-30,92,98,-10}

    {4,23,-8,95,-61,-46}

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

    Returns: 142

  55. {20,-94,32,31,-24,82}

    {-2,-36,46,54,92,39}

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

    Returns: 58

  56. {15,-75,95,44,95,84}

    {78,-54,-10,87,-61,-14}

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

    Returns: 81

  57. {-39,-71,10,-42,-93,40}

    {12,35,-48,8,11,-51}

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

    Returns: 101

  58. {40,-61,-84,17,-7,-96}

    {52,83,-97,-8,93,25}

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

    Returns: 119

  59. {58,91,-27,62,83,-70}

    {50,-94,0,-53,-58,18}

    {"0 2","0 5","2 4","2 5","4 5"}

    Returns: 190

  60. {20,55,41,-86,-36,-86}

    {-84,22,86,-96,97,39}

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

    Returns: 65

  61. {48,4,21,-68,18,95}

    {98,5,9,-16,-47,93}

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

    Returns: 56

  62. {-1,28,45,98,54,86}

    {-1,12,85,-11,-40,-19}

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

    Returns: 14

  63. {16,91,-9,99,3,-88}

    {50,40,63,-17,40,-94}

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

    Returns: 25

  64. {96,-33,-80,-8,-90,69}

    {47,-97,68,56,39,16}

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

    Returns: 41

  65. {5,-79,81,-4,41,13}

    {-95,-67,80,13,-44,90}

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

    Returns: 88

  66. {3,-95,92,63,-27,-32}

    {41,7,-1,0,-50,-69}

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

    Returns: 127

  67. {-29,-19,-92,81,-77,99}

    {-7,58,24,-36,-96,93}

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

    Returns: 237

  68. {-25,87,49,81,-28,72}

    {94,-35,-18,-90,62,45}

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

    Returns: 150

  69. {66,-29,2,52,-97,-40}

    {-9,46,2,-98,-60,-70}

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

    Returns: 57

  70. {-91,35,-38,86,4,-20}

    {53,-89,56,-70,-84,87}

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

    Returns: 35

  71. {15,-35,16,59,-5,-71}

    {32,-80,-98,-67,28,-30}

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

    Returns: 53

  72. {22,-29,60,-17,58,-1}

    {24,-36,-8,78,69,63}

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

    Returns: 102

  73. {-75,61,-92,-51,23,40}

    {42,46,-88,81,-90,98}

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

    Returns: 115

  74. {-98,7,-13,60,17,-71}

    {63,-82,62,44,21,89}

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

    Returns: 50

  75. {-55,-20,2,-70,-85,46}

    {37,88,48,17,20,-8}

    {"0 5","1 4"}

    Returns: 157

  76. {-95,27,-70,-48,66,93}

    {-12,77,-2,100,-20,1}

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

    Returns: 138

  77. {-29,-61,-32,46,7,31}

    {-2,49,17,86,2,-26}

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

    Returns: 36

  78. {36,89,10,-2,41,-82}

    {68,100,39,62,9,-79}

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

    Returns: 362

  79. {24,84,-76,54,-8,-59}

    {-83,-78,96,56,-77,53}

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

    Returns: 32

  80. {-50,46,-66,-75,7,-34}

    {-8,94,-81,-24,-33,52}

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

    Returns: 94

  81. {-74,88,-39,-47,-93,-70}

    {-23,-68,-40,31,81,60}

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

    Returns: 38

  82. {93,-58,-83,-65,-11,58}

    {35,-15,54,-40,4,-71}

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

    Returns: 101

  83. {-16,14,87,47,-25,-44}

    {27,49,9,-51,-26,-24}

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

    Returns: 148

  84. {95,64,3,23,-11,95}

    {-82,-15,-90,-69,-61,18}

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

    Returns: 77

  85. {44,-69,31,-45,-44,-47}

    {-25,43,16,37,84,77}

    {"0 4"}

    Returns: 194

  86. {-39,-94,-69,-72,85,-67}

    {-87,-3,39,-89,-33,35}

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

    Returns: 81

  87. {-20,-28,99,-68,-68,76}

    {53,-95,-71,64,-69,49}

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

    Returns: 47

  88. {-46,-54,91,-83,72,-75}

    {-24,75,27,100,26,-34}

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

    Returns: 165

  89. {-93,-14,-38,-37,40,-6}

    {91,-65,45,-15,61,12}

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

    Returns: 120

  90. {83,94,11,-15,-40,-73}

    {77,34,97,-66,11,13}

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

    Returns: 119

  91. {-50,16,-61,-43,16,80}

    {-58,-1,11,33,-39,-76}

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

    Returns: 134

  92. {7,-89,100,-85,-69,-96}

    {-42,-79,26,-58,13,21}

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

    Returns: 384

  93. {79,-61,53,97,-59,79}

    {2,69,-14,-37,67,-57}

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

    Returns: 2

  94. { 0, 0, 4 }

    { 0, 3, 1 }

    { }

    Returns: 11

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

    { 0, 1, 2, 81, 82, 83 }

    { }

    Returns: 167

  96. { -14, 53, 34, -53, 16, 0 }

    { 45, 34, -67, 66, -7, 100 }

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

    Returns: 171

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: