LEMUSIC - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Vitaliy Herasymiv
Tester: Hiroto Sekido
Editorialist: Anton Lunyov

DIFFICULTY:

EASY

PREREQUISITES:

Greedy algorithm, Sorting algorithms

PROBLEM:

The best described in the problem itself.

QUICK EXPLANATION:

The solution is based on several simple observations:

  • Let M be the total number of bands among all songs.
  • The first M songs should be of different bands. Otherwise we can swap some songs and the sweetness will increase.
  • The lengths of first songs are multiplied by smaller numbers, hence it is advantageous to listen first M songs from the shortest to the longest.
  • Also for the first M songs we should choose the shortest song from each band. Otherwise swapping some songs we could increase sweetness.
  • These rules uniquely determine the answer (see details below).

Here we only mention that maximal value of the answer is about 5e18 and fits into signed 64bit integer type. Indeed, the maximal answer will be when there are 1e5 songs, all bands among them are different and each song has length 1e9. Then the total sweetness is
1e9 + 2 * 1e9 + 3 * 1e9 + … + 1e5 * 1e9 ≅ 1e5 * 1e5 / 2 * 1e9 = 5e18,
while 263 is slightly larger than 9e18.

EXPLANATION:

Here we describe in detail IMHO the simplest implementation of the above solution.

We store initial data as an array of pairs a[] with lexicographical ordering. We denote the first element in pair as B and the second as L. After input the songs we sort them. So they will be sorted by band, and songs with the same band sorted by length in increasing order. Thus, the beginning of the solution looks as follows:

for i = 1 to N do
   read a[i].B, a[i].L
sort a

Next we do one iteration over this array and count the number of different bands, form the list of shortest songs for each band and calculate the total length of the remaining songs:

songs = {}
total = 0
for i = 1 to N do
   if i = 1 or a[i-1].B < a[i].B then
      add a[i].L to songs
   else
      total = total + a[i].L
M = size of songs

Why such simple loop does the job?
Note that when i = 1 or a[i-1].B < a[i].B then the song a[i] is the shortest song for the band a[i].B and hence we add it to the list of songs played first. While otherwise it is the song that will be played after the first M songs and hence its length should be multiplied by M, so we just need to find the total length of all such songs.

Finally we sort the list songs and calculate the sweetness for it by definition and also add M * total to this value to get the answer:

ans = M * total
for i = 1 to M do
   ans = ans + i * songs[i]

Refer to the editorialist’s solution as a good reference to this implementation.

ALTERNATIVE SOLUTION:

There exists of course many other different implementations of the above solution.
See, for example, the tester’s solution.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be provided soon.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

RELATED PROBLEMS:

Will be provided soon. All readers are welcomed to provide related problems in comments.

2

Thanks to this problem that I learnt some Python. Here is my implementation on that.

3

I got the fastest submission in Python. For a better reference see this

3 Likes
4

thanks dude, as I am new to Python. That will help me later.

5

I used the same algorithm explained above. But the code implementation is little bit different. Can anyone tell me the mistake in my code?

http://www.codechef.com/viewsolution/2038189

6

@muttakyn You have long overflow when multiply current and song[i].L as well as last and song[i].L.
Fixing this leads to AC: http://www.codechef.com/viewsolution/2056576

7

Thanks… I can not imagine what a silly mistake I made!! :frowning: I went foolish

1 Like
8

just an advice… define your program inside a main function and I think you will get a faster submission than mine… if it works dont forget to tell me… :slight_smile:

1 Like
9

@devanshug >> Its giving me a ~1.5 seconds boost (total time 14.31 seconds to be precise, earlier 15.71 seconds). I would like to know the theory behind it. http://www.codechef.com/viewplaintext/2059408

1 Like
10

Visit http://wiki.python.org/moin/PythonSpeed/PerformanceTips#Local_Variables

3 Likes
11

Thanks. :slight_smile:

12

mast hai…

1 Like
13

I was working on another approach.
I sorted the list in increasing order on the lengths of the songs(irrespective of their bands).
Then I calculated the answer.
here’s the link:link text
Can anybody please tell me where does approach fail?
Thanks in advance.

14

Consider, for example, the test:
3
1 1
1 2
2 3
The optimal way is to play (1,1), then (2,3) and then (1,2).
The sweetness will be 1 * 1 + 2 * 3 + 2 * 2 = 11.

While you will play them in the order (1,1), (1,2), (2,3)
and sweetness will be 1 * 1 + 1 * 2 + 2 * 3 = 9 < 11.

1 Like
15

thanks a lot.

16

I am using the same logic as explained above but I am still getting wrong answer. Why?
http://www.codechef.com/viewsolution/6356487

17

My easy approach is to first make an unsorted map and a vector called repeat.

Out goal is to store all the b with smallest l corresponding to them in the map and length of all other occurrences of b in the vector called repeat.

Now, we make another vector called first which will store the values of l from the map.

We sort both the vectors.

Now we calculate the sweetness as follows:

llint sweetness = 0;
int nos = first.size();
for (int i = 0; i < nos; i++)                   sweetness += (first[i]*(i+1));
for (int i = 0; i < repeat.size(); i++)         sweetness += (repeat[i]*nos)

Here is the link to my code

18

I was working on another approach. I sorted the list in increasing order on the lengths of the songs(irrespective of their bands and separate the repeated band in another list then calculate sweetness). Then I add both of them.link text Can anybody please tell me where does approach fail?
https://www.codechef.com/viewsolution/22331045
Thanks in advance.

19

I was working on another approach. I sorted the list in increasing order on the lengths of the songs(irrespective of their bands and separate the repeated band in another list then calculate sweetness). Then I add both of them. it show TLE every time,…
https://www.codechef.com/viewsolution/22331045
Thanks in advance.