SRM 679, D2, 250-Pointer (ListeningSongs)

James S. Plank

Tue Sep 13 22:54:52 EDT 2016
It's best to think about this problem in parts, solving each part before proceeding to the next part:

Part 1: An album doesn't have T songs

This case is illustrated in example 6, but it comes from the constraints -- durations1 and durations2 can contain between 1 and 100 elements, and T will be between 1 and 100. There is nothing in the constraints that says that durations1.size() or durations2.size() is ≥ T.

So test for this case first, and return -1 if either vector is too small. Test it on example six.


Part 2: You should to listen to the T shortest songs on each album

The best way to figure this out is to sort both vectors, and then sum up the first T durations in both vectors. If that number is too big, return -1. Otherwise, subtract the number from the total number of seconds (you'll have to multiply minutes by 60). That's the amount of time you have left after listening to T songs on each album.

Part 3: Of the remaining songs, listen to the shortest ones until you run out of time, or you run out of songs

To do this, create a third vector. I called mine "FD" for "final durations." Create this from the songs in the two vectors that are not in the first T songs of either vector.

Now sort FD, and run through it, seeing if you can listen to each song. Return if you can't listen to a song. If you finish FD, you're done -- you can listen to all of the songs!


In sum, this program tripped up a lot of topcoders, but if you split it into parts, and use the sort() method from the algorithms library, the solution is pretty straightforward.

My Solution.