Statistics

Problem Statement for "Playlist"

Problem Statement

You have n distinct songs in your music player, numbered 1 through n. Some of these songs are good and the rest are bad. The good songs are given in the int[] best.

Your task is to order your songs into a playlist where each song appears exactly once. The goal is to maximize the total number of times you hear a good song in shuffle mode. In shuffle mode, your music player plays the a[0]-th song in your playlist, followed by the a[1]-th song, etc. All indices are 1-based. If the same song is played multiple times, each time counts toward the total.

Return a int[] containing the playlist that will achieve this goal. If there are multiple possible return values, choose the one that comes earliest lexicographically. A int[] a comes before a int[] b if a contains a smaller element at the first index where they differ.

Definition

Class:
Playlist
Method:
trackSort
Parameters:
int, int[], int[]
Returns:
int[]
Method signature:
int[] trackSort(int n, int[] best, int[] a)
(be sure your method is public)

Constraints

  • n will be between 1 and 50, inclusive.
  • best will contain between 0 and n elements, inclusive.
  • All elements of best will be distinct.
  • a will contain between 0 and 50 elements, inclusive.
  • Each element of best and a will be between 1 and n, inclusive.

Examples

  1. 3

    {1, 2}

    {3, 2, 3, 3, 1, 2}

    Returns: {3, 1, 2 }

    There are 3 songs, and songs 1 and 2 are good. If you order the tracks in your playlist {3, 1, 2} or {3, 2, 1}, you will hear a good song 5 times in shuffle mode. In case of a tie, you should choose the one that comes earliest lexicographically, so the answer is {3, 1, 2}.

  2. 5

    {}

    {1, 2, 3, 5, 4}

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

    In this case, there are no good songs, so you should just choose the playlist that comes first lexicographically: {1, 2, 3, 4, 5}.

  3. 6

    {3, 5}

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

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

  4. 3

    {3, 2, 1}

    {3, 1, 2, 3, 2, 1, 2, 1, 3}

    Returns: {1, 2, 3 }

  5. 5

    {4, 5, 3}

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

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

  6. 10

    {8, 5, 1, 7}

    {6, 6, 4, 4}

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

  7. 8

    {6}

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

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

  8. 19

    {5, 9, 10, 18}

    {4, 4, 8, 8, 11, 11, 16, 16, 19}

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

  9. 19

    {2, 6, 10, 13, 12, 18}

    {4, 4, 8, 8, 11, 11, 16, 16}

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

  10. 50

    {4, 5, 6, 7}

    {5, 5, 5, 8, 8, 8, 16, 18, 15, 15}

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

  11. 50

    {3}

    {2, 50, 2, 50, 2, 50, 50, 2, 50, 50, 2, 50, 50, 2, 2, 2, 2, 2, 50, 50, 50, 50, 50, 2, 2, 2, 2, 2, 2, 50, 50, 2, 50, 50, 50, 50, 2, 50, 2, 50, 2, 2, 2, 50, 50, 50, 2, 2, 50, 2}

    Returns: {1, 2, 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, 3 }

  12. 50

    {47, 48}

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

    Returns: {47, 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, 48, 46, 49, 50 }

  13. 50

    {6, 33, 2, 1, 30, 49, 12, 40, 34, 17, 11, 9, 8, 41, 20, 5, 13, 23, 4, 39, 38, 25}

    {13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13}

    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 }

  14. 50

    {46, 44, 33, 50, 1, 34, 6, 30, 32, 10, 17, 45}

    {13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13}

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

  15. 50

    {24, 23, 28, 50, 38, 5, 18, 49, 42, 32, 17, 48, 41, 34, 13, 10, 8, 15, 47, 9, 31, 37, 19, 39, 11, 35, 4, 36, 30, 43, 16, 21, 26, 33, 46, 12, 6, 22, 20}

    {13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13}

    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 }

  16. 50

    {40, 30, 50, 23, 28, 38, 16, 35, 27, 20, 39, 43, 10, 46, 2, 8, 7, 9}

    {13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13}

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

  17. 15

    {2, 10}

    {8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8}

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

  18. 18

    {3}

    {}

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

  19. 45

    {15}

    {30, 30, 30, 33, 30, 33, 30, 30, 30, 30, 30, 33, 30, 30, 33, 30, 33, 33}

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

  20. 37

    {2}

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

    Returns: {2, 1, 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 }

  21. 20

    {1}

    {}

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

  22. 32

    {1, 4}

    {30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30}

    Returns: {1, 2, 3, 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, 4, 31, 32 }

  23. 4

    {}

    {}

    Returns: {1, 2, 3, 4 }

  24. 10

    {2}

    {3}

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

  25. 28

    {2, 6, 17, 20, 23}

    {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}

    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 }

  26. 1

    {}

    {1}

    Returns: {1 }

  27. 34

    {1}

    {13, 13, 13, 13, 13}

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

  28. 48

    {}

    {8, 8, 34, 8, 8, 8, 44, 34, 32, 16, 32, 8, 16, 8, 44, 16, 16, 44, 16, 16, 16, 16, 16, 34, 34, 8, 32, 34, 16, 34, 8, 8, 8, 8, 8, 44, 44, 44, 8, 8, 32}

    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 }

  29. 21

    {2}

    {12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12}

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

  30. 3

    {}

    {}

    Returns: {1, 2, 3 }

  31. 17

    {1, 15}

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

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

  32. 49

    {31, 34, 45, 39, 48, 32, 12, 17, 24, 44, 13, 41, 49, 47, 37, 21, 4, 27, 29, 30, 14, 26, 35, 5, 10, 36, 2, 7, 3, 1, 18, 11, 20, 8, 6}

    {14, 1, 1, 7, 1, 29, 1, 2, 1, 1, 1, 1, 1, 24, 39, 29, 1, 1, 1, 1, 1, 1, 39, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 41, 19, 24, 14, 19, 1, 19, 1, 1, 14, 2, 1, 7, 39, 1, 41}

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

  33. 43

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

    {8, 3, 8, 7, 9, 26, 15, 22, 3, 15, 7, 8, 8, 12, 8, 8, 8, 9, 9, 29, 26, 8, 3, 6, 3, 8, 15, 8, 8, 26, 3, 6, 7, 12, 3, 8, 8, 22, 20, 16, 16, 8, 20}

    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 }

  34. 40

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

    {3, 26, 25, 40, 35, 11, 40, 19, 3, 25, 1, 22, 2, 13, 31, 2, 14, 31, 20, 24, 2, 17, 22, 26, 27, 36, 11, 14, 1, 24, 4, 13, 20, 27, 2, 4, 35, 17, 2, 36}

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

  35. 42

    {}

    {19, 12, 29, 16, 12, 19, 19, 12, 12, 12, 22, 30, 28, 27, 42, 16, 12, 12, 27, 12, 2, 12, 19, 19, 19, 21, 21, 26, 12, 12, 26, 12, 19, 12, 28, 2, 19, 29, 12, 30, 42, 12}

    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 }

  36. 20

    {}

    {16, 2, 2, 2, 3, 16, 10, 2, 14, 14, 1, 2, 2, 2, 2, 10, 5, 2, 1, 2}

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

  37. 22

    {14, 1, 10}

    {1, 1, 6, 12, 1, 20, 16, 1, 2, 6, 6, 16, 6, 20, 6, 1, 2, 4, 4, 1, 12, 16}

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

  38. 39

    {19}

    {30, 11, 5, 17, 5, 20, 23, 20, 9, 11, 8, 20, 30, 13, 33, 11, 12, 9, 12, 8, 3, 21, 3, 9, 30, 37, 33, 5, 10, 17, 12, 10, 17, 23, 21, 14, 23, 37, 10}

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

  39. 37

    {25, 6, 5, 33, 7, 11, 24, 20, 18, 9, 15}

    {33, 5, 1, 13, 1, 33, 9, 8, 22, 1, 1, 6, 22, 1, 1, 1, 1, 5, 1, 6, 23, 8, 1, 5, 1, 23, 9, 2, 17, 13, 24, 1, 1, 24, 1, 1, 17}

    Returns: {5, 1, 2, 3, 6, 7, 4, 9, 11, 8, 10, 12, 15, 13, 14, 16, 18, 17, 19, 21, 22, 20, 24, 25, 23, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37 }

  40. 40

    {40, 11, 31, 28, 29, 33, 35, 7, 15, 9, 39, 19, 5, 4, 26, 23, 38, 25, 8, 21, 37}

    {39, 3, 26, 27, 27, 39, 1, 24, 8, 31, 14, 25, 13, 25, 3, 8, 33, 39, 25, 9, 33, 26, 31, 3, 9, 17, 36, 17, 21, 22, 31, 21, 33, 22, 36, 36, 24, 17, 13, 24}

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

  41. 1

    {1}

    {1}

    Returns: {1 }

  42. 2

    {}

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

    Returns: {1, 2 }

  43. 2

    {1}

    {2,2,2,2,2,2,2,2,2,2,2}

    Returns: {2, 1 }

  44. 2

    {1 }

    { }

    Returns: {1, 2 }

  45. 10

    {8, 5, 1, 7 }

    {6, 6, 4, 4 }

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

  46. 50

    {5, 49, 50, 13, 31 }

    {1, 10, 20, 30, 40, 50 }

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

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: