Overview

Given \(2N\) candidate songs, we want to select and arrange songs to create a playlist whose total playback time is at least \(K\) seconds, while minimizing the maximum length of consecutive songs of the same genre (bias score).

Analysis

Key Insight: Binary Search on the Answer

By fixing the bias score \(L\), we can reduce the problem to a decision problem: “Can we achieve the condition with a score of \(L\) or less?” Since larger \(L\) relaxes the constraint, binary search on the answer is applicable.

Solving the Decision Problem

The condition for the bias score to be at most \(L\) is that there exists an arrangement where no genre has more than \(L\) consecutive songs.

When arranging a playlist of \(T\) songs with the maximum consecutive count at most \(L\), the upper bound \(M\) on the number of songs selectable from each genre is given by:

\[M = \left\lfloor \frac{L \times (T+1)}{L+1} \right\rfloor\]

This is derived from the pattern “after placing \(L\) songs, insert 1 song of a different genre.” For example, if \(T=7, L=2\), we can arrange like AA_AA_A, and use at most \(M = \lfloor 2 \times 8 / 3 \rfloor = 5\) songs from one genre.

Greedy Approach

Once \(T\) and \(M\) are determined, it suffices to include up to \(M\) songs with the longest playback times from each genre as candidates, then select the top \(T\) songs from all candidates and check whether their total is at least \(K\) (since we want to maximize total playback time).

Algorithm

1. If the total of all songs is less than \(K\), output -1.
2. Sort the songs in each genre in descending order of playback time.
3. Binary search for the answer \(L\) (range \([1, 2N]\)).
4. Decision function check(L):
   • For \(T = 1, 2, \ldots, 2N\):
     • Compute \(M = \lfloor L(T+1)/(L+1) \rfloor\)
     • Collect the top \(\min(|genre|, M)\) songs from each genre as candidates
     • Sort candidates in descending order, and if the total of the top \(T\) songs is at least \(K\), return true
5. Output the minimum \(L\) for which check(L) returns true.

Complexity

• Time complexity: \(O(N^2 \log^2 N)\)
  • Binary search: \(O(\log N)\) iterations
  • Each decision: iterate \(T\) from \(1\) to \(2N\), with \(O(N \log N)\) sorting and aggregation per iteration → \(O(N^2 \log N)\)
• Space complexity: \(O(N)\)

Since \(N \leq 150\), this runs sufficiently fast.

Implementation Notes

• Pre-sorting by genre: By sorting each genre’s songs in descending order of playback time beforehand, we can immediately retrieve the top \(M\) songs during the decision step.

• Formula for \(M\): \(\lfloor L(T+1)/(L+1) \rfloor\) correctly gives “the maximum number of songs one genre can occupy among \(T\) songs.” This is derived from the constraint that at least 1 song of a different genre is required every \((L+1)\) songs.

• Necessity of trying all \(T\): Since \(M\) cannot be determined without fixing the number of songs \(T\), we need to try all values of \(T\). This cannot be omitted because there may be cases where \(K\) is achieved with a small number of songs.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    long long K;
    cin >> N >> K;
    
    int songs = 2 * N;
    vector<int> B(songs), A(songs);
    
    map<int, vector<int>> genre_map;
    long long total_sum = 0;
    
    for (int i = 0; i < songs; i++) {
        cin >> B[i] >> A[i];
        genre_map[B[i]].push_back(A[i]);
        total_sum += A[i];
    }
    
    if (total_sum < K) {
        cout << -1 << endl;
        return 0;
    }
    
    vector<vector<int>> genre_songs;
    for (auto& [g, v] : genre_map) {
        sort(v.begin(), v.end(), greater<int>());
        genre_songs.push_back(v);
    }
    
    int num_genres = genre_songs.size();
    
    auto check = [&](int L) -> bool {
        for (int T = 1; T <= songs; T++) {
            long long M = (long long)L * (T + 1) / (L + 1);
            
            vector<int> eligible;
            eligible.reserve(songs);
            
            for (int g = 0; g < num_genres; g++) {
                int take = min((long long)genre_songs[g].size(), M);
                for (int j = 0; j < take; j++) {
                    eligible.push_back(genre_songs[g][j]);
                }
            }
            
            if ((int)eligible.size() < T) continue;
            
            sort(eligible.begin(), eligible.end(), greater<int>());
            
            long long sum = 0;
            for (int i = 0; i < T; i++) {
                sum += eligible[i];
            }
            
            if (sum >= K) return true;
        }
        return false;
    };
    
    int lo = 1, hi = songs;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (check(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    
    cout << lo << endl;
    return 0;
}

This editorial was generated by claude4.6opus-thinking.