Statistics

Problem Statement for "FoxAndSightseeing"

Problem Statement

Fox Ciel is staying in Linear Country for sightseeing. The country consists of N cities numbered 0 through N-1. Ciel is currently staying in city 0.

In this problem, we assume that the country is a straight line and that each city is a point on this line. You are given a int[] position with N elements. The i-th element in position represents the coordinate of the city i. The cities are numbered arbitrarily, their numbers are not related to their positions. Thus, distance between city i and city j is |position[i] - position[j]|, where |z| represents the absolute value of z.

Ciel wanted to visit all the cities, so she planned a tour. She was going to visit city 0 on day 1, visit city 1 on day 2, and so on. She wanted to terminate the tour upon arrival to city N-1.

Unfortunately, it turned out that Ciel's holiday has to be one day shorter. Of course, she must still start in city 0 and end in city N-1, so she decided to skip one of the other N-2 cities (i.e., one of cities 1 through N-2). She still wants to visit the other cities in the order given by their numbers. For example, if N=5, Ciel has three possibilities for her holiday: she will visit the cities in one of the orders (0,1,2,4), (0,1,3,4), or (0,2,3,4).

Among these possibilities, Ciel will choose the one where the total distance she will have to travel is minimized. Compute and return this minimum total distance.

Definition

Class:
FoxAndSightseeing
Method:
getMin
Parameters:
int[]
Returns:
int
Method signature:
int getMin(int[] position)
(be sure your method is public)

Notes

  • You are not given the value of N, but you can easily determine it: N is equal to the number of elements in position.

Constraints

  • position will contain between 3 and 50 elements, inclusive.
  • Each element of position will be between -100 and 100, inclusive.
  • All the elements in position will be distinct.

Examples

  1. {1, 4, -1, 3}

    Returns: 4

    There are two strategies for Ciel. Skip city 1. The total distance is |1-(-1)|+|(-1)-3| = 2+4 = 6. Skip city 2. The total distance is |1-4|+|4-3| = 3+1 = 4. The second choice is better. So you should output 4.

  2. {-2, 4, 3}

    Returns: 5

    There is only one strategy for Ciel: She skips city 1. The total distance is |(-2)-3| = 5.

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

    Returns: 9

    For any choice she makes, the total distance is 9.

  4. {100, -100, 99, -99}

    Returns: 199

    The optimum strategy is to skip city 1.

  5. {74,84,92,23,5,-70,-47,-59,24,-86,-39,99,85,-42,54,100,47,-3,42,38}

    Returns: 836

  6. {2,-3,5,7,-11,-13,17,-19,23,29,-31,-37,-41,43,-47,-53,-59,61,-67,71}

    Returns: 535

  7. {-39, 27, -54, 25}

    Returns: 68

  8. {-28, 91, -62, 77, -47, -20, -51, 7, 23}

    Returns: 389

  9. {55, -33, 35, -80, 83, 87, -56, 16, 73, 20, -35, 45, 11, -12}

    Returns: 725

  10. {6, -9, -98, 29, -25, -33, -12, 42, 15, -46, 23, -1, 50, -61, 11, 77, 1, 34, 51}

    Returns: 797

  11. {-73, -43, -83, -92, -71, -95, -62, -48, -4, -94, 82, -22, -63, 41, -78, -2, 59, -17, -74, 8, 51, -27, 79, -15}

    Returns: 1314

  12. {33, 16, 43, 88, 15, -14, 71, -74, 59, -24, 0, -7, 81, 76, 80, -90, -49, 9, -43, 86, 60, 4, -66, -19, 41, 91, -15, -61, 53}

    Returns: 1524

  13. {-68, -7, -12, 43, -64, -65, 96, -98, 84, 50, 66, -52, 0, 80, 24, -83, 70, -82, -51, 62, -45, -70, -21, -97, 6, 14, -72, 86, -9, -40, -28, 34, -71, -86}

    Returns: 2246

  14. {-14, 81, 97, 98, 54, 43, -57, -84, 69, -93, 36, -88, 78, -39, -9, -61, 17, -48, 46, 92, -71, -46, 58, -95, -23, -52, 87, 4, 66, -87, -18, -36, 59, 35, 96, 38, 67, -69, -54}

    Returns: 2692

  15. {-98, -79, -44, -69, -26, -37, -43, -94, 91, 80, 27, 29, 56, 63, 46, 66, 95, -73, -49, 74, 100, -92, -75, -29, -53, -16, -60, 44, 90, 57, 94, -85, -78, -9, 89, 20, 83, 22, 28, 32, -8, -57, -45, -22}

    Returns: 2004

  16. {-94, -67, 62, 97, 57, 44, -21, 47, -20, -91, 83, -72, -75, -55, 3, 32, 52, -53, 84, -85, 10, 45, 89, 1, 53, -96, 61, -16, -35, 51, -51, 25, -24, 39, -19, 43, -15, -65, 13, 65, 33, -4, -76, 7, -73, -100, 60, 16, -82}

    Returns: 3158

  17. {-40, -13, 4}

    Returns: 44

  18. {-99, -96, -79, -44, -37, -26, 9, 79}

    Returns: 178

  19. {-96, -93, -62, -29, -21, 2, 28, 30, 31, 63, 86, 98, 100}

    Returns: 196

  20. {-91, -66, -50, -36, -29, -17, -10, -8, 19, 20, 29, 49, 57, 66, 90, 91, 94, 95}

    Returns: 186

  21. {-88, -86, -59, -57, -31, -27, -24, -23, -20, -13, -7, 0, 13, 17, 19, 26, 36, 44, 45, 82, 87, 97, 98}

    Returns: 186

  22. {-96, -93, -54, -50, -49, -47, -40, -29, -19, -11, -1, 8, 11, 20, 24, 27, 29, 30, 34, 40, 51, 57, 61, 63, 67, 71, 74, 83}

    Returns: 179

  23. {-87, -79, -75, -72, -70, -68, -65, -60, -52, -41, -40, -38, -32, -29, -23, -14, -5, -3, -1, 12, 19, 25, 27, 31, 37, 59, 60, 63, 69, 76, 86, 95, 100}

    Returns: 187

  24. {-99, -96, -94, -87, -81, -80, -77, -73, -57, -54, -52, -49, -40, -31, -28, -27, -22, -9, -7, -1, 2, 9, 10, 15, 17, 19, 20, 30, 46, 49, 51, 69, 71, 76, 78, 84, 85, 97}

    Returns: 196

  25. {-98, -83, -81, -79, -76, -75, -73, -71, -68, -58, -54, -51, -40, -37, -21, -10, -7, 5, 9, 10, 12, 17, 23, 24, 25, 26, 27, 43, 44, 45, 47, 51, 52, 57, 66, 68, 69, 70, 83, 85, 86, 91, 92}

    Returns: 190

  26. {-95, -94, -93, -89, -85, -81, -80, -75, -74, -69, -66, -57, -53, -51, -49, -47, -32, -19, -18, -16, -15, -8, -7, -6, -5, 0, 2, 13, 16, 18, 22, 26, 32, 36, 40, 42, 50, 62, 68, 72, 74, 80, 82, 86, 92, 96, 98, 100}

    Returns: 195

  27. {-93, -1, -52, 46, -66}

    Returns: 157

  28. {18, -83, -30, -98, 43, -8, 74, -84, -72, -89}

    Returns: 519

  29. {55, 63, -19, 4, -74, -22, -99, 62, -62, 14, -26, 82, 26, 57, -97}

    Returns: 822

  30. {-58, 37, 22, 55, -31, 83, -46, 46, -41, 81, -36, 48, 23, 41, -33, -8, -70, 70, -1, 33}

    Returns: 1189

  31. {-42, -96, -50, -62, -60, -91, -16, -29, 99, -70, -46, -73, 70, -3, 83, -54, 79, -18, 56, -22, 12, 8, 94, 11, 27}

    Returns: 1359

  32. {40, 65, -63, 36, -95, 35, -42, 28, -44, 59, 53, 75, -49, 61, 54, 82, -34, 51, 3, 19, -50, -48, -64, -13, -41, 62, -80, -18, -53, 100}

    Returns: 1798

  33. {-47, -60, -18, -30, 9, -81, 59, 56, 99, -29, 51, 48, 97, 80, 83, 43, 78, 44, 85, 10, 75, -66, 20, -43, 64, -78, -46, -68, -59, -85, -1, -22, -8, -95, 100}

    Returns: 1767

  34. {13, 38, 27, 64, -32, -10, -44, 10, -51, 51, 26, 59, -61, 31, -65, 52, 25, 43, -34, 74, 15, 71, -25, -6, -55, 54, -82, 57, 29, 87, -8, 99, 40, 63, -93, -87, -90, 22, -75, 2}

    Returns: 2367

  35. {-78, -11, -40, 61, 27, 62, 26, 68, -76, 79, -81, 88, -82, -50, -64, -49, -68, -65, -94, 14, -29, 28, -47, 86, -35, 71, 48, 89, -46, 18, -53, -33, -71, -27, -43, -20, -45, -6, -93, 19, -100, -75, -96, -89, -90}

    Returns: 2470

  36. {70, -98, -95, -97, 31, -27, 20, -30, 77, 67, 74, -79, -49, -55, 25, -4, 2, -67, -14, -37, 6, -36, 95, -12, 17, -80, -3, -66, 82, 3, 28, 15, 91, -19, 59, -26, -7, -60, -22, -76, -45, -78, 84, -52, 78, -20, 52, 32, 51, -53}

    Returns: 2929

  37. {4, -9, -26}

    Returns: 30

  38. {-12, 62, 73, -77}

    Returns: 213

  39. {89, -70, -73, -53, 94}

    Returns: 323

  40. {-11, -2, 4}

    Returns: 15

  41. {-55, 14, 87, 94}

    Returns: 149

  42. {-65, 3, 55, 81, 83}

    Returns: 148

  43. {-27, -12, -95, -4, -31, 66, -67, 6, -89, 91, -79, -44, -85, -30, -69, -8, -70, 87, -3, -1, -49, -14, -97, -75, -90, 78, 12, 33, -84, 29, 1, 62, -68, 23, -64, 100, -21, 25, -59, 36, -92, 31, -35, 55, -15, 54, -54, -16, -65, 41}

    Returns: 3608

  44. {-29, 23, -75, -8, -43, 50, -25, 3, -57, -35, -44, 5, -85, 70, 46, 77, -45, 94, 14, 64, -61, -16, -70, 18, 6, 30, -59, 60, -77, 8, -52, 31, 11, 86, -78, 54, 51, 87, -95, 9, -46, 82, 76, 97, 28, 98, -96, -41, -56, -1}

    Returns: 3320

  45. {-38, 21, 12, 87, -99, 17, -24, 56, 11, 16, -76, 81, 63, 88, 10, 59, 31, 89, 6, 58, -7, 19, -39, 40, -57, -36, -47, 72, -44, 53, -77, 92, -56, 91, 5, 73, 49, 94, -71, -17, -48, 43, -12, -10, -64, -42, -51, 55, 13, 90}

    Returns: 3174

  46. {100, -100, 99, -99, 98, -98, 97, -97, 96, -96, 95, -95, 94, -94, 93, -93, 92, -92, 91, -91, 90, -90, 89, -89, 88, -88, 87, -87, 86, -86, 85, -85, 84, -84, 83, -83, 82, -82, 81, -81, 80, -80, 79, -79, 78, -78, 77, -77, 76, -76}

    Returns: 8226

  47. {100, -100, 99, -99, 98, -98, 97, -97, 96, -96, 95, -95, 94, -94, 93, -93, 92, -92, 91, -91, 90, -90, 89, -89, 88, -88, 87, -87, 86, -86, 85, -85, 84, -84, 83, -83, 82, -82, 81, -81, 80, -80, 79, -79, 78, -78, 77, -77, 76}

    Returns: 8074

  48. {1, 4, -1, 3 }

    Returns: 4

  49. {-100, 99, -98, 97, -96, 95, -94, 93, -92, 91, -90, 89, -88, 87, -86, 85, -84, 83, -82, 81, -80, 79, -78, 77, -76, 75, -74, 73, -72, 71, -70, 69, -68, 67, -66, 65, -64, 63, -62, 61, -60, 59, -58, 57, -56, 55, -54, 53, -52, 51 }

    Returns: 7005

  50. {-2, 4, 3 }

    Returns: 5

  51. {0, 20, 10, -1, 11, 31 }

    Returns: 51

  52. {100, -100, 99, -99, 98, -98, 97, -97, 96, -96, 95, -95, 94, -94, 93, -93, 92, -92, 91, -91, 90, -90, 89, -89, 88, -88, 87, -87, 86, -86, 85, -85, 84, -84, 83, -83, 82, -82, 81, -81, 80, -80, 79, -79, 78, -78, 77, -77, 76 }

    Returns: 8074

  53. {100, -100, 99, -99, 98, -98, 97, -97, 96, -96, 95, -95, -94, 94, -93, 93, -92, 92, -91, 91, -90, 90, -89, 89 }

    Returns: 3761

  54. {1, 2, 3, 10 }

    Returns: 9

  55. {74, 84, 92, 23, 5, -70, -47, -59, 24, -86, -39, 99, 85, -42, 54, 100, 47, -3, 42, 38 }

    Returns: 836

  56. {-100, 100, -99, 99, -98, 98, -97, 97, -96, 96, -95, 95, -94, 94, -93, 93, -92, 92, -91, 91, -90, 90, -89, 89, -88, 88, -87, 87, -86, 86, -85, 85, -84, 84, -83, 83, -82, 82, -81, 81, -80, 80, -79, 79, -78, 78, -77, 77, -76, 76 }

    Returns: 8226

  57. {10, 15, 20 }

    Returns: 10

  58. {-5, -6, 0, 5, 3, 4 }

    Returns: 11

  59. {0, -3, 4, 6 }

    Returns: 6

  60. {1, 2, 10, 30, 50, 80 }

    Returns: 79

  61. {0, 1, 2, 3, 50, 51, 52, 53 }

    Returns: 53

  62. {0, 1, 2 }

    Returns: 2

  63. {1, 5, 4, 2, 3 }

    Returns: 6

  64. {1, 4, 6, 5 }

    Returns: 4

  65. {1, 20, 50 }

    Returns: 49

  66. {1, 2, 3, 4, 5, 100 }

    Returns: 99

  67. {3, 2, 11, 13 }

    Returns: 10

  68. {10, 20, 30, 31, 38, 32, 33 }

    Returns: 23

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: