Overview

This problem asks you to find the minimum total price by selecting one vegetable and one meat product from the available ingredients for each day.

Analysis

Key Insight

In this problem, you need to select “one type of vegetable and one type of meat.” Since we want to minimize the total price, we can simply select the cheapest item from each category.

Why a Simple Approach Works

At first glance, it might seem necessary to try all combinations of vegetables and meat products. However, vegetables are independent of each other, and meat products are independent of each other. In other words:

• The choice of vegetable does not affect the choice of meat
• The choice of meat does not affect the choice of vegetable

Therefore, we can find the minimum price among vegetables and the minimum price among meat products separately, then add them together to get the answer.

Concrete Example

For example, suppose the following ingredients are available on a certain day: - Vegetable A (100 yen), Vegetable B (150 yen) - Meat C (200 yen), Meat D (180 yen)

Considering all combinations: - A+C = 300 yen, A+D = 280 yen - B+C = 350 yen, B+D = 330 yen

The minimum is 280 yen, which is the combination of the cheapest vegetable A (100 yen) and the cheapest meat D (180 yen).

Algorithm

1. Read the price \(P_i\) and type \(T_i\) of each ingredient and store them in arrays
2. For each day \(j\), do the following:
   • Read the list of ingredients available for purchase that day
   • Check each available ingredient one by one, and find the minimum price among vegetables (\(T=0\)) and the minimum price among meat products (\(T=1\)) respectively
   • If there is at least one ingredient in each category, output the sum of the two minimum prices
   • If either category has no ingredients, output \(-1\)

Complexity

• Time Complexity: \(O(N + \sum_{j=1}^{M} K_j)\)

  • Reading ingredient information takes \(O(N)\)
  • For each day’s processing, we look at each available ingredient once, so the total across all days is \(O(\sum K_j)\)
  • From the constraints, \(\sum K_j \leq 2 \times 10^5\), which is sufficiently fast

• Space Complexity: \(O(N + M)\)

  • \(O(N)\) for arrays storing ingredient prices and types
  • \(O(M)\) for an array storing results

Implementation Tips

1. Infinity as Initial Value: When finding the minimum, setting the initial value to float('inf') makes it easy to check whether an ingredient exists in a category.

2. Handling 1-indexed: Since ingredient numbers start from 1, making the array size \(N+1\) and using the indices directly makes implementation easier.

3. Output Optimization: Instead of calling print for each day’s result, accumulating results in a list and outputting them all at once at the end reduces I/O overhead.

4. Fast Input: Using sys.stdin.readline allows for fast reading even when there is a large amount of input.

   Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    
    prices = [0] * (N + 1)
    types = [0] * (N + 1)
    
    for i in range(1, N + 1):
        P, T = map(int, input().split())
        prices[i] = P
        types[i] = T
    
    results = []
    
    for _ in range(M):
        line = list(map(int, input().split()))
        K = line[0]
        items = line[1:K+1]
        
        # Find minimum price for meat (T=1) and vegetable (T=0)
        min_meat = float('inf')
        min_veg = float('inf')
        
        for item in items:
            if types[item] == 1:  # meat
                if prices[item] < min_meat:
                    min_meat = prices[item]
            else:  # vegetable
                if prices[item] < min_veg:
                    min_veg = prices[item]
        
        if min_meat == float('inf') or min_veg == float('inf'):
            results.append(-1)
        else:
            results.append(min_meat + min_veg)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.