Connection Status:
Competition Arena > OrderFood

OrderFood

SRM 219 · 2004-11-20 · by erinn

SRM 219 · 2004-11-20 · by erinn · Brute Force, Search, Sorting
Class Name: OrderFood
Return Type: int
Method Name: selectEntrees
Arg Types: (vector<int>, vector<string>)
Problem Statement

Problem Statement

You and several friends go out to dinner for Chinese food. The waiter advises that you should share entrees, since each is large enough to feed many people. Each of you has certain favorite entrees that you like best.

To make sure that everyone enjoys the meal, you decide each person should have two of his favorite entrees to choose from. However, to ensure that nobody gets too greedy, you also decide that nobody should have more than two of his favorite entrees.

You are given a int[] entrees, indicating the cost of each entree on the menu. You are also given a String[] favorites, each element of which is a space delimited list of integers. Each integer is a 0-based index into entrees, where the integers in element i of favorites correspond to the favorite entrees of person i. You are to return an int, indicating the least expensive way to order entrees such that each person has exactly two of his favorite entrees to choose from. If it is not possible to order entrees in such a way that everyone gets exactly two of his favorite items, the method should return -1.

Notes

  • You may assume that each entree will be enough to feed an arbitrary number of people.

Constraints

  • entrees will contain between 1 and 30 elements, inclusive.
  • Each element of entrees will be between 1 and 1000000, inclusive.
  • favorites will contain between 1 and 15 elements, inclusive.
  • Each element of favorites will be a list of integers, each separated by a single space, with no additional leading or trailing spaces.
  • Each element of favorites will contain between 1 and 50 characters, inclusive.
  • Each number represented in each element of favorites will be between 0 and n - 1, inclusive, where n is the number of elements in entrees (leading zeros are permitted).
Examples
0)
{100, 150, 300, 425, 200}
{"0 1 3", "0 2 3 4", "0 3 4"}
Returns: 450

Clearly, we want to order item 0, since it's cheapest, and everyone likes it. Now, we could order item 3, also one that everybody likes, but it costs 425. It would be cheaper to buy items 1 and 4 (for 350 total) to give everyone a second favorite entree.

1)
{100, 200, 300, 400}
{"0 1", "1 2", "0 1 2"}
Returns: -1

Since the first two people are picky, and only have two favorites, we have to buy items 0, 1, and 2. But this gives the last person three favorites, which isn't allowed, so there's no solution.

2)
{10, 20, 40, 80, 160, 320, 640}
{"0 2 5", "0 2 6", "0 3 5", "1 3 6", "1 4", "1 4"}
Returns: 310

Clearly, we're must purchase items 1 and 4. We can satisfy everyone else by then selecting 0, 2, 3 or 0, 5, 6. We choose the cheaper option.

3)
{100, 200, 300, 400}
{"1 1"}
Returns: -1

Even though we have listed it twice, this person only has a single favorite, so there's no way to pick two favorites.

4)
{1000, 90, 80, 70, 60, 50, 40}
{"0 1 2", "0 00 000 3 4", "0 5 6", "0 1 4", "0 2 5", "0 3 6"}
Returns: 390

Even though entree 0 is listed multiple times in element 1 of favorites, it only counts once. Note also that leading zeros are permitted.

Submissions are judged against all 64 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class OrderFood with a public method int selectEntrees(vector<int> entrees, vector<string> favorites) · 64 test cases · 2 s / 256 MB per case

Submitting as anonymous