TopCoder problem "BuffetLine" used in TCCC06 Finals (Division I Level Three)

Problem Statement


Before the final round of the TCCC, audience members head to the buffet for lunch. The buffet line contains a number of food items, in a fixed order. Those indulging line up at the buffet, each intending to sample a subset of the items available.

It takes each person exactly 10 seconds to help themselves to a food item. Every 10 seconds, each person moves up as far as they can (without passing by any food they want, of course!). This movement takes no time. The first person in line moves immediately to each item he wants, in order, spending 10 seconds at each item. Depending on which items the rest of the people want, they may be able to move up to each item immediately, but also may have to spend some time waiting for the person they are following.

Each person is always either waiting in line before reaching the first food item, standing in front of exactly one food item, or has passed the last food item and is looking for a place to sit. Two people may not stand in front of the same food item at the same time. Also, people always remain in the order in which they lined up, and they never move backward in line. No one ever passes another person in line -- even after they have taken all the food they want, they still exit the buffet in line. People can only take a food item that they are standing directly in front of. Anyone who cannot reach the next food item they want (because they are waiting for the person in front of them) will advance as far as possible in line, to avoid blocking the people behind them unnecessarily.

Anxious to get back to the TCCC event, the people wish to get the group through the buffet line as quickly as possible. Given the list of food items in the buffet and the items that each person wants, return the optimal order in which the people should line up at the buffet so that everyone can get all the food they desire in the least total amount of time.

The food items available at the buffet will be given as a String food. Each item in food will contain only letters ('a'-'z', 'A'-'Z'), and there will be exactly one space between each pair of adjacent items. Each item in food will be unique. The order of items in food is the order they appear in the buffet line, with the first item in food being the first item available. The items each person wants are given in a String[] cravings. There will be one element in cravings for each person. Each element in cravings will be a list of food items found in food, with exactly one space between each food items. Within each element of cravings, each food item will be unique.

Return a int[] containing the optimal order, where each element is the 0-based index of a person in cravings, and elements are ordered from first to last in line. If there are multiple solutions, return the one that comes first lexicographically. A int[] a1 comes before a int[] a2 lexicographically if, at the first element at which they differ, a1 contains the smaller value.



Parameters:String, String[]
Method signature:int[] order(String food, String[] cravings)
(be sure your method is public)


-food will contain between 1 and 50 characters, inclusive.
-food will be formatted as described in the problem statement and contain between 1 and 8 items, inclusive.
-food will not contain any duplicate items.
-cravings will contain between 1 and 12 elements, inclusive.
-Each element of cravings will contain between 0 and 50 characters, inclusive.
-Each element of cravings will be formatted as described in the problem statement.
-Each word in each element of cravings will be an item from food.
-Each element of cravings will not contain any duplicate items.


"applesauce beans carrots dates eggplant"
{ "beans",
  "dates" }
Returns: {2, 0, 1 }
All three people can get through the line in 10 seconds if the person who wants dates goes first, followed by the person who wants beans, and then the person who wants applesauce. Any other order would require 20 or 30 seconds.
"applesauce beans carrots dates eggplant"
{ "beans",
  "dates" }
Returns: {0, 1, 3, 2 }
In this example there are two people who want beans. Since only one person can take any given food item at once, it will take at least 20 seconds for all 4 people to get through the line. There are several orders that get them through in 20 seconds, and { 0, 1, 3, 2 } is selected according to the tiebreaking rules.
"bread water"
{ "" }
Returns: {0 }
"A B C D E F"
{ "A C E D",
  "A B D E F",
  "B C A D",
  "B C F D E",
  "B D C F" }
Returns: {3, 1, 0, 4, 2 }
"A B C"
{ "A", "A", "A", "A",
  "B", "B", "B", "B",
  "C", "C", "C", "C" }
Returns: {8, 4, 0, 9, 5, 1, 10, 6, 2, 11, 7, 3 }
"A G E F D B H C"
{ "D C A H",
  "H B F G A",
  "B F G D",
  "F C E B A G",
  "D H B C",
  "B A D F G",
  "E B C F D",
  "A D H E B G",
  "A H B G E C",
  "F D A B C",
  "B D A G C",
  "A G E C F" }
Returns: {0, 4, 1, 10, 9, 6, 2, 3, 11, 8, 7, 5 }

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Yarin , Olexiy

Problem categories:

Dynamic Programming