Overview

There are N event requests, and after a rival company cancels K of them, we need to select from the remaining requests such that no times overlap, maximizing the total reward.

Analysis

Since the constraint is small with N≤8, we can exhaustively search all combinations of K requests to cancel. For each cancellation pattern, we need to make the optimal selection from the remaining requests. As a typical approach for event scheduling problems, we sort by end time and then use dynamic programming (DP) to compute the maximum reward.

Algorithm

1. Exhaustively search all combinations of K requests to cancel
2. For each combination, sort the remaining requests in ascending order of end time
3. Prepare a DP table dp[t] that holds the maximum reward obtainable up to time t
4. For each time t, carry over the value from the previous time
5. For requests with end time t, update DP[t] with the value of DP at start time L plus the reward V
6. The answer is the minimum of the maximum rewards across all cancellation patterns

Complexity

• Time complexity: \(O(2^N \cdot N \cdot T)\) (where T is the maximum time)
• Space complexity: \(O(N + T)\)

Implementation Notes

• Use itertools.combinations to generate cancellation combinations

• Process remaining requests sorted by end time

• When updating DP, process requests with the same end time together

• The maximum time is dynamically computed from the input

  Source Code

import itertools

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0]); k = int(data[1])
    events = []
    index = 2
    max_time = 0
    for i in range(n):
        L = int(data[index]); R = int(data[index+1]); V = int(data[index+2])
        index += 3
        events.append((L, R, V))
        if R > max_time:
            max_time = R
            
    # すべてのキャンセル組み合わせを生成
    indices = list(range(n))
    ans = 10**9
    # K個キャンセルする全ての組み合わせ
    for cancel_set in itertools.combinations(indices, k):
        remaining = []
        for i in range(n):
            if i not in cancel_set:
                remaining.append(events[i])
        # 残った依頼を終了時刻でソート
        remaining.sort(key=lambda x: x[1])
        dp = [0] * (max_time+1)
        # DP: 時刻0から最大時刻まで
        t_index = 0
        for t in range(1, max_time+1):
            dp[t] = dp[t-1]
            while t_index < len(remaining) and remaining[t_index][1] == t:
                L, R, V = remaining[t_index]
                if dp[L] + V > dp[t]:
                    dp[t] = dp[L] + V
                t_index += 1
        total_reward = dp[max_time]
        if total_reward < ans:
            ans = total_reward
            
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.