Statistics

Problem Statement for "LuckyCycle"

Problem Statement

This problem is about trees. A tree consists of some special points (called nodes), and some lines (called edges) that connect those points. Each edge connects exactly two nodes. If there are N nodes in a tree, there are exactly N-1 edges. The edges of a tree must connect the nodes in such a way that the tree is connected: it must be possible to get from any node to any other node by traversing some sequence of edges. Note that this implies that a tree never contains a cycle: for each pair of nodes there is exactly one way to reach one from the other without using the same edge twice.


Dog has a tree. The edges in Dog's tree have weights. As Dog likes the numbers 4 and 7, the weight of each edge is either 4 or 7.


Cat loves modifying trees. Cat is now going to modify Dog's tree by adding one new edge. The new edge will also have a weight that is either 4 or 7. The new edge will connect two nodes that don't already have an edge between them. Note that adding any such edge will create exactly one cycle somewhere in the tree. (A cycle is a sequence of consecutive edges that starts and ends in the same node.)


A cycle is balanced if the number of edges on the cycle is even, and among them the number of edges with weight 4 is the same as the number of edges with weight 7. Cat would like to add the new edge in such a way that the cycle it creates will be balanced.


You are given the description of Dog's current tree in int[]s edge1, edge2, and weight. Each of these int[]s will have exactly n-1 elements, where n is the number of nodes in Dog's tree. The nodes in Dog's tree are labeled 1 through n. For each valid i, Dog's tree contains an edge that connects the nodes edge1[i] and edge2[i], and the weight of this edge is weight[i].


Return a int[] with exactly three elements: {P,Q,W}. Here, P and Q should be the nodes connected by the new edge, and W should be the weight of the new edge. (Note that P and Q must be between 1 and N, inclusive, and W must be either 4 or 7.) If there are multiple solutions, return any of them. If there are no solutions, return an empty int[] instead.

Definition

Class:
LuckyCycle
Method:
getEdge
Parameters:
int[], int[], int[]
Returns:
int[]
Method signature:
int[] getEdge(int[] edge1, int[] edge2, int[] weight)
(be sure your method is public)

Constraints

  • N will be between 2 and 100, inclusive.
  • edge1, edge2, and weight will each contain exactly N-1 elements.
  • Each element of weight will be either 4 or 7
  • Each element of edge1 and edge2 will be between 1 and N, inclusive.
  • The input will define a tree.

Examples

  1. {1}

    {2}

    {4}

    Returns: { }

    We cannot add any edge because the only two nodes are already connected by an edge.

  2. {1, 3, 2, 4}

    {2, 2, 4, 5}

    {4, 7, 4, 7}

    Returns: {1, 5, 7 }

    The input describes a tree with 5 nodes. The tree contains the following edges: 1-2 (weight 4), 3-2 (weight 7), 2-4 (weight 4), and 4-5 (weight 7). The example return value describes a new edge that connects nodes 1 and 5, and has weight 7. Adding the new edge creates a cycle that goes through the nodes 1, 2, 4, and 5, in this order. This cycle is balanced: two of its four edges have weight 4 and the other two have weight 7.

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

    {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}

    {4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7}

    Returns: {1, 12, 7 }

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

    {2, 3, 4, 3, 5}

    {4, 7, 7, 7, 7}

    Returns: {1, 4, 4 }

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

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

    {4, 4, 4, 4, 4, 4, 4}

    Returns: { }

  6. {1, 2, 2}

    {2, 4, 3}

    {4, 4, 7}

    Returns: { }

  7. {1, 4, 3, 2}

    {2, 5, 4, 3}

    {4, 4, 7, 4}

    Returns: {1, 4, 7 }

  8. {1, 4, 3, 2}

    {2, 5, 4, 3}

    {7, 7, 4, 7}

    Returns: {1, 4, 4 }

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

    {13, 2, 7, 5, 3, 12, 4, 11, 6, 9, 8, 10}

    {4, 7, 7, 4, 7, 4, 4, 4, 7, 7, 7, 4}

    Returns: {2, 7, 4 }

  10. {11, 33, 72, 92, 14, 61, 10, 55, 24, 94, 80, 84, 2, 85, 48, 73, 95, 51, 58, 86, 82, 71, 17, 20, 54, 1, 41, 88, 70, 68, 63, 96, 32, 43, 22, 52, 62, 9, 13, 6, 8, 60, 46, 5, 18, 50, 69, 21, 47, 15, 77, 35, 49, 64, 99, 42, 28, 91, 75, 79, 37, 44, 19, 27, 93, 38, 39, 81, 90, 29, 67, 7, 40, 12, 56, 25, 53, 16, 59, 78, 30, 89, 23, 87, 36, 76, 31, 45, 83, 66, 34, 4, 3, 26, 57, 74, 98, 97, 65}

    {12, 34, 73, 93, 15, 62, 11, 56, 25, 95, 81, 85, 3, 86, 49, 74, 96, 52, 59, 87, 83, 72, 18, 21, 55, 2, 42, 89, 71, 69, 64, 97, 33, 44, 23, 53, 63, 10, 14, 7, 9, 61, 47, 6, 19, 51, 70, 22, 48, 16, 78, 36, 50, 65, 100, 43, 29, 92, 76, 80, 38, 45, 20, 28, 94, 39, 40, 82, 91, 30, 68, 8, 41, 13, 57, 26, 54, 17, 60, 79, 31, 90, 24, 88, 37, 77, 32, 46, 84, 67, 35, 5, 4, 27, 58, 75, 99, 98, 66}

    {4, 4, 7, 7, 7, 4, 7, 4, 7, 7, 7, 7, 7, 4, 7, 4, 4, 4, 7, 7, 7, 4, 4, 7, 7, 4, 4, 7, 7, 7, 4, 7, 7, 4, 7, 7, 7, 4, 4, 7, 7, 7, 7, 4, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 4, 7, 7, 4, 4, 4, 4, 7, 4, 4, 4, 7, 4, 4, 7, 4, 4, 4, 7, 7, 7, 4, 4, 7, 4, 7, 7, 4, 4, 4, 7, 7, 4, 4, 4, 7, 7, 7, 4, 7, 4, 7, 7, 4, 4}

    Returns: {1, 4, 7 }

  11. {60, 37, 99, 15, 48, 42, 65, 72, 40, 51, 75, 36, 85, 94, 41, 8, 69, 34, 81, 10, 74, 4, 19, 76, 80, 12, 56, 66, 63, 29, 45, 3, 52, 50, 96, 86, 26, 7, 32, 47, 92, 64, 57, 2, 33, 11, 55, 17, 73, 87, 1, 49, 22, 6, 67, 98, 71, 14, 13, 27, 77, 61, 44, 95, 83, 20, 79, 93, 30, 21, 54, 91, 9, 62, 89, 38, 97, 82, 68, 35, 84, 90, 25, 53, 43, 59, 24, 16, 18, 58, 88, 78, 46, 5, 39, 23, 70, 28, 31}

    {61, 38, 100, 16, 49, 43, 66, 73, 41, 52, 76, 37, 86, 95, 42, 9, 70, 35, 82, 11, 75, 5, 20, 77, 81, 13, 57, 67, 64, 30, 46, 4, 53, 51, 97, 87, 27, 8, 33, 48, 93, 65, 58, 3, 34, 12, 56, 18, 74, 88, 2, 50, 23, 7, 68, 99, 72, 15, 14, 28, 78, 62, 45, 96, 84, 21, 80, 94, 31, 22, 55, 92, 10, 63, 90, 39, 98, 83, 69, 36, 85, 91, 26, 54, 44, 60, 25, 17, 19, 59, 89, 79, 47, 6, 40, 24, 71, 29, 32}

    {4, 7, 4, 4, 4, 4, 7, 7, 7, 4, 7, 7, 4, 4, 4, 4, 7, 7, 4, 4, 7, 4, 4, 7, 7, 4, 4, 7, 7, 7, 4, 4, 4, 4, 4, 4, 7, 4, 7, 4, 4, 7, 4, 4, 7, 4, 4, 4, 7, 4, 4, 4, 7, 4, 7, 4, 7, 4, 4, 7, 7, 7, 4, 4, 4, 4, 7, 4, 7, 7, 4, 4, 4, 7, 4, 7, 4, 4, 7, 7, 4, 4, 7, 4, 4, 4, 7, 4, 4, 4, 4, 7, 4, 4, 7, 7, 7, 7, 7}

    Returns: {1, 40, 7 }

  12. {88, 46, 4, 2, 5, 18, 63, 83, 17, 20, 73, 76, 6, 25, 82, 69, 10, 93, 56, 11, 65, 9, 22, 42, 64, 85, 84, 41, 48, 30, 44, 51, 50, 92, 35, 12, 95, 79, 24, 100, 15, 16, 39, 89, 70, 72, 45, 74, 49, 37, 13, 43, 38, 36, 26, 61, 87, 14, 58, 53, 99, 81, 66, 31, 47, 80, 62, 57, 75, 23, 98, 94, 34, 78, 91, 27, 21, 40, 32, 71, 19, 33, 8, 3, 54, 77, 29, 97, 60, 52, 96, 90, 67, 68, 55, 86, 7, 59, 28}

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

    {4, 4, 4, 4, 7, 4, 7, 7, 7, 4, 7, 4, 4, 7, 4, 7, 4, 7, 4, 7, 7, 7, 4, 4, 4, 7, 4, 7, 4, 4, 4, 7, 4, 4, 7, 4, 7, 7, 4, 4, 7, 4, 7, 7, 4, 4, 7, 4, 7, 7, 7, 7, 4, 4, 4, 7, 7, 4, 4, 7, 7, 7, 4, 7, 7, 4, 4, 7, 7, 7, 4, 4, 4, 4, 7, 7, 7, 4, 4, 7, 7, 7, 4, 7, 4, 7, 7, 7, 4, 4, 4, 4, 7, 4, 7, 4, 7, 7, 4}

    Returns: {1, 9, 7 }

  13. {20, 83, 10, 55, 70, 11, 46, 90, 61, 25, 21, 14, 17, 84, 12, 92, 6, 79, 4, 27, 62, 71, 9, 57, 69, 54, 58, 39, 91, 56, 98, 86, 8, 59, 96, 75, 94, 99, 42, 29, 87, 80, 60, 2, 85, 76, 31, 93, 22, 81, 73, 15, 43, 32, 51, 65, 41, 24, 64, 74, 45, 35, 19, 50, 3, 23, 66, 28, 34, 33, 63, 7, 37, 36, 5, 26, 52, 49, 30, 44, 95, 67, 47, 82, 77, 53, 88, 100, 78, 48, 13, 18, 40, 97, 38, 68, 16, 89, 72}

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

    {7, 4, 4, 4, 7, 4, 4, 4, 7, 7, 7, 4, 4, 4, 4, 4, 4, 7, 4, 7, 7, 7, 4, 4, 7, 4, 4, 7, 4, 4, 4, 4, 4, 4, 4, 7, 4, 4, 4, 7, 4, 4, 7, 4, 4, 7, 7, 4, 7, 4, 7, 4, 4, 7, 4, 7, 4, 7, 7, 7, 4, 7, 4, 4, 4, 7, 7, 7, 7, 7, 7, 4, 7, 7, 4, 7, 4, 4, 7, 4, 4, 7, 4, 4, 7, 4, 4, 7, 7, 4, 4, 4, 4, 4, 7, 7, 4, 4, 7}

    Returns: {1, 62, 7 }

  14. {35, 94, 53, 18, 66, 14, 87, 56, 96, 57, 15, 4, 77, 11, 9, 71, 61, 21, 68, 48, 46, 12, 65, 89, 44, 59, 86, 63, 82, 37, 54, 55, 2, 24, 58, 50, 30, 84, 70, 6, 67, 52, 90, 93, 47, 49, 81, 97, 13, 7, 64, 33, 16, 76, 31, 62, 91, 92, 83, 27, 85, 8, 75, 51, 20, 98, 74, 19, 1, 40, 79, 78, 43, 69, 99, 3, 41, 25, 60, 28, 42, 23, 38, 39, 22, 29, 10, 73, 80, 5, 88, 36, 34, 95, 26, 32, 45, 72, 17}

    {36, 95, 54, 19, 67, 15, 88, 57, 97, 58, 16, 5, 78, 12, 10, 72, 62, 22, 69, 49, 47, 13, 66, 90, 45, 60, 87, 64, 83, 38, 55, 56, 3, 25, 59, 51, 31, 85, 71, 7, 68, 53, 91, 94, 48, 50, 82, 98, 14, 8, 65, 34, 17, 77, 32, 63, 92, 93, 84, 28, 86, 9, 76, 52, 21, 99, 75, 20, 2, 41, 80, 79, 44, 70, 100, 4, 42, 26, 61, 29, 43, 24, 39, 40, 23, 30, 11, 74, 81, 6, 89, 37, 35, 96, 27, 33, 46, 73, 18}

    {4, 7, 4, 4, 4, 7, 4, 7, 4, 7, 4, 4, 4, 4, 4, 7, 4, 7, 7, 7, 7, 7, 4, 4, 4, 7, 7, 7, 4, 4, 7, 4, 7, 4, 7, 7, 4, 7, 4, 4, 7, 4, 4, 4, 7, 4, 4, 7, 7, 4, 4, 4, 7, 7, 4, 7, 4, 7, 7, 7, 7, 7, 7, 4, 7, 7, 4, 7, 7, 4, 4, 7, 4, 4, 7, 7, 4, 7, 7, 4, 7, 7, 4, 4, 7, 4, 4, 7, 7, 7, 7, 7, 7, 4, 7, 4, 7, 4, 7}

    Returns: {1, 8, 4 }

  15. {40, 43, 36, 23, 7, 22, 56, 62, 63, 69, 21, 11, 60, 16, 18, 26, 3, 92, 84, 2, 14, 25, 87, 45, 57, 99, 68, 51, 85, 15, 24, 77, 41, 13, 79, 80, 4, 48, 72, 47, 65, 19, 74, 49, 88, 98, 8, 76, 61, 67, 9, 71, 46, 58, 37, 89, 34, 52, 53, 17, 83, 93, 33, 59, 55, 97, 44, 81, 32, 31, 38, 96, 50, 20, 1, 28, 70, 35, 30, 73, 75, 64, 5, 95, 86, 82, 29, 39, 94, 10, 54, 91, 12, 27, 66, 78, 42, 90, 6}

    {41, 44, 37, 24, 8, 23, 57, 63, 64, 70, 22, 12, 61, 17, 19, 27, 4, 93, 85, 3, 15, 26, 88, 46, 58, 100, 69, 52, 86, 16, 25, 78, 42, 14, 80, 81, 5, 49, 73, 48, 66, 20, 75, 50, 89, 99, 9, 77, 62, 68, 10, 72, 47, 59, 38, 90, 35, 53, 54, 18, 84, 94, 34, 60, 56, 98, 45, 82, 33, 32, 39, 97, 51, 21, 2, 29, 71, 36, 31, 74, 76, 65, 6, 96, 87, 83, 30, 40, 95, 11, 55, 92, 13, 28, 67, 79, 43, 91, 7}

    {7, 7, 7, 4, 4, 4, 4, 7, 7, 4, 4, 4, 7, 4, 7, 7, 4, 4, 7, 4, 4, 7, 7, 4, 7, 4, 4, 7, 7, 7, 7, 4, 7, 7, 7, 4, 4, 7, 4, 4, 7, 4, 4, 4, 4, 4, 4, 7, 4, 7, 4, 4, 4, 4, 4, 7, 7, 7, 4, 4, 4, 7, 4, 7, 4, 7, 4, 7, 4, 7, 7, 7, 4, 7, 7, 4, 4, 4, 4, 4, 7, 4, 4, 4, 7, 7, 4, 4, 4, 7, 7, 4, 4, 4, 7, 4, 7, 4, 7}

    Returns: {1, 4, 7 }

  16. {73, 75, 17, 37, 90, 69, 86, 47, 46, 27, 52, 60, 65, 71, 96, 98, 32, 70, 14, 64, 42, 34, 44, 7, 88, 91, 53, 77, 30, 63, 33, 89, 45, 24, 35, 10, 3, 81, 31, 83, 20, 38, 4, 79, 72, 25, 99, 8, 41, 6, 26, 48, 23, 19, 15, 22, 74, 12, 56, 43, 82, 39, 9, 13, 80, 93, 16, 94, 54, 18, 57, 95, 2, 29, 84, 67, 1, 28, 68, 58, 49, 5, 62, 87, 76, 97, 51, 61, 66, 92, 40, 36, 50, 59, 78, 11, 55, 21, 85}

    {74, 76, 18, 38, 91, 70, 87, 48, 47, 28, 53, 61, 66, 72, 97, 99, 33, 71, 15, 65, 43, 35, 45, 8, 89, 92, 54, 78, 31, 64, 34, 90, 46, 25, 36, 11, 4, 82, 32, 84, 21, 39, 5, 80, 73, 26, 100, 9, 42, 7, 27, 49, 24, 20, 16, 23, 75, 13, 57, 44, 83, 40, 10, 14, 81, 94, 17, 95, 55, 19, 58, 96, 3, 30, 85, 68, 2, 29, 69, 59, 50, 6, 63, 88, 77, 98, 52, 62, 67, 93, 41, 37, 51, 60, 79, 12, 56, 22, 86}

    {4, 7, 4, 4, 4, 4, 4, 7, 4, 7, 4, 4, 4, 7, 7, 7, 4, 4, 7, 7, 4, 7, 7, 4, 7, 7, 4, 7, 4, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 7, 7, 4, 7, 7, 7, 7, 4, 4, 7, 4, 4, 4, 4, 4, 7, 7, 4, 4, 7, 7, 4, 7, 7, 7, 7, 7, 7, 7, 7, 4, 7, 4, 7, 4, 4, 4, 4, 4, 7, 4, 4, 7, 4, 4, 4, 7, 7, 4, 4, 7, 4, 7, 4, 4, 4, 4, 4, 7, 7}

    Returns: {1, 4, 7 }

  17. {37, 91, 63, 45, 29, 10, 59, 58, 89, 97, 11, 9, 81, 92, 93, 53, 54, 90, 69, 88, 77, 62, 65, 52, 80, 23, 41, 55, 14, 64, 96, 44, 75, 76, 60, 6, 74, 46, 24, 5, 48, 84, 26, 22, 51, 99, 17, 78, 20, 98, 3, 50, 28, 38, 12, 30, 49, 16, 61, 33, 35, 66, 47, 27, 13, 83, 95, 94, 34, 67, 25, 86, 70, 21, 68, 19, 85, 57, 40, 82, 72, 79, 56, 31, 8, 42, 32, 87, 73, 1, 2, 18, 36, 71, 43, 7, 4, 15, 39}

    {38, 92, 64, 46, 30, 11, 60, 59, 90, 98, 12, 10, 82, 93, 94, 54, 55, 91, 70, 89, 78, 63, 66, 53, 81, 24, 42, 56, 15, 65, 97, 45, 76, 77, 61, 7, 75, 47, 25, 6, 49, 85, 27, 23, 52, 100, 18, 79, 21, 99, 4, 51, 29, 39, 13, 31, 50, 17, 62, 34, 36, 67, 48, 28, 14, 84, 96, 95, 35, 68, 26, 87, 71, 22, 69, 20, 86, 58, 41, 83, 73, 80, 57, 32, 9, 43, 33, 88, 74, 2, 3, 19, 37, 72, 44, 8, 5, 16, 40}

    {7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7}

    Returns: { }

  18. {20, 60, 83, 58, 61, 30, 65, 22, 55, 44, 15, 81, 73, 52, 46, 56, 41, 39, 36, 69, 9, 91, 8, 35, 96, 49, 68, 3, 66, 88, 50, 27, 37, 97, 87, 7, 45, 82, 75, 99, 34, 74, 89, 6, 84, 54, 38, 2, 23, 10, 16, 94, 40, 21, 62, 72, 12, 28, 24, 26, 71, 19, 78, 51, 11, 48, 47, 80, 33, 32, 98, 31, 5, 92, 76, 13, 85, 63, 64, 43, 77, 29, 86, 18, 57, 95, 70, 79, 59, 17, 4, 25, 53, 42, 93, 1, 14, 67, 90}

    {21, 61, 84, 59, 62, 31, 66, 23, 56, 45, 16, 82, 74, 53, 47, 57, 42, 40, 37, 70, 10, 92, 9, 36, 97, 50, 69, 4, 67, 89, 51, 28, 38, 98, 88, 8, 46, 83, 76, 100, 35, 75, 90, 7, 85, 55, 39, 3, 24, 11, 17, 95, 41, 22, 63, 73, 13, 29, 25, 27, 72, 20, 79, 52, 12, 49, 48, 81, 34, 33, 99, 32, 6, 93, 77, 14, 86, 64, 65, 44, 78, 30, 87, 19, 58, 96, 71, 80, 60, 18, 5, 26, 54, 43, 94, 2, 15, 68, 91}

    {4, 7, 7, 7, 7, 4, 7, 4, 7, 4, 4, 7, 7, 7, 4, 7, 4, 4, 4, 7, 4, 7, 4, 4, 7, 4, 7, 4, 7, 7, 4, 4, 4, 7, 7, 4, 4, 7, 7, 7, 4, 7, 7, 4, 7, 7, 4, 4, 4, 4, 4, 7, 4, 4, 7, 7, 4, 4, 4, 4, 7, 4, 7, 4, 4, 4, 4, 7, 4, 4, 7, 4, 4, 7, 7, 4, 7, 7, 7, 4, 7, 4, 7, 4, 7, 7, 7, 7, 7, 4, 4, 4, 7, 4, 7, 4, 4, 7, 7}

    Returns: {3, 100, 7 }

  19. {20, 73, 27, 17, 28, 85, 21, 1, 77, 52, 91, 79, 31, 94, 63, 16, 81, 51, 3, 36, 44, 25, 53, 57, 78, 76, 98, 96, 46, 6, 43, 39, 45, 75, 66, 93, 56, 22, 71, 88, 7, 92, 69, 4, 61, 82, 70, 90, 62, 65, 41, 14, 26, 23, 13, 11, 10, 97, 47, 55, 68, 30, 87, 89, 84, 12, 24, 8, 49, 83, 34, 58, 40, 42, 95, 60, 37, 32, 72, 59, 80, 54, 29, 74, 33, 19, 18, 48, 35, 67, 2, 99, 15, 64, 9, 5, 50, 86, 38}

    {21, 74, 28, 18, 29, 86, 22, 2, 78, 53, 92, 80, 32, 95, 64, 17, 82, 52, 4, 37, 45, 26, 54, 58, 79, 77, 99, 97, 47, 7, 44, 40, 46, 76, 67, 94, 57, 23, 72, 89, 8, 93, 70, 5, 62, 83, 71, 91, 63, 66, 42, 15, 27, 24, 14, 12, 11, 98, 48, 56, 69, 31, 88, 90, 85, 13, 25, 9, 50, 84, 35, 59, 41, 43, 96, 61, 38, 33, 73, 60, 81, 55, 30, 75, 34, 20, 19, 49, 36, 68, 3, 100, 16, 65, 10, 6, 51, 87, 39}

    {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4}

    Returns: { }

  20. {9, 20, 6, 73, 69, 3, 57, 66, 7, 83, 13, 90, 11, 25, 31, 16, 42, 53, 99, 32, 30, 87, 71, 91, 61, 75, 96, 70, 88, 34, 82, 8, 2, 12, 1, 77, 43, 50, 98, 14, 80, 26, 37, 46, 95, 51, 5, 45, 60, 27, 76, 85, 79, 24, 17, 74, 40, 58, 18, 78, 93, 29, 55, 39, 41, 84, 15, 48, 67, 86, 72, 36, 35, 81, 89, 19, 56, 4, 97, 33, 64, 94, 68, 10, 59, 44, 49, 62, 92, 21, 47, 52, 38, 54, 65, 23, 28, 63, 22}

    {10, 21, 7, 74, 70, 4, 58, 67, 8, 84, 14, 91, 12, 26, 32, 17, 43, 54, 100, 33, 31, 88, 72, 92, 62, 76, 97, 71, 89, 35, 83, 9, 3, 13, 2, 78, 44, 51, 99, 15, 81, 27, 38, 47, 96, 52, 6, 46, 61, 28, 77, 86, 80, 25, 18, 75, 41, 59, 19, 79, 94, 30, 56, 40, 42, 85, 16, 49, 68, 87, 73, 37, 36, 82, 90, 20, 57, 5, 98, 34, 65, 95, 69, 11, 60, 45, 50, 63, 93, 22, 48, 53, 39, 55, 66, 24, 29, 64, 23}

    {7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7}

    Returns: { }

  21. {51, 3, 27, 31, 97, 5, 94, 65, 52, 54, 24, 84, 90, 57, 69, 2, 66, 62, 74, 38, 88, 95, 81, 61, 11, 35, 53, 7, 78, 26, 87, 68, 19, 93, 34, 46, 75, 28, 91, 79, 47, 89, 29, 96, 48, 77, 98, 13, 17, 72, 6, 67, 43, 18, 4, 80, 82, 25, 33, 58, 10, 92, 41, 76, 36, 63, 21, 59, 40, 60, 64, 85, 15, 44, 8, 55, 39, 14, 45, 12, 99, 30, 56, 20, 49, 83, 50, 71, 86, 16, 42, 32, 37, 23, 22, 73, 70, 9, 100}

    {36, 2, 11, 27, 4, 2, 3, 55, 5, 32, 16, 65, 30, 28, 67, 1, 21, 5, 39, 21, 18, 7, 46, 48, 7, 12, 45, 1, 61, 18, 83, 9, 5, 84, 18, 19, 14, 8, 2, 48, 37, 85, 4, 87, 33, 46, 42, 12, 11, 57, 1, 20, 12, 5, 3, 29, 38, 18, 3, 24, 8, 55, 12, 4, 32, 21, 1, 49, 23, 19, 25, 43, 12, 3, 1, 15, 38, 12, 32, 1, 7, 13, 43, 10, 3, 70, 14, 63, 4, 14, 6, 19, 7, 17, 3, 4, 33, 6, 6}

    {7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7}

    Returns: { }

  22. {26, 84, 36, 56, 83, 99, 13, 3, 79, 18, 61, 2, 87, 58, 92, 32, 34, 68, 22, 81, 38, 8, 45, 75, 40, 74, 62, 15, 64, 52, 90, 35, 89, 65, 24, 60, 42, 31, 44, 5, 96, 66, 55, 10, 48, 63, 9, 17, 82, 97, 71, 86, 57, 39, 6, 4, 7, 25, 20, 16, 85, 59, 98, 12, 73, 78, 69, 41, 33, 100, 29, 21, 37, 28, 91, 53, 47, 94, 70, 72, 67, 51, 88, 80, 95, 76, 30, 11, 19, 50, 46, 14, 27, 93, 23, 43, 49, 54, 77}

    {7, 23, 10, 5, 10, 62, 6, 1, 64, 7, 44, 1, 51, 21, 64, 22, 22, 57, 5, 70, 33, 7, 22, 60, 21, 5, 19, 8, 50, 41, 42, 4, 6, 54, 11, 45, 8, 25, 37, 1, 6, 23, 50, 6, 24, 52, 7, 3, 45, 23, 41, 72, 4, 30, 3, 3, 5, 11, 16, 12, 31, 38, 56, 3, 8, 72, 55, 24, 23, 31, 2, 14, 27, 15, 10, 5, 35, 62, 5, 50, 28, 22, 74, 12, 73, 66, 10, 2, 9, 39, 41, 11, 3, 48, 21, 5, 16, 35, 66}

    {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4}

    Returns: { }

  23. {99, 8, 3, 82, 59, 21, 91, 46, 63, 65, 92, 17, 79, 28, 86, 73, 23, 18, 97, 44, 69, 2, 61, 53, 14, 94, 84, 47, 77, 36, 6, 37, 81, 38, 100, 42, 27, 30, 43, 31, 48, 39, 74, 68, 56, 51, 9, 98, 45, 49, 70, 96, 35, 62, 88, 95, 89, 19, 15, 11, 29, 22, 90, 80, 16, 58, 72, 4, 55, 75, 60, 40, 85, 20, 12, 67, 13, 5, 24, 87, 54, 83, 34, 26, 33, 52, 10, 41, 25, 32, 71, 7, 93, 50, 64, 57, 66, 76, 78}

    {18, 1, 1, 36, 27, 15, 18, 34, 28, 41, 7, 14, 71, 21, 74, 72, 13, 3, 33, 14, 67, 1, 18, 18, 13, 76, 46, 13, 24, 14, 2, 8, 17, 28, 19, 26, 18, 26, 28, 4, 45, 12, 52, 66, 9, 24, 7, 77, 18, 40, 16, 18, 21, 18, 13, 22, 15, 16, 2, 8, 7, 17, 9, 65, 8, 35, 46, 2, 39, 71, 27, 29, 35, 4, 3, 64, 2, 4, 15, 52, 33, 75, 13, 4, 27, 4, 5, 35, 17, 12, 56, 5, 8, 47, 48, 35, 54, 24, 22}

    {7, 4, 4, 7, 4, 7, 4, 7, 7, 4, 7, 7, 7, 4, 4, 7, 4, 4, 4, 4, 7, 4, 7, 4, 4, 4, 7, 4, 4, 7, 7, 4, 4, 4, 4, 7, 7, 4, 7, 7, 4, 4, 4, 4, 7, 4, 4, 4, 7, 4, 7, 4, 4, 4, 4, 7, 4, 4, 7, 7, 7, 4, 4, 7, 7, 4, 4, 7, 4, 4, 4, 7, 7, 7, 7, 7, 4, 4, 7, 4, 7, 4, 7, 7, 7, 4, 7, 4, 7, 4, 4, 4, 4, 7, 4, 7, 4, 7, 4}

    Returns: {1, 70, 4 }

  24. {16, 33, 62, 68, 100, 74, 89, 88, 71, 56, 77, 24, 60, 54, 22, 32, 38, 52, 37, 29, 48, 50, 72, 51, 6, 17, 83, 86, 78, 94, 44, 4, 49, 10, 55, 92, 31, 39, 27, 99, 58, 26, 59, 9, 34, 69, 95, 81, 63, 90, 43, 46, 19, 28, 35, 41, 93, 14, 42, 18, 30, 53, 76, 25, 67, 8, 91, 40, 57, 75, 7, 79, 21, 70, 47, 80, 84, 20, 13, 5, 45, 64, 3, 85, 97, 82, 2, 66, 73, 11, 96, 87, 98, 12, 23, 61, 15, 65, 36}

    {5, 9, 11, 25, 58, 59, 65, 2, 29, 4, 18, 9, 31, 11, 12, 29, 33, 11, 18, 10, 6, 25, 39, 4, 1, 8, 48, 41, 48, 86, 24, 1, 8, 4, 54, 15, 18, 5, 22, 88, 34, 4, 54, 5, 13, 63, 28, 46, 26, 53, 23, 17, 12, 7, 31, 7, 88, 8, 17, 6, 7, 51, 69, 18, 32, 7, 76, 22, 23, 70, 6, 58, 10, 1, 29, 76, 3, 15, 8, 1, 22, 19, 1, 62, 88, 8, 1, 9, 16, 6, 58, 61, 54, 1, 8, 45, 10, 14, 22}

    {7, 7, 4, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 7, 4, 7, 7, 7, 7, 7, 4, 4, 4, 4, 7, 4, 7, 7, 4, 4, 7, 7, 4, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 7, 4, 4, 4, 4, 7, 4, 4, 4, 4, 4, 7, 4, 7, 7, 4, 7, 4, 4, 7, 4, 7, 4, 4, 7, 7, 7, 7, 7, 4, 7, 7, 7, 7, 4, 4, 7, 4, 4, 4, 7, 4, 7, 7, 4, 7, 4, 4, 7, 4, 7, 4, 7, 4, 4, 4}

    Returns: {1, 83, 4 }

  25. {1, 3, 2, 4 }

    {2, 2, 4, 5 }

    {4, 7, 4, 7 }

    Returns: {1, 5, 7 }

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

    {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 }

    {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 }

    Returns: { }

  27. {1, 2, 3, 5, 6 }

    {2, 3, 4, 3, 5 }

    {4, 7, 7, 7, 7 }

    Returns: {1, 4, 4 }

  28. {1, 1, 1, 2 }

    {2, 3, 4, 5 }

    {4, 4, 7, 7 }

    Returns: {3, 5, 7 }

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

    {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 }

    {4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7 }

    Returns: {1, 12, 7 }

  30. {1, 2, 3, 4 }

    {2, 3, 4, 5 }

    {4, 4, 7, 7 }

    Returns: {1, 4, 7 }

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: