# DOTIFYPLAY - Editorial

Tester & Editorialist: iceknight1093

1178

None

# PROBLEM:

You have N songs saved on your Dotify app. The i-th song is M_i minutes long and in language L_i.
Find the longest playlist you can make if:

• Exactly K songs from these N should be chosen
• Each song should be of language L

# EXPLANATION:

We only care about songs whose language is L.
So, let’s create a list of the lengths of only these songs, say A.

We now want to choose K elements from A such that their sum is as large as possible.
So,

• If the length of A is less than K, choosing K songs is of course impossible.
In this case, the answer is -1.
• Otherwise, clearly it’s optimal to choose the largest K elements of A and find their sum.

A simple way to do this is to sort A and then take the sum of its last K elements.
However, the constraints here are small, so a solution in \mathcal{O}(N\cdot K) that repeats “find the maximum element in A, add it to the sum, and then remove it from A”, K times, will also get AC.

# TIME COMPLEXITY

\mathcal{O}(N\log N) or \mathcal{O}(N\cdot K) per test case.

# CODE:

Editorialist's code (Python, sorting)
for _ in range(int(input())):
n, k, l = map(int, input().split())
songs = []
for i in range(n):
x, y = map(int, input().split())
if y == l: songs.append(x)
songs.sort()
songs = songs[::-1]
if len(songs) < k: print(-1)
else: print(sum(songs[:k]))

Editorialist's code (Python, no sorting)
for _ in range(int(input())):
n, k, l = map(int, input().split())
songs = []
for i in range(n):
x, y = map(int, input().split())
if y == l: songs.append(x)
if len(songs) < k: print(-1)
else:
ans = 0
for i in range(k):
M = max(songs)
ans += M
songs.remove(M)
print(ans)


hey @iceknight1093, in the problem statement it was mentioned that the k songs chosen should be distinct, but the solution that you have given does not consider that.

2 Likes

That just means that the same song can’t be selected twice. Are you maybe thinking that the Lengths should also be distinct? The statement does not say so.