TopCoder problem "MusicCompilation" used in SRM 251 (Division I Level Three)

Problem Statement


Over the years you have collected a great mass of music from various artists. These days you have very little time to listen to your whole collection. You decide to make a single compilation that contains the best hits from each artist. Your first attempt at the compilation was to place the best hits in a random order. However, this resulted in songs from the same artist being close or even next to each other. This is highly undesirable since you hate listening to the same artist over and over again.

After some further consideration you realize that there must be some kind of an ultimate order - i.e., an order where artists are 'spread out' across the compilation as much as possible. You then come up with a distance metric (D) that measures the 'spread' of artists across the compilation:

D(compilation) = Sum of all D(i), where D(i) is the distance of the song at position i.

D(i) = k-i, where k is the smallest integer greater than i, such that the songs at positions k and i are by the same artist. 0 if no such k exists.

Each element in artists will be formatted as "<artist name> <number of hits>". Your task is to make a String[] compilation of these artists such that D(compilation) is maximal. If there is more than one such compilation return the one which is lexicographically earliest.



Method signature:String[] makeCompilation(String[] artists)
(be sure your method is public)


-artists will contain between 0 and 50 elements inclusive.
-Each element in artists will be formatted as "<artist name> <number of hits>".
-<artist name> will contain between 1 and 10 letters ('a'-'z' and 'A'-'Z'), inclusive.
-<artist name> is case-sensitive and may not appear more than once in artists.
-<number of hits> will be an integer with no leading zeroes between 1 and 800 inclusive.
-The sum of all <number of hits> will be between 0 and 800 inclusive.


{"Shakira 1","Jamiroquai 3","Gorillaz 2"}
Returns: {"Gorillaz", "Jamiroquai", "Jamiroquai", "Shakira", "Gorillaz", "Jamiroquai" }
Songs 1, 2 and 3 have distances 4, 1 and 3 respectively. Songs 4, 5 and 6 have distances of 0 because they are not followed by songs from the same artist. Hence, the distance of the compilation is 4 + 1 + 3 = 8. Although there are other compilations with the same distance, this is the lexicographically earliest.
{"Radiohead 2","Spiderbait 3","LimpBizkit 4"}
"Spiderbait" }
{"Beatles 2","ABBA 1"}
Returns: {"Beatles", "ABBA", "Beatles" }
Call me old-fashioned, but I love these two bands!

Problem url:

Problem stats url:




PabloGilberto , lbackstrom , brett1479

Problem categories:

Greedy, Sorting