Statistics

Problem Statement for "RoadsAndFools"

Problem Statement

In one big country there is a saying that "we've got only two troubles: roads and fools". This problem is about both of them.

Two cities of this country are connected by a highway. Some points on the highway are marked with milestones. On the two sides of each milestone the distances to the two cities are written. When you travel from one city to another, the milestones show the distance traveled from the origin city. If the milestones are placed correctly, the numbers you see while traveling must go in ascending order since the distance you've traveled is always increasing.

During the reconstruction of the highway, some of the milestones were stolen, some were broken and some... just disappeared. On top of it all a group of bandits with unexplained motives set out to the highway one night and reversed some of the milestones.

Given the state of the remaining milestones after the act, determine if it is possible to restore the correct orientations.
You are given an int length, the length of the highway, and a int[] frontSides. Each element of frontSides is the mark on the front side of the milestone in the order they are seen traveling from the first city to the second. The mark on the opposite side of milestone i is obviously length-frontSides[i].

Return a String containing the restored sequence of milestones separated by single spaces (again, as seen traveling from the first city to the second). If there is more than one solution, return "MULTIPLE SOLUTIONS". If no solution exists (you can never tell what else could have happend to the milestones in that big country...), return "NO SOLUTION".

Two solutions are considered equal if you see the same numbers on all milestones when traveling between the cities (see examples 4 and 5 for further clarification).

Definition

Class:
RoadsAndFools
Method:
determineOrientation
Parameters:
int, int[]
Returns:
String
Method signature:
String determineOrientation(int length, int[] frontSides)
(be sure your method is public)

Constraints

  • length will be between 1 and 1000, inclusive.
  • frontSides will contain between 1 and 50 elements, inclusive.
  • each element of frontSides will be between 0 and length, inclusive.

Examples

  1. 5

    {1, 2, 3}

    Returns: "1 2 3"

    The first milestone has the numbers 1 and 4 on it. The second and third both have the numbers 2 and 3 on their two sides. "1 2 3" is the only correct orientation.

  2. 5

    {5, 2, 0}

    Returns: "MULTIPLE SOLUTIONS"

    There are two correct orientations: {0, 2, 5} and {0, 3, 5}.

  3. 5

    {4, 4}

    Returns: "1 4"

  4. 5

    {4, 4, 4}

    Returns: "NO SOLUTION"

  5. 5

    {3}

    Returns: "MULTIPLE SOLUTIONS"

    Both {2} and {3} are correct orientations.

  6. 10

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

    Returns: "0 1 2 3 4 5 6 7 8 9 10"

  7. 10

    {5}

    Returns: "5"

    Both sides of the milestone contain the number 5, so the solution is unique.

  8. 38

    {3,4,7,18,19,18,7,4,3}

    Returns: "3 4 7 18 19 20 31 34 35"

  9. 37

    {3,4,7,18,19,18,7,4,3}

    Returns: "NO SOLUTION"

  10. 39

    {3,4,7,18,19,18,7,4,3}

    Returns: "MULTIPLE SOLUTIONS"

  11. 37

    {3,4,7,18,18,7,4,3}

    Returns: "3 4 7 18 19 30 33 34"

  12. 1

    {1}

    Returns: "MULTIPLE SOLUTIONS"

  13. 1

    {0}

    Returns: "MULTIPLE SOLUTIONS"

  14. 1

    {0,1}

    Returns: "0 1"

  15. 2

    {1}

    Returns: "1"

  16. 3

    {1}

    Returns: "MULTIPLE SOLUTIONS"

  17. 1000

    {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49}

    Returns: "MULTIPLE SOLUTIONS"

  18. 50

    {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49}

    Returns: "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49"

  19. 98

    {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49}

    Returns: "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49"

  20. 99

    {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49}

    Returns: "MULTIPLE SOLUTIONS"

  21. 97

    {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,48}

    Returns: "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49"

  22. 96

    {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,48}

    Returns: "NO SOLUTION"

  23. 100

    {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,48}

    Returns: "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 52"

  24. 1000

    {49,48,47,46,45,44,43,42,41,40,49,48,47,46,45,44,43,42,41,40,49,48,47,46,45,44,43,42,41,40,49,48,47,46,45,44,43,42,41,40,49,48,47,46,45,44,43,42,41,40}

    Returns: "NO SOLUTION"

  25. 100

    {49,48,47,46,45,44,43,42,41,40,49,48,47,46,45,44,43,42,41,40}

    Returns: "NO SOLUTION"

  26. 100

    {49,48,47,46,45,44,43,42,41,40,40,41,42,43,44,45,46,47,48,49}

    Returns: "NO SOLUTION"

  27. 998

    {35,234,499,499,464,888}

    Returns: "NO SOLUTION"

  28. 998

    {35,234,498,499,464,888}

    Returns: "35 234 498 499 534 888"

  29. 998

    {35,234,499,498,464,888}

    Returns: "35 234 499 500 534 888"

  30. 777

    {0,777}

    Returns: "0 777"

  31. 777

    {0,776}

    Returns: "MULTIPLE SOLUTIONS"

  32. 777

    {1,776}

    Returns: "1 776"

  33. 100

    {17, 83}

    Returns: "17 83"

  34. 100

    {83,50,17}

    Returns: "17 50 83"

  35. 100

    {83, 50, 50, 17}

    Returns: "NO SOLUTION"

  36. 101

    {83, 50, 50, 17}

    Returns: "18 50 51 84"

  37. 99

    {83, 50, 50, 17}

    Returns: "16 49 50 82"

  38. 100

    {50, 51, 52}

    Returns: "50 51 52"

  39. 100

    {51, 52, 53}

    Returns: "MULTIPLE SOLUTIONS"

  40. 70

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

    Returns: "NO SOLUTION"

  41. 10

    {1, 5, 9 }

    Returns: "1 5 9"

  42. 5

    {4, 4, 4 }

    Returns: "NO SOLUTION"

  43. 100

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    Returns: "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50"

  44. 10

    {2, 3 }

    Returns: "MULTIPLE SOLUTIONS"

  45. 10

    {0, 4, 7, 7 }

    Returns: "NO SOLUTION"

  46. 10

    {5, 6 }

    Returns: "5 6"

  47. 10

    {2, 5, 6 }

    Returns: "2 5 6"

  48. 20

    {20, 19, 17, 18, 15, 4, 14, 13, 11, 8, 10, 9, 7, 8, 5, 6, 3, 4, 18, 1 }

    Returns: "NO SOLUTION"

  49. 8

    {2, 3 }

    Returns: "MULTIPLE SOLUTIONS"

  50. 1000

    {0, 46, 68, 93, 123, 700, 301, 500, 600, 601, 602, 607, 608, 650, 756, 789, 978, 980, 981, 982, 983, 984, 985, 986, 987, 989, 990, 1000 }

    Returns: "0 46 68 93 123 300 301 500 600 601 602 607 608 650 756 789 978 980 981 982 983 984 985 986 987 989 990 1000"

  51. 1000

    {500 }

    Returns: "500"

  52. 999

    {1, 997, 996, 4, 5, 6, 7, 8, 9, 989, 11, 987, 13, 985, 15, 983, 982, 981, 980, 979, 978, 977, 976, 975, 974, 26, 27, 28, 970, 30, 31, 32, 33, 34, 35, 963, 962, 961, 960, 959, 41, 42, 43, 44, 954, 46, 47, 48, 49, 499 }

    Returns: "MULTIPLE SOLUTIONS"

  53. 10

    {1, 1, 5 }

    Returns: "NO SOLUTION"

  54. 10

    {1, 1, 2 }

    Returns: "NO SOLUTION"

  55. 10

    {4, 5 }

    Returns: "4 5"

  56. 49

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49 }

    Returns: "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49"

  57. 5

    {1, 1 }

    Returns: "1 4"

  58. 10

    {1, 5, 4, 2, 6, 9, 8 }

    Returns: "NO SOLUTION"

  59. 10

    {1, 2, 10 }

    Returns: "MULTIPLE SOLUTIONS"

  60. 1000

    {999, 991, 242, 353, 232, 123, 123, 576, 655, 323, 567, 554, 332, 0, 0, 245, 768, 23, 53, 45, 67, 89, 12, 13, 14, 15, 16, 16, 45, 57, 90, 100, 123, 234, 345, 456, 567, 768, 1, 2, 3, 4, 5, 5, 6, 7, 72, 71, 70, 74 }

    Returns: "NO SOLUTION"

  61. 1000

    {999, 991, 242, 353, 232, 123, 123, 576, 655, 323, 567, 554, 332, 0, 0, 245, 768 }

    Returns: "NO SOLUTION"

  62. 10

    {5 }

    Returns: "5"

  63. 10

    {0, 1, 5 }

    Returns: "0 1 5"

  64. 10

    {5, 1, 0 }

    Returns: "5 9 10"

  65. 4

    {1, 3, 4 }

    Returns: "1 3 4"

  66. 8

    {5, 3, 4 }

    Returns: "NO SOLUTION"

  67. 50

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 18, 33, 34, 35, 36, 37, 38, 39, 10, 41, 42, 43, 44, 45, 46, 47, 48, 50 }

    Returns: "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 50"

  68. 10

    {1, 2, 4 }

    Returns: "MULTIPLE SOLUTIONS"

  69. 4

    {4, 1, 2, 3, 4 }

    Returns: "0 1 2 3 4"

  70. 55

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 }

    Returns: "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30"

  71. 1000

    {2, 34, 43, 230, 560, 324, 600, 23, 4, 234, 6, 56, 234, 333, 51, 150, 121, 663, 114, 888, 115, 151, 556, 441, 555, 559, 454, 151, 454, 454, 999, 454, 456, 512 }

    Returns: "NO SOLUTION"

  72. 1000

    {1, 3, 6, 7, 9, 12, 15, 200, 300, 301, 450, 6, 1, 1000 }

    Returns: "MULTIPLE SOLUTIONS"

  73. 10

    {9, 5, 4, 8 }

    Returns: "1 5 6 8"

  74. 10

    {1, 5, 10 }

    Returns: "1 5 10"

  75. 10

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

    Returns: "NO SOLUTION"

  76. 4

    {0, 1, 2, 1, 0 }

    Returns: "0 1 2 3 4"

  77. 1000

    {1, 3, 54, 32, 67, 324, 123, 654, 898, 332, 888, 768, 645, 433, 789, 435, 195, 347, 583, 753, 324, 896, 432, 785, 425, 756, 432, 43, 444, 555, 666, 777, 888, 111, 116, 118, 129, 110, 435, 456, 343, 212, 678, 546, 437, 536, 657, 340, 760, 643 }

    Returns: "NO SOLUTION"

  78. 10

    {4 }

    Returns: "MULTIPLE SOLUTIONS"

  79. 10

    {2, 5, 2 }

    Returns: "2 5 8"

  80. 999

    {1, 2, 3, 980, 300, 301, 999 }

    Returns: "MULTIPLE SOLUTIONS"

  81. 10

    {1, 5 }

    Returns: "1 5"

  82. 9

    {4, 6 }

    Returns: "MULTIPLE SOLUTIONS"

  83. 5

    {2 }

    Returns: "MULTIPLE SOLUTIONS"

  84. 9

    {3 }

    Returns: "MULTIPLE SOLUTIONS"

  85. 5

    {0, 2, 0, 0 }

    Returns: "NO SOLUTION"

  86. 100

    {0, 50, 99 }

    Returns: "0 50 99"

  87. 6

    {3, 3 }

    Returns: "NO SOLUTION"

  88. 6

    {1, 1 }

    Returns: "1 5"

  89. 10

    {5, 8 }

    Returns: "5 8"

  90. 100

    {6, 3, 0 }

    Returns: "MULTIPLE SOLUTIONS"

  91. 6

    {1, 3, 5 }

    Returns: "1 3 5"

  92. 5

    {1, 2, 3 }

    Returns: "1 2 3"

  93. 10

    {1, 5, 2 }

    Returns: "1 5 8"

  94. 10

    {4, 7, 2, 7 }

    Returns: "NO SOLUTION"

  95. 20

    {10 }

    Returns: "10"

  96. 5

    {2, 3, 4 }

    Returns: "2 3 4"

  97. 3

    {1 }

    Returns: "MULTIPLE SOLUTIONS"

  98. 5

    {1, 4, 2, 3, 1 }

    Returns: "NO SOLUTION"

  99. 10

    {1, 6, 2, 3 }

    Returns: "NO SOLUTION"

  100. 1000

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49 }

    Returns: "MULTIPLE SOLUTIONS"

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: