A record shop has room for only k listening stations, and each station plays one song from the catalogue. A customer who likes song s walks to the station whose song is closest to s (Euclidean distance between the song vectors [tempo, energy, acoustic, vocals]). The shop wants every song in the catalogue to have a station that sounds like it: it wants the total, over all songs, of the distance from the song to its closest station song, to be as small as possible.
Write choose_stations(songs, k) that returns a list of k different song indices. station_total(songs, stations) computes the total for your choice, and song_table(n, seed) builds the catalogues used by the tests; both are available in your code.
How this problem is scored
There is no single right answer. A choice passes if it has exactly k different valid indices and its total is no larger than the total you get by adding stations one at a time: start with no stations, and k times add the song that lowers the total the most (with no station yet, the total counts every song's distance to the new station). Its quality (0 to 100) says how much of the gap between that simple choice and the best choice we know you close: 0 matches the one-at-a-time choice, 100 matches or beats the best known one. Match the reference solution's quality (the par in the header) for the third star.
Examples
Input: songs = [[70, 20, 80, 60], [72, 25, 85, 55], [125, 80, 15, 40], [130, 85, 10, 35], [120, 78, 20, 45]], k = 2
Output: a list such as [0, 2]
Explanation: one station for the two quiet acoustic songs and one for the three loud ones. The total
is the distance from song 1 to song 0 plus the distances from songs 3 and 4 to song 2, about 27.8.
Constraints
100 <= len(songs) <= 300,3 <= k <= 12- the tests call
choose_stations(song_table(n, seed), k); no randomness or clock is needed, and results must not depend on the clock - keep the work bounded (a fixed number of rounds): each test must finish well within a second
Goals
- Measure how well a few chosen rows represent a whole dataset
- Build a choice greedily, one representative at a time
- Improve a choice by moving representatives towards the middle of their groups