Editorial for WC '15 Contest 1 J3 - Jazz Concert


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

This is a basic implementation problem. We want to make the concert as long as possible by picking two of the N songs to repeat. Obviously, we should always pick two of the longest songs. In the end, we add up the lengths of all the songs in the input, add again the sum of the lengths of the two longest songs, and finally add 10 for the time of the intermission.

How do we find the lengths of the two longest songs? One way is to store all the song lengths into an array and sort the array. If we sort the array in descending order, the two longest lengths will be at the first and second indices of the array (since it's guaranteed that there are at least two songs). If we sort the array in ascending order, the two longest lengths will be at the last and second last indices. Many languages come up with built-in sort functions, so it is a viable way to approach the problem.

However, using arrays and sorting may seem like overkill for just finding the top two elements. As it turns out, we can also solve the problem by processing each song length as we read them in – there is no need to store all of them at once! We keep two variables: the top value (maximum length) we've encountered so far and the second value (next greatest length) we've encountered so far. For every new T value we read in, we add it to the running total and update the two variables as follows. If T is greater than the top value, we set the second value to the top value and then update the top value to T. It is important to do it in this order, otherwise we would be setting the second value to T and not the old top value. At the end, we add 10 along with these two variables to the running total and output the result.


Comments

There are no comments at the moment.