TopCoder – ListeningSongs

Problem Name Competition Difficulty
ListeningSongs SRM 679 Easy

Solution

Full source code is available here.

I found this problem a bit more involved in terms of coding for an easy problem. Lucky with LINQ the code is relatively compact but I think people competing with other languages could have find it a bit long.

From the requirements, we must listen at least T songs from each album. So we return -1 if there not at least T songs in each album.

2016-02-12 15_14_40-Start

We can now calculate the minimum time needed to listen T songs from each album. Obviously we take the shortest songs from each album to minimize this number. If this time is greater than the allowed time we return -1. Note that we must convert the minutes in seconds!

2016-02-12 15_16_47-Start

At this point, we know that we can at least listen 2 * T songs that in total takes time seconds.

Now, we don’t have any album constraints so we can listen the next shortest song from any of the two albums. We can do this until we have enough time.

We can take the two durations array, remove the first T songs, concatenate them and sort the result. In this way we have the remaining list of songs ordered by duration. We then iterate through the list, adding each duration to the time and counting the listened songs.

2016-02-12 15_21_36-Start

Follow the complete implementation:

2016-02-12 15_22_35-Start

 

Personal Notes

  • Use Contact() to concatenate two sequences and keep duplicates.
  • Use Union() to concatenate two sequences and remove duplicates. I made this silly mistake during the competition and I failed system tests 🙁
  • LINQ made implementing this problem so much easier. I invite you to try doing it in Java.

 

 

Permanent link to this article: https://www.productivecsharp.com/2016/02/listeningsongs/


Warning: in_array() expects parameter 2 to be array, null given in /home/andreaa9/public_html/wp-content/themes/graphene/inc/plugins.php on line 92
>