Statistics

Problem Statement for "ConvexArray"

Problem Statement

An array of integers is called convex if all of the following apply:

  • It contains an even number of elements.
  • It contains between 6 and 50 elements, inclusive.
  • Each element is an integer between 1 and 50, inclusive. Interpret the integers as the coordinates of n points: x_1, y_1, x_2, y_2, ..., x_n, y_n (in this order).
  • These n points are vertices of a convex polygon.
  • The vertices are listed in either clockwise or counterclockwise order.
  • No three consecutive vertices lie on the same straight line (when saying three consecutive vertices we also mean vertices number N, 1 and 2 and vertices number N-1, N and 1).

Given a int[] beginning, find the shortest int[] that will produce a valid convex array when appended to the end of beginning. If there are multiple such int[]s, return the one among them that comes first lexicographically. If there is no such int[], return a int[] containing a single element -1.

Definition

Class:
ConvexArray
Method:
getEnding
Parameters:
int[]
Returns:
int[]
Method signature:
int[] getEnding(int[] beginning)
(be sure your method is public)

Constraints

  • beginning will contain between 0 and 50 elements, inclusive.
  • Each element of beginning will be between 1 and 50, inclusive.

Examples

  1. {1, 1, 2, 2}

    Returns: {1, 2 }

    The polygon must contain at least 3 points, so we need to add at least one more. Adding (1, 1) would give us a segment, not a polygon, thus we stick to the next lexicographical point which is (1, 2).

  2. {5, 6, 6}

    Returns: {1, 1, 1 }

    It is possible that the x coordinate is given and you have to choose the y coordinate.

  3. {1, 3}

    Returns: {1, 1, 2, 1 }

    (1, 1, 1, X) would form a segment, not a triangle. Move on to the next lexicographical quadruple, (1, 1, 2, 1).

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

    Returns: {1 }

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

    Returns: {4 }

    We need to find the y coordinate for the last vertex that will generate a convex polygon. Points (3, 1) and (3, 2) would make the polygon non-convex. Point (3, 3) would break the rules because there would be three consecutive vertices on the same straight line. Point (3, 4) is the only valid choice.

  6. {}

    Returns: {1, 1, 1, 2, 2, 1 }

  7. {1}

    Returns: {1, 1, 2, 2, 1 }

  8. {2}

    Returns: {1, 1, 1, 1, 2 }

  9. {50}

    Returns: {1, 1, 1, 1, 2 }

  10. {1, 1}

    Returns: {1, 2, 2, 1 }

  11. {1, 2}

    Returns: {1, 1, 2, 1 }

  12. {2, 1}

    Returns: {1, 1, 1, 2 }

  13. {5, 6}

    Returns: {1, 1, 1, 2 }

  14. {1, 1, 1}

    Returns: {2, 2, 1 }

  15. {1, 1, 2}

    Returns: {1, 1, 2 }

  16. {1, 2, 1}

    Returns: {1, 2, 1 }

  17. {1, 2, 2}

    Returns: {1, 1, 1 }

  18. {1, 10, 1}

    Returns: {1, 2, 1 }

  19. {1, 50, 49}

    Returns: {1, 1, 1 }

  20. {2, 1, 1}

    Returns: {1, 1, 2 }

  21. {2, 1, 2}

    Returns: {2, 1, 1 }

  22. {2, 1, 4}

    Returns: {1, 1, 2 }

  23. {2, 2, 1}

    Returns: {1, 1, 2 }

  24. {2, 2, 2}

    Returns: {1, 1, 1 }

  25. {2, 40, 50}

    Returns: {1, 1, 1 }

  26. {3, 1, 1}

    Returns: {1, 1, 2 }

  27. {3, 1, 3}

    Returns: {2, 1, 1 }

  28. {3, 3, 1}

    Returns: {1, 1, 2 }

  29. {3, 40, 6}

    Returns: {1, 1, 1 }

  30. {5, 1, 1}

    Returns: {1, 1, 2 }

  31. {7, 1, 8}

    Returns: {1, 1, 2 }

  32. {1, 1, 2, 2}

    Returns: {1, 2 }

  33. {1, 1, 1, 10}

    Returns: {2, 1 }

  34. {3, 3, 5, 5}

    Returns: {1, 2 }

  35. {49, 49, 50, 50}

    Returns: {1, 2 }

  36. {1, 7, 1, 19}

    Returns: {2, 1 }

  37. {1, 50, 50, 1}

    Returns: {1, 1 }

  38. {35, 1, 15, 1, 25}

    Returns: {2 }

  39. {5, 4, 7, 7, 3}

    Returns: {2 }

  40. {8, 1, 24, 1, 3}

    Returns: {2 }

  41. {1, 50, 20, 32, 50}

    Returns: {1 }

  42. {23, 24, 25, 26, 27, 29}

    Returns: { }

  43. {5, 1, 24, 21, 46, 42}

    Returns: { }

  44. {10, 1, 20, 1, 15, 10, 12}

    Returns: {5 }

  45. {33, 20, 41, 10, 48, 20, 41}

    Returns: {21 }

  46. {9, 2, 8, 3, 9, 16, 10}

    Returns: {2 }

  47. {1, 1, 5, 2, 10, 5, 15}

    Returns: {9 }

  48. {1, 1, 2, 1, 4, 12, 5}

    Returns: {18 }

  49. {4, 4, 4, 6, 6, 6, 6}

    Returns: {1 }

  50. {2, 6, 5, 48, 43, 33, 35, 12}

    Returns: { }

  51. {23, 21, 21, 21, 21, 23, 23, 23, 24}

    Returns: {22 }

  52. {5, 49, 3, 31, 9, 28, 7, 49, 6}

    Returns: {50 }

  53. {30, 20, 20, 10, 10, 20, 20, 30, 25}

    Returns: {26 }

  54. {1, 1, 5, 6, 9, 8, 5, 3, 4}

    Returns: {2 }

  55. {2, 50, 1, 49, 1, 2, 2, 1, 49, 1, 50, 2, 50, 49, 3}

    Returns: {50 }

  56. {10, 37, 11, 46, 1, 1, 2, 1, 3, 2, 4, 4, 5, 7, 6, 11, 7, 16, 8, 22, 9}

    Returns: {29 }

  57. {12, 42, 16, 46, 21, 49, 26, 50, 30, 49, 35, 46, 39, 42, 43, 36, 46, 28, 48, 20, 50, 11, 50, 10, 49, 9, 47, 8, 44, 7, 40, 6, 29, 4, 22, 3, 14, 2, 5, 1, 1, 1, 1, 11, 3, 20, 5, 28, 8}

    Returns: {35 }

  58. {45, 25, 42, 35, 35, 42, 25, 45, 15, 42, 8, 35, 5, 25, 8, 15, 15, 8, 25, 5, 35, 8, 42, 15, 44}

    Returns: {18 }

  59. {41, 49, 33, 47, 25, 43, 17, 37, 9, 28, 1, 1, 25, 25, 49}

    Returns: {50 }

  60. {1, 1, 2, 4, 3, 9, 4, 16, 5, 25, 6, 36, 7, 49}

    Returns: { }

  61. {1, 1, 2, 4, 3, 9, 4, 16, 5, 25, 6, 36, 7, 49, 3}

    Returns: {18 }

  62. {40, 30, 20, 30, 10, 31, 20, 32, 40, 32, 50}

    Returns: {31 }

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

    Returns: {-1 }

    No matter what the last y-coordinate is, the edge (1, 1)-(2, 3) intersects the edge (3, 1)-(1, 2), so there is no convex polygon possible.

  64. {1, 1, 1, 1}

    Returns: {-1 }

  65. {23, 9, 23, 9}

    Returns: {-1 }

  66. {50, 50, 50, 50}

    Returns: {-1 }

  67. {50, 50, 50, 50, 23}

    Returns: {-1 }

  68. {12, 6, 12, 48, 12}

    Returns: {-1 }

  69. {30, 50, 38, 48, 39, 49, 40}

    Returns: {-1 }

  70. {5, 1, 7, 3, 8, 2, 9}

    Returns: {-1 }

  71. {2, 2, 2, 4, 4, 4, 4, 2, 2, 2, 2, 4, 4, 4, 4, 2}

    Returns: {-1 }

  72. {1, 1, 1, 9, 5, 9, 5, 5, 1, 5, 1, 9, 5, 9, 5, 1}

    Returns: {-1 }

  73. {20, 20, 20, 30, 30, 30, 30, 20, 20, 20, 20, 28, 28, 28, 28, 20}

    Returns: {-1 }

  74. {25, 1, 23, 5, 25, 7, 27, 5, 25, 1, 10, 8, 24, 14, 40}

    Returns: {-1 }

  75. {6, 1, 5, 2, 7, 5, 9, 2, 8, 1, 7}

    Returns: {-1 }

  76. {3, 14, 15, 9, 2, 6, 5, 35, 8, 9, 7, 9}

    Returns: {-1 }

  77. {4, 4, 8, 6, 8, 4, 4, 6, 4, 8, 5}

    Returns: {-1 }

  78. {5, 6, 6, 6, 7, 7, 8, 8, 9}

    Returns: {-1 }

  79. {10, 10, 50, 1, 50, 50, 1, 50, 1, 1, 20, 2, 15}

    Returns: {-1 }

  80. {4, 6, 4, 3, 7, 3, 7, 7, 3, 7, 3, 4, 5}

    Returns: {-1 }

  81. {50, 25, 44, 39, 32, 46, 18, 44, 10, 35, 10, 25, 16, 18, 22, 16, 26, 19, 29, 22, 30, 25, 29, 27, 26, 30, 22, 33, 16, 31, 11, 25, 10, 14, 18, 5, 32, 3, 44, 10}

    Returns: {-1 }

  82. {44, 24, 34, 39, 15, 40, 4, 26, 10, 10, 29, 6, 43, 18, 39, 35, 21, 41, 5, 31, 7, 14, 24, 6, 40, 14, 42, 31, 26, 41}

    Returns: {-1 }

  83. {1, 25, 5, 37, 14, 45, 26, 47, 36, 43, 43, 35, 45, 25, 42, 16, 35, 10, 26, 9, 19, 12, 14, 18, 13, 25, 16, 31, 20, 35, 26, 35, 30, 33, 33, 29, 33, 25, 14}

    Returns: {-1 }

  84. {25, 1, 34, 3, 42, 8, 47, 16, 49, 25, 47, 34, 41, 41, 34, 46, 25, 48, 16, 46, 9, 41, 4, 34, 3, 25, 5, 17, 9, 9, 17, 5, 25, 3, 33, 5, 40, 10, 44, 17, 46, 25, 30}

    Returns: {-1 }

  85. {1, 25, 25, 3, 45, 25, 25, 43, 9, 25, 25, 11, 37, 25, 25}

    Returns: {-1 }

  86. {2, 1, 2 }

    Returns: {2, 1, 1 }

  87. {1 }

    Returns: {1, 1, 2, 2, 1 }

  88. { }

    Returns: {1, 1, 1, 2, 2, 1 }

  89. {50, 50, 1, 1, 1, 2 }

    Returns: { }

  90. {1, 1, 1, 2, 2, 2, 2, 1 }

    Returns: { }

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: