Overview

This is a problem where, given \(N\) types of products, we need to find how many products have a price within the budget for every day of the training camp.

Analysis

Key Insight

Consider the condition “for all days \(j\), \(R_i \leq S_j\).” For product \(i\)’s price \(R_i\) to be within the budget on every day, it is sufficient that the price is within the budget even on the day with the tightest budget (the day with the minimum budget).

Let’s consider a concrete example. If the training camp lasts 3 days with budgets \(S = [500, 300, 400]\): - The minimum budget is \(300\) yen - A product priced at \(300\) yen or less clears the \(300\) yen day, the \(400\) yen day, and the \(500\) yen day — all of them - Conversely, a product priced at \(301\) yen or more exceeds the budget on the \(300\) yen day

In other words, the condition “for all \(j\), \(R_i \leq S_j\)” is equivalent to “\(R_i \leq \min(S_1, S_2, \ldots, S_M)\).”

Problem with the Naive Approach

Comparing each product against every day’s budget would result in \(O(N \times M)\) time complexity. Since \(N, M\) can be up to \(10^6\), this would require up to \(10^{12}\) comparisons in the worst case, which would not fit within the time limit (TLE).

Solution

By computing the minimum budget \(\min(S)\) in advance, we can determine the result for each product with just one comparison.

Algorithm

1. Compute the minimum value \(\text{min\_s}\) of the budget array \(S\)
2. For each product’s price \(R_i\), check whether \(R_i \leq \text{min\_s}\)
3. Count and output the number of products satisfying the condition

min_s = min(S)
answer = (number of i such that R_i <= min_s)

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(M)\) for computing \(\min(S)\)
  • \(O(N)\) for checking each product
• Space complexity: \(O(N + M)\)
  • Required for storing arrays \(R\) and \(S\)

Implementation Notes

• It is important to compute min(S) only once in advance and store it in a variable. Calling min(S) every iteration inside a loop would result in \(O(N \times M)\) complexity.

• In Python, you can use a generator expression like sum(1 for r in R if r <= min_s) to concisely count the number of elements satisfying the condition.

  Source Code

N, M = map(int, input().split())
R = list(map(int, input().split()))
S = list(map(int, input().split()))
min_s = min(S)
print(sum(1 for r in R if r <= min_s))

---

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