GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Wednesday 14 December 2022

[Solution] Akash and Dinner CodeChef Solution 2022



Problem

Akash got his money from CodeChef today, so he decided to have dinner outside.
He went to a restaurant having N items on the menu. The i^{th} item on the menu belongs to the category A_i and requires B_i time to be cooked.

Akash wants to have a complete meal. Thus, his meal should have at least K distinct categories of food.
The total time required to get all the food Akash orders, is the sum of the cooking time of all the items in the order.

Help Akash find the minimum time required to have a complete meal or tell if it is not possible to do so.

Input Format

  • First line will contain T, the number of test cases. Then the test cases follow.
  • Each test case contains three lines:
    • The first line of each test case contains two space-separated integers N and K, denoting the number of dishes on the menu and the number of distinct categories in a complete meal.
    • The second line contains N space-separated integers where the i^{th} integer is A_i, denoting the category of the i^{th} dish in the menu.
    • The third line contains N space-separated integers where the i^{th} integer is B_i, denoting the time required to cook the i^{th} dish in the menu.

Output Format

For each test case, output in a single line, the minimum time required to have a complete meal.


Solution Click Below:-  👉CLICK HERE👈
👇👇👇👇👇


If it is impossible to have a complete meal, print -1 instead.

Explanation:

Test case 1: Akash can choose dish with index 2 having category 2. The total time required to get the complete meal is 1.

Test case 2: Akash can choose dishes with index 3, 5, and 7 from the menu.

  • Dish 3: The dish has category 2 and requires time 0.
  • Dish 5: The dish has category 4 and requires time 2.
  • Dish 7: The dish has category 3 and requires time 1.

Thus, there are 3 distinct categories and the total time to get the meal is 0+2+1 = 3. It can be shown that this is the minimum time to get the complete meal.

Test case 3: Akash can choose the only available dish having category 5. The total time required to get the complete meal is 1.

Test case 4: The total number of distinct categories available is 2, which is less than K. Thus, it is impossible to have a complete meal.

No comments:

Post a Comment