February 15

TopCoder – ListeningSongs

0  comments

Problem NameCompetitionDifficulty
ListeningSongsSRM 679Easy

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.

 

 


Tags


You may also like

Agile Estimation

Agile Estimation
{"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}

Subscribe to our newsletter now!

Get instant access to the Master C# 9 webinar to learn all the new exciting C# 9 features quickly.
Get regular videos and news on C# and .NET and offers on products and services to master C#.

We will collect, use and protect your data in accordance with our Privacy Policy.

>