SRM 679, D2, 250-Pointer (ListeningSongs)

James S. Plank

Tue Sep 13 22:54:52 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: January, 2016
Competitors who opened the problem: 572
Competitors who submitted a solution: 488
Number of correct solutions:299
Accuracy (percentage correct vs those who opened): 52.3%
Average Correct Time: 21 minutes, 7 seconds.

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.

Running time analysis

Let n be the size of the largest vector (durations1 or durations2).

Part 1 is clearly O(1).

Part 2 is clearly O(n log n), (because sorting a vector with n elements is O(n log n), and sorting two vectors with n elements is also O(n log n)).

Part 3 is O(m log m) where m is equal to 2(n-T). If we assume that n is larger than T, then m is O(n) (because 2(n-T) is linear in n). So, Part 3 is O(n log n). This means the overall running time is O(n log n).

As I mentioned in class, you can make Part 3 O(n) if you retain the two vectors from Part 2, start at the T-th element of each, and add up the shortest songs from each vector. Since there is not a second sorting step to this, it is O(n). When you learn merge sort in CS302, this is equivalent to the "merge" operation.