Overview

This problem asks us to determine whether we can simultaneously satisfy the constraints on the number of books that can be inspected each day and the required number of inspections for each book, when inspecting \(M\) books over \(N\) days. This is a type of bipartite graph matching problem that can be solved efficiently using a greedy approach and cumulative sums.

Analysis

Reformulating the Problem

• Each book \(j\) must be inspected on \(R_j\) different days (since the same book cannot be inspected multiple times on the same day)
• Each day \(i\) can inspect at most \(L_i\) books

Issues with a Naive Approach

Directly computing the maximum matching on a bipartite graph (between days and books) would require \(O(NM)\) or more time complexity, which would result in TLE given the constraints \(N, M \leq 2 \times 10^5\).

Key Observation

Books that require more inspections need to use more “good days” (days with higher inspection capacity).

Consider after sorting: - Sort \(L\) in descending order: \(l_1 \geq l_2 \geq \cdots \geq l_N\) - Sort \(R\) in descending order: \(r_1 \geq r_2 \geq \cdots \geq r_M\)

Hall’s theorem-like condition: When considering “up to the \(k\)-th book with most required inspections,” we check whether the total inspection count required by those books can be covered by the inspection capacity each day can provide.

Specifically, for each \(k\): $\(\sum_{i=1}^{k} r_i \leq \sum_{j=1}^{N} \min(l_j, k)\)$

Meaning of the right-hand side: The total inspection count each day can provide for the top \(k\) books. Day \(j\) can inspect up to \(l_j\) books, but since there are only \(k\) books, it can only contribute \(\min(l_j, k)\) inspections.

Concrete Example

For \(N = 3, M = 2\), \(L = [3, 2, 1]\), \(R = [2, 2]\): - \(k = 1\): LHS \(= 2\), RHS \(= \min(3,1) + \min(2,1) + \min(1,1) = 1+1+1 = 3\) → OK - \(k = 2\): LHS \(= 2+2 = 4\), RHS \(= \min(3,2) + \min(2,2) + \min(1,2) = 2+2+1 = 5\) → OK

Algorithm

1. Sort \(L\) and \(R\) each in descending order
2. If \(\sum R > \sum L\), immediately output No (necessary condition)
3. Compute \(cnt[k]\) = “number of days where \(L_i \geq k\)”
4. For each \(k = 1, 2, \ldots, M\), check the following:
   • LHS: \(\sum_{i=1}^{k} r_i\) (computed using cumulative sum)
   • RHS: \(\sum_{j=1}^{k} cnt[j]\) (using the relation \(\sum_{j=1}^{N} \min(l_j, k) = \sum_{j=1}^{k} cnt[j]\))
   • If LHS > RHS, output No
5. If all \(k\) pass, output Yes

Supplement on the Right-Hand Side Formula

\(\sum_{j=1}^{N} \min(l_j, k)\) is “the total inspection count each day can provide (capped at \(k\)).” This equals \(\sum_{t=1}^{k} (\text{number of days where } l_j \geq t)\), which is \(\sum_{t=1}^{k} cnt[t]\).

Complexity

• Time complexity: \(O(N \log N + M \log M)\) (sorting is the bottleneck)
• Space complexity: \(O(N + M)\) (for storing arrays)

Implementation Notes

• When computing \(cnt[k]\), handle cases where \(L_i > M\) correctly (clip to \(M\))
• Compute the cumulative sum of \(cnt\) array from the back to get “count of values \(\geq k\)”
• Cases where the number of elements in \(R\) is less than \(k\) (i.e., \(k > M\)) need consideration, but looping up to \(M\) is sufficient

Source Code

def solve():
    import sys
    from collections import defaultdict
    
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    L = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    R = [int(input_data[idx + i]) for i in range(M)]
    idx += M
    
    # Each book j requires R[j] inspections, cannot inspect same book multiple times on same day
    # Each day i can inspect at most L[i] books
    
    # This can be thought of as a matching problem
    # Choose a set of days to inspect book j (|set| >= R[j])
    # Number of books chosen for each day i is <= L[i]
    
    # Hall's theorem approach:
    # Assign books with larger R[j] first to days with more capacity
    
    # Greedy approach: Books with larger R[j] need more days
    # Each book can be inspected on at most N days (once per day)
    
    # Condition: Assign each book j to R[j] different days
    # Each day i has at most L[i] books
    
    # This is a bipartite graph matching problem, but need efficient method for large N, M
    
    # Change of perspective:
    # sum(R) <= sum(L) is a necessary condition
    # Also, R[j] <= N is necessary (at most N times since once per day)
    
    # Stronger condition:
    # Sort L in descending order, sort R in descending order
    # Consider the assignment
    
    # Actually, this problem can be solved as follows:
    # Sort L in descending order, sort R in descending order
    # L[0], L[1], ..., L[N-1] (descending)
    # R[0], R[1], ..., R[M-1] (descending)
    # 
    # Book j needs R[j] days, can be assigned to top R[j] days with largest L values
    # 
    # Condition: For each k (1 <= k <= N)
    # "Number of books requiring k or more inspections" <= cumulative "number of days that can inspect k or more books"
    
    # count_R[k] = number of books with R[j] >= k
    # count_L[k] = number of days with L[i] >= k
    # 
    # For book j to be inspected R[j] times, use top R[j] days
    # Total inspections processable by day k = sum of min(L[i], k) for top k days
    
    # Alternative perspective:
    # Sort R in descending order: r_1 >= r_2 >= ... >= r_M
    # Sort L in descending order: l_1 >= l_2 >= ... >= l_N
    # 
    # Book i needs r_i days
    # Day j can handle up to l_j books
    # 
    # Condition: For any k, sum(r_1, ..., r_k) <= sum(min(l_1, k), ..., min(l_N, k))
    # That is, total inspections required by top k books <= total inspections each day can provide to top k books
    
    R_sorted = sorted(R, reverse=True)
    L_sorted = sorted(L, reverse=True)
    
    # Necessary condition: sum(R) <= sum(L)
    if sum(R) > sum(L):
        print("No")
        return
    
    # Check for each k
    # sum(R_sorted[:k]) <= sum(min(l, k) for l in L_sorted)
    
    # For efficient computation, use cumulative of L
    # cnt[k] = number of days with L[i] >= k
    cnt = [0] * (M + 2)
    for l in L_sorted:
        if l <= M:
            cnt[l] += 1
        else:
            cnt[M] += 1
    
    # Cumulative cnt[k] (count of values >= k)
    for k in range(M, 0, -1):
        cnt[k] += cnt[k + 1]
    
    # sum(min(l, k) for l in L_sorted) = sum over i of min(L_sorted[i], k)
    # = sum_{j=1}^{k} cnt[j]  (cnt[j] = count where L[i] >= j)
    
    prefix_R = 0
    capacity = 0
    
    for k in range(1, M + 1):
        if k <= len(R_sorted):
            prefix_R += R_sorted[k - 1]
        capacity += cnt[k]
        
        if prefix_R > capacity:
            print("No")
            return
    
    print("Yes")

solve()

---

This editorial was generated by claude4.5opus.