Overview

There are \(N\) treasure chests and \(M\) keys. A key can open a chest if the key’s unlocking ability is greater than or equal to the chest’s lock strength. Find the maximum number of chests that can be opened.

Discussion

The goal of this problem is to “open as many treasure chests as possible.” Each chest requires a key whose unlocking ability is at least as large as the chest’s lock strength, and each key can only be used once, so we need to find a good matching.

Naive Approach (Greedy Matching)

The first idea that comes to mind is to use “the most available key among usable keys” for each chest. However, implementing this naively requires \(O(M)\) to search for a usable key each time, resulting in \(O(NM)\) overall, which is too slow.

Improvement: Sort and Process in Order

The key observation is as follows: - “Weak chests (small \(C_i\))” have “many usable keys” - “Strong chests” have “limited usable keys”

In other words, it is optimal to sort the chests in ascending order of strength and assign the smallest available key to each. This avoids wasting weak keys on chests that could have used them, preserving them for stronger chests.

The approach is as follows: 1. Sort the chest strengths \(C\) and the key unlocking abilities \(R\) in ascending order. 2. Process the chests from weakest to strongest, and for each chest, use the smallest unused key that satisfies \(R_j \geq C_i\). 3. This allows us to open the maximum number of chests while consuming keys efficiently.

For Efficient Implementation

Since the key list \(R\) is sorted, we can quickly find “the smallest position among unused keys that is at least a given value \(c\).” This is possible using binary search (bisect.bisect_left).

Algorithm

1. Sort the chest strength list \(C\) and the key unlocking ability list \(R\) in ascending order.
2. Set the key usage start position r_index to 0.
3. For each chest strength \(c\), do the following:
   • Use binary search to find the first position in \(R\) from r_index onward where the value is at least \(c\).
   • If such a position exists, consider that chest opened (count += 1) and advance r_index by 1.
4. Output the final count.

This algorithm optimally assigns the necessary keys to each chest.

Example

Sample input:

N = 3, M = 4
C = [3, 1, 4]
R = [2, 5, 1, 3]

After sorting:

C = [1, 3, 4]
R = [1, 2, 3, 5]

Processing: - Chest 1 (\(c=1\)) → Opened with key 1 (\(r=1\)) (next search starts from index=1) - Chest 2 (\(c=3\)) → Opened with key 3 (\(r=3\)) (next search starts from index=3) - Chest 3 (\(c=4\)) → Opened with key 4 (\(r=5\)) (next search starts from index=4)

→ A total of 3 chests can be opened.

Complexity

• Time complexity: \(O(N \log N + M \log M)\) (cost of sorting and binary search)
• Space complexity: \(O(1)\) (no additional large arrays are used)

Implementation Notes

• \(C\) and \(R\) must be sorted in ascending order.

• By using bisect.bisect_left(R, c, r_index) to limit the search range, we can efficiently search among unused keys.

• After using a key, advance r_index to prevent reuse.

  Source Code

import bisect

N, M = map(int, input().split())
C = list(map(int, input().split()))
R = list(map(int, input().split()))

C.sort()
R.sort()

count = 0
r_index = 0

for c in C:
    r_index = bisect.bisect_left(R, c, r_index)
    if r_index < M:
        count += 1
        r_index += 1

print(count)

---

This editorial was generated by qwen3-coder-480b.