Overview

From \(2N\) songs, select songs such that the total playback time is at least \(K\) seconds, and minimize the maximum number of consecutive songs of the same genre (bias score) when arranging them. Among all valid selections and arrangements of songs that satisfy the conditions, find the minimum bias score.

Analysis

1. Conditions for Bias Score \(X\)

When \(M\) songs are selected, let \(n_g\) be the number of songs belonging to a specific genre \(g\). Consider the condition under which these \(M\) songs can be arranged to achieve a bias score of at most \(X\).

The number of songs not in genre \(g\) is \(M - n_g\). Using these as “dividers,” there are \((M - n_g + 1)\) positions where songs of genre \(g\) can be placed (before, after, and between the dividers). Since at most \(X\) songs of genre \(g\) can be placed in each position, the bias score can be kept at most \(X\) if the following inequality holds: $\(n_g \leq X \times (M - n_g + 1)\)$

Solving for \(n_g\): $\(n_g \leq \frac{X(M+1)}{X+1}\)\( Since the number of songs must be an integer, \)n_g \leq \lfloor \frac{X(M+1)}{X+1} \rfloor\(. In other words, this can be rephrased as the constraint that **at most \)C = \lfloor \frac{X(M+1)}{X+1} \rfloor$ songs can be selected from any single genre**.

2. Binary Search on the Answer

The smaller the bias score \(X\), the stricter the condition becomes, and the larger it is, the more relaxed. Using this monotonicity, we find the minimum \(X\) via binary search.

3. Designing the Check Function (Greedy Approach)

For a fixed \(X\), determine whether there exists a valid selection of songs satisfying the conditions. Try all possible values of the number of selected songs \(M\) from \(1\) to \(2N\). For each \(M\), the following strategy maximizes the total playback time: 1. Within each genre, sort songs in descending order of playback time. 2. From all songs, consider only those that are “within the top \(C\)” in their genre as candidates. 3. Select \(M\) songs from the candidates in descending order of playback time, and check whether their total is at least \(K\).

Algorithm

1. Preprocessing:
   • Group songs by genre and sort each genre in descending order of playback time.
   • For each song, record “its rank within its genre by playback time (rank).”
2. Binary Search:
   • Binary search for bias score \(X\) in the range \([1, 2N]\).
3. Check Function check(X):
   • Loop \(M\) from \(1\) to \(2N\).
   • For each \(M\), compute the upper limit \(C = \lfloor \frac{X(M+1)}{X+1} \rfloor\) on the number of songs selectable from each genre.
   • Select \(M\) songs with in-genre rank at most \(C\) in descending order of playback time, and return true if their total is at least \(K\).
4. Output:
   • Output the minimum \(X\) found by binary search. If the condition is never satisfied, output \(-1\).

Complexity

• Time Complexity: \(O(N^2 \log N)\)
  • Sorting songs: \(O(N \log N)\)
  • Number of binary search iterations: \(O(\log N)\)
  • Check function: Loop over \(M\) (\(2N\) iterations) \(\times\) scanning songs (\(2N\) iterations) = \(O(N^2)\)
  • Overall \(O(N^2 \log N)\), which is sufficiently fast for \(N=150\).
• Space Complexity: \(O(N)\)
  • Used for lists storing song information, etc.

Implementation Notes

• Sorting optimization: Sorting inside the check function every time could be slow, so it is efficient to pre-sort all songs in “descending order of playback time” and only compare ranks within the check function to select \(M\) songs.

• When \(M\) songs cannot be selected: If the restriction on \(C\) makes it impossible to select a total of \(M\) songs, skip that value of \(M\) as infeasible.

• Handling \(C=0\): When \(X\) or \(M\) is small, \(C\) may become \(0\). In this case, no songs can be selected from that genre.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Problem Analysis:
 * We need to find the minimum bias score X such that we can select M songs (1 <= M <= 2N)
 * with a total duration >= K and arrange them so that no more than X consecutive songs
 * are of the same genre.
 * 
 * The condition for an arrangement of M songs to have a bias score of at most X is that
 * for each genre g, the number of songs selected from that genre, n_g, must satisfy:
 * n_g <= X * (M - n_g + 1)
 * This simplifies to:
 * n_g * (X + 1) <= X * (M + 1)
 * n_g <= floor(X * (M + 1) / (X + 1))
 * 
 * To maximize the total duration for a fixed bias score X and total song count M, 
 * we should pick the M largest duration songs across all genres, with the restriction 
 * that we can pick at most C = floor(X * (M + 1) / (X + 1)) songs from each genre.
 */

struct Song {
    int duration;
    int rank; // rank of the song within its genre (1-indexed, largest duration is rank 1)
};

int main() {
    // Optimize I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long K;
    if (!(cin >> N >> K)) return 0;

    // Group songs by genre
    vector<vector<int>> genre_songs(2 * N + 1);
    for (int i = 0; i < 2 * N; ++i) {
        int b, a;
        cin >> b >> a;
        if (b >= 1 && b <= 2 * N) {
            genre_songs[b].push_back(a);
        }
    }

    // Sort songs within each genre and store them with their genre-rank
    vector<Song> all_songs;
    for (int i = 1; i <= 2 * N; ++i) {
        if (genre_songs[i].empty()) continue;
        sort(genre_songs[i].rbegin(), genre_songs[i].rend());
        for (int j = 0; j < (int)genre_songs[i].size(); ++j) {
            all_songs.push_back({genre_songs[i][j], j + 1});
        }
    }

    // Sort all songs by duration in descending order
    sort(all_songs.begin(), all_songs.end(), [](const Song& a, const Song& b) {
        if (a.duration != b.duration) return a.duration > b.duration;
        return a.rank < b.rank;
    });

    // Check if a bias score X is achievable
    auto check = [&](int X) {
        for (int M = 1; M <= 2 * N; ++M) {
            // Maximum songs allowed per genre for this M and X
            long long C = (long long)X * (M + 1) / (X + 1);
            if (C == 0) continue; 

            long long current_sum = 0;
            int count = 0;
            // Greedily pick the M best available songs
            for (const auto& song : all_songs) {
                if (song.rank <= C) {
                    current_sum += (long long)song.duration;
                    count++;
                    if (count == M) break;
                }
            }
            // If we found exactly M songs and their sum is >= K, X is achievable
            if (count == M && current_sum >= K) return true;
        }
        return false;
    };

    // Binary search for the minimum achievable bias score X
    int low = 1, high = 2 * N;
    int ans = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (check(mid)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    cout << ans << endl;

    return 0;
}

This editorial was generated by gemini-3-flash-thinking.