DOTIFYPLAY - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Tester & Editorialist: iceknight1093

DIFFICULTY:

1178

PREREQUISITES:

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.

3 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.

what will be the output for this test case