MusicCompilation
SRM 251 · 2005-07-12 · by dimkadimon
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
Constraints
- artists will contain between 0 and 50 elements inclusive.
- Each element in artists will be formatted as "
". will contain between 1 and 10 letters ('a'-'z' and 'A'-'Z'), inclusive. is case-sensitive and may not appear more than once in artists. will be an integer with no leading zeroes between 1 and 800 inclusive. - The sum of all
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"}
Returns: {"LimpBizkit", "Radiohead", "Spiderbait", "LimpBizkit", "LimpBizkit", "Spiderbait", "LimpBizkit", "Radiohead", "Spiderbait" }
{"MisHiggins 3","TheWhitlam 7","AvrilLavig 3","ChrAguiler 3","CatEmpire 5",
"RHCP 5","Shakira 1"}
Returns: {"AvrilLavig", "CatEmpire", "ChrAguiler", "MisHiggins", "RHCP", "TheWhitlam", "AvrilLavig", "CatEmpire", "CatEmpire", "CatEmpire", "ChrAguiler", "MisHiggins", "RHCP", "RHCP", "RHCP", "Shakira", "TheWhitlam", "TheWhitlam", "TheWhitlam", "TheWhitlam", "TheWhitlam", "AvrilLavig", "CatEmpire", "ChrAguiler", "MisHiggins", "RHCP", "TheWhitlam" }
{"Beatles 7","ABBA 5"}
Returns: {"ABBA", "Beatles", "ABBA", "ABBA", "ABBA", "Beatles", "Beatles", "Beatles", "Beatles", "Beatles", "ABBA", "Beatles" }
Call me old-fashioned, but I love these two bands! Unfortunately there is no way to make a compilation that doesnt have any repeats.
{"d 2","b 3","c 4"}
Returns: {"b", "c", "d", "b", "c", "c", "b", "c", "d" }
{"a 1","b 2","c 3","d 4","e 5","f 6","g 7","h 8","k 9","m 10","n 11","o 12","p 13","r 9"}
Returns: {"b", "c", "d", "e", "f", "g", "h", "k", "m", "n", "o", "p", "r", "a", "c", "d", "d", "e", "e", "e", "f", "f", "f", "f", "g", "g", "g", "g", "g", "h", "h", "h", "h", "h", "h", "k", "k", "k", "k", "k", "k", "k", "m", "m", "m", "m", "m", "m", "m", "m", "n", "n", "n", "n", "n", "n", "n", "n", "n", "o", "o", "o", "o", "o", "o", "o", "o", "o", "o", "p", "p", "p", "p", "p", "p", "p", "p", "p", "p", "p", "r", "r", "r", "r", "r", "r", "r", "b", "c", "d", "e", "f", "g", "h", "k", "m", "n", "o", "p", "r" }
100 elements
{"Beatles 2","ABBA 1"}
Returns: {"Beatles", "ABBA", "Beatles" }
Call me old-fashioned, but I love these two bands!
Submissions are judged against all 32 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MusicCompilation with a public method vector<string> makeCompilation(vector<string> artists) · 32 test cases · 2 s / 256 MB per case