Overview

This is a problem of assigning \(N\) delivery workers to \(M\) delivery requests. First, we determine whether all requests can be assigned, and if so, we maximize the number of “exact” assignments (where \(A_i = B_j\)).

Analysis

Key Insight 1: Feasibility Check

Whether all requests can be assigned can be determined using a greedy method. Sort \(A\) and \(B\), then attempt matching from the largest values. It is optimal to assign, for each large value of \(B\) in order, the smallest \(A\) that can satisfy it.

Specifically, scanning \(A\) and \(B\) in descending order, if \(A[i] \geq B[j]\), the assignment succeeds and we advance both pointers; otherwise, we advance only \(A\). If all elements of \(B\) are assigned by the end, the assignment is feasible.

Key Insight 2: Maximum Number of Exact Matches

For each value \(v\), if \(A\) contains \(c_A(v)\) copies and \(B\) contains \(c_B(v)\) copies, the maximum number of exact matches for value \(v\) is \(\min(c_A(v), c_B(v))\).

Core insight: Even if we use as many exact matches as possible for all values, the feasibility of assigning the remaining elements is preserved.

Why Feasibility Is Preserved (Intuitive Explanation)

Removing exact matches (\(A_i = B_j = v\)) is equivalent to removing the same number of elements with the same value from both \(A\) and \(B\). For example:

• \(A = [1, 2, 3, 3, 5]\), \(B = [2, 3, 4]\)
• Exact matches: 1 pair at value 2, 1 pair at value 3 (2 pairs total)
• Remaining: \(A = [1, 3, 5]\), \(B = [4]\) → \(5 \geq 4\), so assignment is possible

Since removing the same value from both sides does not change (or even improves) the difference between “the number of elements in \(A\) that are \(\geq B[j]\)” and “the number of elements in \(B\) that are \(\geq B[j]\)”, feasibility is maintained.

Algorithm

1. Sort \(A\) and \(B\)
2. Check feasibility using the greedy method (output -1 if infeasible)
3. Count the occurrences of each value in \(A\) and \(B\)
4. Sum \(\min(c_A(v), c_B(v))\) over each value \(v\); this is the answer

Answer = Σ min(count_A[v], count_B[v])  (for all values v appearing in B)

Complexity

• Time complexity: \(O(N \log N + M \log M)\) (dominated by sorting)
• Space complexity: \(O(N + M)\) (for counters)

Implementation Notes

• Feasibility check: Use a greedy method scanning from the end (largest values) of the arrays. Move two pointers \(i\) and \(j\) from the end; if \(A[i] \geq B[j]\), advance both; otherwise, advance only \(i\).

• Using Counter: Python’s collections.Counter conveniently computes the occurrence count of each value.

• Fast input: By using sys.stdin.buffer.read() to read all input at once, we avoid TLE even with large amounts of data.

  Source Code

from collections import Counter

def solve():
    import sys
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    A = [int(input_data[idx + i]) for i in range(N)]; idx += N
    B = [int(input_data[idx + i]) for i in range(M)]; idx += M
    
    A.sort()
    B.sort()
    
    # First check if assignment is possible at all using greedy matching
    # Match largest B with smallest sufficient A (greedy from right)
    # Standard check: sort both, try to match B[j] with A[i] where A[i] >= B[j]
    # Greedy: iterate from the end
    
    # Check feasibility: for each j from M-1 to 0, we need A[i] >= B[j]
    # Greedy feasibility check: match B sorted desc with A sorted desc
    j = M - 1
    i = N - 1
    while j >= 0 and i >= 0:
        if A[i] >= B[j]:
            j -= 1
            i -= 1
        else:
            i -= 1
    
    if j >= 0:
        print(-1)
        return
    
    # Now maximize the number of exact matches (A[i] == B[j])
    # Count exact matches available
    count_a = Counter(A)
    count_b = Counter(B)
    
    # Maximum possible exact matches
    max_exact = sum(min(count_a[v], count_b[v]) for v in count_b)
    
    # But we need to check if we can achieve max_exact exact matches while still
    # being able to assign the remaining B's to remaining A's.
    
    # Binary search on the number of exact matches: can we achieve at least k exact matches?
    # Actually, let's think differently. We want to maximize exact matches.
    # 
    # Key insight: We can binary search on the answer k.
    # For a given k exact matches, we need to verify feasibility.
    # 
    # Better approach: try to use as many exact matches as possible.
    # We can binary search: is it possible to have at least k exact matches?
    #
    # For checking: we decide to make k exact matches. We want to maximize exact,
    # so we try k = max_exact and decrease if not feasible.
    #
    # Actually, let's think about it greedily.
    # Sort A and B. For each value v, we can use min(count_a[v], count_b[v]) exact matches.
    # After removing exact-matched pairs, we need to match remaining B's with remaining A's
    # such that A[i] >= B[j]. This is always possible if the original full matching is possible
    # and we only removed equal pairs.
    #
    # Proof: If we remove k pairs where A[i]=B[j], the remaining A's and B's still satisfy
    # the feasibility condition. Because for the remaining sorted arrays, removing equal
    # elements from both sides preserves the greedy matching property.
    
    # Let me verify: after removing all possible exact matches, check if remaining can be matched.
    # Build remaining A and B after removing exact matches.
    
    remaining_a = []
    remaining_b = []
    
    used_a = Counter()
    for v in count_b:
        exact = min(count_a[v], count_b[v])
        used_a[v] = exact  # exact matches used from A for value v
    
    # Remaining A: for each value, count_a[v] - used_a[v]
    # Remaining B: for each value v, count_b[v] - min(count_a[v], count_b[v])
    
    for v in sorted(count_a):
        rem = count_a[v] - used_a.get(v, 0)
        remaining_a.extend([v] * rem)
    
    for v in sorted(count_b):
        exact = min(count_a[v], count_b[v])
        rem = count_b[v] - exact
        remaining_b.extend([v] * rem)
    
    # Check if remaining can be matched
    j2 = len(remaining_b) - 1
    i2 = len(remaining_a) - 1
    while j2 >= 0 and i2 >= 0:
        if remaining_a[i2] >= remaining_b[j2]:
            j2 -= 1
            i2 -= 1
        else:
            i2 -= 1
    
    if j2 >= 0:
        # This shouldn't happen if the overall matching is feasible and we only removed equal pairs
        # But just in case, we could reduce exact matches. For safety:
        # Actually this can't happen. Removing equal pairs preserves feasibility.
        # But let me handle it anyway - shouldn't reach here.
        print(-1)
        return
    
    print(max_exact)

solve()

---

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