Statistics

Problem Statement for "ReversalSorting"

Problem Statement

You are given a permutation P of values 0 to N-1.

Your task is simple: sort this permutation, i.e., transform it to the identity permutation {0, 1, ..., N-1}.


The only way in which you can modify P is by reversing its subarrays. More precisely, in each step you can select any half-open range of indices [x, y) and reverse the order of values within that range: instead of P[x], P[x+1], ..., P[y-1] these values will now be P[y-1], ..., P[x+1], P[x].

For example, you can transform the permutation P = {0, 1, 2, 6, 5, 4, 3, 7, 8} into the identity permutation by reversing the range [3, 7).


Your task is to find a reasonably short sequence of reversals that sorts P.

Let opt(P) be the optimal number of reversals needed to sort P. Then:

  • The number of reversals in your solution must not exceed 2*opt(P).
  • The number of reversals in your solution must not exceed N-1.

If you want to perform K reversals, return a int[] with 2*K values: for each reversal, in order, return the indices x and y.


----------


The system tests contain a set of permutations for which we know the exact value of the optimal solution. These permutations have between 1 and 50 elements, inclusive.

As we need to know opt(P) to evaluate your solution, for N > 9 the validator that is executed when you submit a challenge only allows the specific test cases that are included in the system tests. If you can guess what they are, you can use them as challenges :) but most likely this means that custom challenges are only allowed for permutations of length up to 9.

Definition

Class:
ReversalSorting
Method:
solve
Parameters:
int[]
Returns:
int[]
Method signature:
int[] solve(int[] P)
(be sure your method is public)

Notes

  • It is guaranteed that a valid solution always exists.
  • Each reversal [x, y) in your return value must satisfy 0 <= x <= y <= N. (Reversals with y-x < 2 do nothing, but your solution may still return them if you want.)

Constraints

  • P will contain between 1 and 50 elements, inclusive.
  • P will be a permutation of values 0 through length(P)-1.

Examples

  1. {0, 1, 2}

    Returns: { }

    This is already a sorted permutation. The optimal number of reversals needed is 0, and thus the only valid solution is to do nothing.

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

    Returns: {3, 7, 0, 1 }

    Example permutation from the problem statement. You may return any sequence of one or two reversals that sorts it. The reference solution performs the one reversal that sorts it and then another dummy reversal that only touches element 0 of P. The returned solution is not optimal but it is still within the stated limits, so it's a valid solution.

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

    Returns: {0, 2, 2, 4, 4, 6, 6, 8 }

    Our solution sorts this permutation by performing four consecutive transpositions (i.e., reversals of two-element ranges): we reverse the range [0,2), then [2,4), then [4,6), and finally [6,8).

  4. {0}

    Returns: { }

  5. {0, 1}

    Returns: { }

  6. {1, 0}

    Returns: {0, 2 }

  7. {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: { }

  8. {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}

    Returns: {0, 50, 0, 49 }

  9. {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, 0}

    Returns: {0, 49, 0, 50 }

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

    Returns: {0, 2, 2, 6, 1, 4, 1, 5, 4, 6, 5, 7 }

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

    Returns: {0, 2, 0, 3, 3, 5, 2, 4, 4, 6, 4, 7 }

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

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

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

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

  14. {2, 0, 4, 1, 6, 3, 8, 5, 7}

    Returns: {0, 2, 1, 3, 1, 4, 4, 8, 3, 6, 3, 7, 6, 8, 7, 9 }

  15. {0, 2, 4, 1, 6, 3, 8, 5, 7}

    Returns: {1, 3, 1, 4, 4, 8, 3, 6, 3, 7, 6, 8, 7, 9 }

  16. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15, 13, 17, 14, 19, 16, 21, 18, 23, 20, 24, 22, 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: {13, 15, 14, 16, 14, 17, 16, 18, 16, 19, 18, 20, 18, 21, 21, 23, 20, 22, 22, 24, 22, 25 }

  17. {2, 0, 4, 1, 6, 3, 8, 5, 10, 7, 11, 9, 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, 2, 1, 3, 1, 4, 3, 5, 3, 6, 5, 7, 5, 8, 8, 10, 7, 9, 9, 11, 9, 12 }

  18. {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, 40, 38, 42, 39, 44, 41, 46, 43, 48, 45, 49, 47}

    Returns: {38, 40, 39, 41, 39, 42, 41, 43, 41, 44, 43, 45, 43, 46, 46, 48, 45, 47, 47, 49, 47, 50 }

  19. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 16, 13, 18, 15, 20, 17, 22, 19, 24, 21, 23, 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: {13, 15, 13, 16, 15, 17, 15, 18, 17, 19, 17, 20, 20, 24, 19, 22, 19, 23, 22, 24, 23, 25 }

  20. {1, 3, 0, 5, 2, 7, 4, 9, 6, 11, 8, 10, 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, 2, 0, 3, 2, 4, 2, 5, 4, 6, 4, 7, 7, 11, 6, 9, 6, 10, 9, 11, 10, 12 }

  21. {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, 39, 41, 38, 43, 40, 45, 42, 47, 44, 49, 46, 48}

    Returns: {38, 40, 38, 41, 40, 42, 40, 43, 42, 44, 42, 45, 45, 49, 44, 47, 44, 48, 47, 49, 48, 50 }

  22. {0, 1, 2, 4, 3}

    Returns: {3, 5 }

  23. {1, 0, 2, 4, 3}

    Returns: {0, 2, 3, 5 }

  24. {3, 4, 8, 7, 6, 2, 1, 0, 5}

    Returns: {2, 9, 0, 3, 0, 6, 0, 3 }

  25. {0, 4, 3, 2, 1}

    Returns: {1, 5 }

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

    Returns: {1, 5 }

  27. {0, 1, 2, 3, 4, 5, 8, 7, 6}

    Returns: {6, 9 }

  28. {0, 1, 3, 2, 4}

    Returns: {2, 4 }

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

    Returns: {0, 3, 0, 2, 2, 4, 2, 7, 2, 4 }

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

    Returns: {1, 5, 3, 7, 0, 4, 0, 6 }

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

    Returns: {1, 6, 0, 4, 1, 5, 1, 4 }

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

    Returns: {2, 5, 4, 7 }

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

    Returns: {4, 7 }

  34. {2, 0, 1}

    Returns: {0, 2, 1, 3 }

  35. {1, 4, 3, 0, 2}

    Returns: {1, 5, 0, 2, 0, 3 }

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

    Returns: {2, 8 }

  37. {3, 0, 2, 1, 4}

    Returns: {0, 2, 1, 4 }

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

    Returns: {1, 3, 2, 5, 0, 3, 0, 6 }

  39. {1, 0, 3, 2}

    Returns: {0, 2, 2, 4 }

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

    Returns: {0, 6, 2, 5 }

  41. {8, 7, 1, 3, 4, 5, 6, 2, 0}

    Returns: {0, 9, 2, 7, 1, 3 }

  42. {0, 1, 2}

    Returns: { }

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

    Returns: {2, 5, 3, 5, 4, 6 }

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

    Returns: {0, 6, 0, 2 }

  45. {0, 3, 2, 8, 6, 5, 4, 1, 7}

    Returns: {3, 8, 1, 4, 7, 9 }

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

    Returns: {1, 7, 0, 6 }

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

    Returns: {2, 4, 1, 6, 2, 4, 4, 6 }

  48. {1, 0, 2}

    Returns: {0, 2 }

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

    Returns: {1, 6 }

  50. {0, 2, 1}

    Returns: {1, 3 }

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

    Returns: {2, 5, 1, 3, 4, 6 }

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

    Returns: {0, 4, 0, 3, 3, 7 }

  53. {0, 4, 3, 2, 1}

    Returns: {1, 5 }

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

    Returns: {0, 3 }

  55. {0, 2, 1}

    Returns: {1, 3 }

  56. {2, 1, 0, 3, 4, 5, 6, 7, 8}

    Returns: {0, 3 }

  57. {0, 7, 4, 8, 3, 2, 6, 1, 5}

    Returns: {2, 4, 6, 8, 1, 7, 5, 9 }

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

    Returns: {1, 5, 0, 3 }

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

    Returns: {1, 6, 1, 3 }

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

    Returns: {1, 7, 0, 4, 4, 8, 1, 6, 1, 5 }

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

    Returns: {1, 7, 0, 2, 2, 5, 3, 8, 3, 5 }

  62. {4, 3, 2, 1, 0}

    Returns: {0, 5 }

  63. {8, 7, 6, 1, 2, 3, 5, 4, 0}

    Returns: {0, 9, 1, 3, 1, 6 }

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

    Returns: {4, 6 }

  65. {2, 0, 1}

    Returns: {0, 2, 1, 3 }

  66. {0, 1, 2, 3, 4, 7, 8, 6, 5}

    Returns: {5, 7, 5, 9 }

  67. {6, 3, 5, 4, 8, 0, 2, 7, 1}

    Returns: {5, 8, 1, 6, 3, 5, 0, 3, 0, 9, 0, 2 }

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

    Returns: {0, 5, 1, 3, 1, 6, 1, 3 }

  69. {3, 0, 1, 2, 4}

    Returns: {0, 4, 0, 3 }

  70. {0, 1, 3, 2, 4}

    Returns: {2, 4 }

  71. {2, 3, 1, 4, 0}

    Returns: {2, 4, 0, 3, 0, 5 }

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

    Returns: {3, 10, 1, 5, 1, 4, 3, 7, 6, 8, 7, 9 }

  73. {0, 1, 2, 3, 4, 9, 5, 13, 11, 10, 7, 8, 12, 6, 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}

    Returns: {7, 14, 5, 9, 5, 8, 7, 11, 10, 12, 11, 13 }

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

    Returns: {4, 6, 6, 8, 8, 10 }

  75. {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, 40, 39, 42, 41, 44, 43, 45, 46, 47}

    Returns: {39, 41, 41, 43, 43, 45 }

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

    Returns: {0, 3, 2, 4, 6, 8, 7, 10 }

  77. {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, 39, 37, 36, 38, 40, 41, 45, 42, 44, 43, 46, 47}

    Returns: {36, 39, 38, 40, 42, 44, 43, 46 }

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

    Returns: {0, 7, 6, 9, 4, 7 }

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

    Returns: {16, 23, 22, 25, 20, 23 }

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

    Returns: {0, 4, 5, 9, 2, 8 }

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

    Returns: {24, 28, 29, 33, 26, 32 }

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

    Returns: {2, 9, 4, 7, 0, 6, 1, 3, 3, 5, 3, 11, 4, 6, 6, 8 }

  83. {0, 1, 10, 12, 6, 9, 4, 2, 8, 3, 11, 7, 5, 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}

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

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

    Returns: {1, 6, 3, 10, 2, 8, 4, 9 }

  85. {0, 1, 3, 5, 10, 6, 2, 4, 9, 8, 7, 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}

    Returns: {2, 7, 4, 11, 3, 9, 5, 10 }

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

    Returns: {1, 4, 5, 9 }

  87. {0, 3, 2, 1, 4, 8, 7, 6, 5, 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}

    Returns: {1, 4, 5, 9 }

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

    Returns: {0, 7, 3, 5, 3, 9 }

  89. {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, 35, 36, 38, 37, 32, 31, 30, 34, 33, 39, 40, 41, 42, 43, 44, 45, 46}

    Returns: {30, 37, 33, 35, 33, 39 }

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

    Returns: {4, 7, 0, 10, 0, 7 }

  91. {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, 43, 42, 41, 34, 37, 36, 35, 38, 39, 40, 44, 45, 46, 47, 48, 49}

    Returns: {38, 41, 34, 44, 34, 41 }

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

    Returns: {6, 11, 2, 9, 0, 7, 6, 13, 4, 12, 3, 9, 3, 5 }

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

    Returns: {26, 31, 22, 29, 20, 27, 26, 33, 24, 32, 23, 29, 23, 25 }

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

    Returns: {1, 3, 2, 4, 2, 8, 3, 5, 3, 11, 3, 12, 3, 8, 3, 13, 5, 7, 7, 13 }

  95. {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, 34, 28, 39, 35, 37, 36, 29, 32, 33, 31, 38, 30, 40, 41, 42, 43, 44, 45, 46, 47, 48}

    Returns: {28, 30, 29, 31, 29, 35, 30, 32, 30, 38, 30, 39, 30, 35, 30, 40, 32, 34, 34, 40 }

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

    Returns: {1, 9, 2, 12, 2, 7, 2, 13 }

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

    Returns: {16, 24, 17, 27, 17, 22, 17, 28 }

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

    Returns: {6, 11, 5, 7, 0, 3, 0, 10, 0, 6, 6, 8 }

  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, 38, 40, 41, 39, 32, 34, 42, 37, 36, 35, 33, 43, 44, 45, 46, 47, 48}

    Returns: {38, 43, 37, 39, 32, 35, 32, 42, 32, 38, 38, 40 }

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

    Returns: {2, 8, 10, 13, 0, 6, 0, 5, 3, 11, 5, 9, 7, 14, 5, 7, 5, 10 }

  101. {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, 36, 28, 41, 37, 39, 38, 30, 29, 40, 32, 34, 33, 31, 35, 42, 43, 44, 45, 46}

    Returns: {30, 36, 38, 41, 28, 34, 28, 33, 31, 39, 33, 37, 35, 42, 33, 35, 33, 38 }

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

    Returns: {5, 13, 1, 9, 1, 5, 1, 12 }

  103. {0, 1, 2, 6, 7, 8, 9, 14, 3, 4, 5, 10, 11, 12, 13, 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}

    Returns: {7, 15, 3, 11, 3, 7, 3, 14 }

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

    Returns: {0, 9, 1, 9, 1, 11 }

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

    Returns: {23, 32, 24, 32, 24, 34 }

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

    Returns: {0, 13, 5, 8, 3, 12, 3, 9, 3, 14 }

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

    Returns: {22, 35, 27, 30, 25, 34, 25, 31, 25, 36 }

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

    Returns: {1, 13, 0, 5, 0, 8, 1, 8, 1, 10, 1, 8 }

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

    Returns: {22, 34, 21, 26, 21, 29, 22, 29, 22, 31, 22, 29 }

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

    Returns: {2, 10, 5, 14, 7, 13, 10, 12 }

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

    Returns: {14, 22, 17, 26, 19, 25, 22, 24 }

  112. {0, 1, 10, 9, 8, 4, 12, 11, 2, 3, 5, 13, 14, 7, 6, 15}

    Returns: {6, 11, 2, 9, 4, 6, 6, 13, 6, 15 }

  113. {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, 35, 34, 33, 29, 37, 36, 27, 28, 30, 38, 39, 32, 31, 40, 41, 42, 43, 44, 45}

    Returns: {31, 36, 27, 34, 29, 31, 31, 38, 31, 40 }

  114. {3, 4, 5, 0, 6, 8, 13, 11, 12, 10, 9, 2, 7, 1, 14, 15}

    Returns: {7, 9, 0, 4, 4, 12, 1, 11, 1, 14, 2, 8, 8, 13, 8, 14 }

  115. {0, 1, 5, 6, 7, 2, 8, 10, 15, 13, 14, 12, 11, 4, 9, 3, 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: {9, 11, 2, 6, 6, 14, 3, 13, 3, 16, 4, 10, 10, 15, 10, 16 }

  116. {8, 0, 3, 2, 1, 9, 12, 11, 10, 4, 5, 13, 14, 15, 16, 7, 6}

    Returns: {0, 2, 1, 5, 4, 15, 4, 10, 6, 17, 10, 13, 13, 17 }

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

    Returns: {10, 12, 11, 15, 14, 25, 14, 20, 16, 27, 20, 23, 23, 27 }

  118. {15, 6, 5, 4, 10, 9, 14, 16, 17, 1, 2, 3, 13, 12, 11, 8, 7, 0}

    Returns: {0, 6, 0, 15, 6, 18, 0, 7, 7, 11, 11, 14, 4, 14, 14, 16 }

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

    Returns: {11, 17, 11, 26, 17, 29, 11, 18, 18, 22, 22, 25, 15, 25, 25, 27 }

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

    Returns: {2, 4, 2, 6, 3, 8, 8, 11 }

  121. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 18, 17, 19, 14, 16, 15, 22, 21, 20, 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}

    Returns: {14, 16, 14, 18, 15, 20, 20, 23 }

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

    Returns: {1, 3, 3, 13, 0, 9, 3, 11, 3, 17, 3, 5, 3, 19, 3, 20 }

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

    Returns: {18, 20, 20, 30, 17, 26, 20, 28, 20, 34, 20, 22, 20, 36, 20, 37 }

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

    Returns: {5, 7, 10, 18, 15, 17, 0, 8, 0, 21, 0, 10, 2, 8, 2, 12, 2, 7, 2, 5, 2, 14 }

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

    Returns: {8, 10, 13, 21, 18, 20, 3, 11, 3, 24, 3, 13, 5, 11, 5, 15, 5, 10, 5, 8, 5, 17 }

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

    Returns: {8, 20, 9, 13, 2, 14, 2, 9 }

  127. {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, 40, 39, 38, 37, 36, 29, 46, 45, 44, 43, 42, 41, 35, 31, 32, 33, 34, 30, 47, 48, 49}

    Returns: {35, 47, 36, 40, 29, 41, 29, 36 }

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

    Returns: {8, 11, 1, 3, 2, 7, 6, 21, 6, 8, 6, 10, 9, 12, 10, 12, 10, 22, 12, 18, 18, 22 }

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

    Returns: {30, 33, 23, 25, 24, 29, 28, 43, 28, 30, 28, 32, 31, 34, 32, 34, 32, 44, 34, 40, 40, 44 }

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

    Returns: {0, 9, 0, 3, 0, 12, 2, 21, 6, 22, 3, 17, 3, 18, 8, 13, 9, 14, 13, 18, 13, 23 }

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

    Returns: {6, 15, 6, 9, 6, 18, 8, 27, 12, 28, 9, 23, 9, 24, 14, 19, 15, 20, 19, 24, 19, 29 }

  132. {4, 0, 5, 6, 7, 8, 9, 10, 11, 19, 20, 21, 24, 23, 22, 1, 2, 3, 16, 15, 14, 13, 12, 18, 17}

    Returns: {0, 2, 9, 23, 1, 14, 1, 17, 17, 20, 17, 25 }

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

    Returns: {23, 25, 32, 46, 24, 37, 24, 40, 40, 43, 40, 48 }

  134. {24, 14, 13, 12, 3, 20, 21, 2, 1, 0, 23, 22, 19, 16, 6, 7, 5, 4, 15, 18, 17, 11, 10, 9, 8}

    Returns: {0, 10, 3, 6, 4, 12, 4, 10, 4, 18, 9, 19, 6, 8, 8, 25, 12, 23, 15, 25, 15, 17 }

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

    Returns: {13, 23, 16, 19, 17, 25, 17, 23, 17, 31, 22, 32, 19, 21, 21, 38, 25, 36, 28, 38, 28, 30 }

  136. {5, 4, 7, 8, 2, 3, 6, 0, 1 }

    Returns: {2, 6, 4, 9, 0, 6 }

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

    Returns: {0, 3, 1, 7, 0, 2, 0, 3, 0, 8, 2, 4, 4, 8 }

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: