Introduction
Everything started as an application for a research and innovation role at ICCS.
Days later, an email arrives – you’ve landed an interview. Or so you think. As you
walk into the elegant, marble-floored office, you quickly realize something’s wrong.
The interview isn’t for the research position; You had applied to for Head Chef at
“ICCS: Imperial Cuisine & Curated Symphonies” one of the most prestigious
Michelin-starred restaurants in the city. Before you can explain the mix-up, you’re
swept up in the anxiety of it all – the previous chef has left, and they desperately
need someone to craft an extraordinary degustation menu for a high-profile
event happening in just a few days.
You are about to turn them down and clarify the misunderstanding, but the
restaurant owner, visibly stressed, looks at you with hope in their eyes. The kitchen
is in disarray, the staff is lost, and the event is looming like a storm on the horizon.
You understand that no one else can step in and you felt compelled to help. After
all, problem-solving is second nature to you, and you were no stranger to
handling pressure.
But you weren’t going to play it safe… If you were going to design an extraordinary
degustation menu, you will do it your way!
Task
Given a list of recipes and the tags / ingredients associated with each recipe,
arrange the recipes into a degustation menu list that is as interesting as possible
(the scoring section below explains what we mean by “interesting”).
Problem description
Recipes
A recipe is described by a set of tags that are the ingredients of the recipe.
For example, The cheesy eggplant recipe could be tagged with the following tags:
[eggplant, tomato, parmesan cheese, basil].
Each recipe belongs to one of the categories regarding its nutritional value
- a full-dish
- a half-dish
- a quarter-dish
Τhe recipe on the left is full, while the recipe on the right (top) is a half-dish recipe and
the right (bottom) is a quarter-dish recipe
A Degustation Menu
A degustation menu is an ordered list of dishes. Each dish contains either:
● a full recipe, or
● two half-recipes, or
● four quarters-recipes or
● one half and two-quarters recipes
If the dish contains a full recipe, the tags
of the dish are the same as the tags of
the single recipe.
For example, a dish containing a full
recipe with tags [chicken, lentils, rice,
cherry tomatoes, oregano], has tags
[chicken, lentils, rice, cherry tomatoes,
oregano].
If the dish contains more recipes, the tags
of the dish are all the tags present in any
of the recipes.
For example, a dish containing a half
recipe with 3 tags [potatoes, garlic, basil]
a quarter recipe with tags 4 [eggplant,
tomato, parmesan, basil] and a quarter
recipe with 1 tag [dough], the total tags of
the dish are 7, [potatoes, garlic, basil,
eggplant, tomato, parmesan, dough].
Each recipe can be used either once or
not at all.
Input data set
File format
Each input data set is provided in a plain text that contains exclusively ASCII
characters with lines terminated with a single '\n' character (UNIX-style line
endings).
5
The first line of the data set contains a single integer 𝑁, (1 ≤ 𝑁 ≤ 10 ) — the
number of the available recipes in the Book.
This is followed by 𝑁 lines, where line 𝑖 contains a description of the recipe with ID
𝑖, (0 ≤ 𝑖 < 𝑁). The description of the recipe 𝑖 contains the following data,
separated by a single space:
● A single character ‘F’ if the recipe is Full, or ‘H’ if it is Half, or ‘Q’ if it is
Quarter.
● An integer 𝑀𝑖 (1 ≤ 𝑀𝑖 ≤ 100) — the number of tags for that recipe
● 𝑀𝑖 text strings — the tags for recipe i. Each tag consists only of lowercase
ASCII letters and digits, between 1 and 10 characters in total.
Example
Input file Description
5 the Book has 5 recipes
F 5 chicken lentils rice tomatoes oregano recipe 0 is Full and has tags [chicken, lentils, rice, tomatoes, oregano]
H 3 potatoes garlic basil recipe 1 is Half and has tags [potatoes, garlic, basil]
F 4 chicken lentils broccoli potatoes recipe 2 is Full and has tags [chicken, lentils, broccoli, potatoes]
Q 4 eggplant tomato parmesan basil recipe 3 is Quarter and has tags [eggplant, tomato, parmesan, basil]
Q 1 dough recipe 4 is Quarter and has tags [dough]
Submissions
File format
The output file must start with a single integer 𝐷 (1 ≤ 𝐷 ≤ 𝑁) — the number of
dishes in the Degustation Menu. This must be followed by 𝐷 lines describing the
individual dishes. Each line should contain either:
● A single integer – ID of the single full recipe in the dish.
● Two integers separated by a single space – IDs of the two half-recipes in the
dish in any order.
● Three integers separated by a single space – IDs of the one half-recipe and
two quarters in the dish in any order.
● Four integers separated by a single space – IDs of the four quarter-recipes
in the dish in any order.
Each recipe can be used only one time or not at all.
Example
Submission file Description
3 The degustation menu has 3 dishes
0 First dish contains recipe 0
2 Second dish contains recipe 2
134 Third dish contains recipes 1, 3 and 4
Scoring
Your degustation menu is scored based on the WOW effect! The WOW effect is
based on the transitions between the pairs of subsequent dishes. We want the
transitions to have some ingredients in common to preserve smoothness (the two
dishes should not be totally different), but we also want them to be different
enough to impress the clients. The scoring is measured between the dishes and
not between the recipes.
For two subsequent dishes 𝐷𝑖 and 𝐷𝑖+1 the interest factor is the minimum (the
smallest number of the three) of:
- the number of common tags between 𝐷𝑖 and 𝐷𝑖+1
- the number of tags in 𝐷𝑖 but not in 𝐷𝑖+1
- the number of tags in 𝐷𝑖+1 but not in 𝐷𝑖.
For example, for the transition from 𝐷1 to 𝐷2, we know that the tags are [chicken,
lentils, broccoli, potatoes] for 𝐷1, and [potatoes, garlic, basil, eggplant, tomato,
parmesan, dough] for 𝐷2
● The number of common tags is 1 → [potatoes]
● The number of tags in 𝐷1, but not is 𝐷2 is 3 → [chicken, lentils, broccoli]
● The number of tags in 𝐷2, but not in 𝐷1, is 6 → [garlic, basil, eggplant,
tomato, parmesan, dough]
The WOW effect is the minimum of these numbers, so it is 1.
For a degustation menu of 𝐷 dishes, the score will be equal to the sum of WOW
effects of each transition of two sequential dishes. A degustation menu with only
one dish has a score of zero.
For example, with the input and the submission files above, the degustation menu
has 3 dishes, hence it has 2 transitions:
1st transition, from dish 𝐷0 (recipe 0) to dish 𝐷1 (recipe 2)
- 2 common tags between recipes 0 and 2 → [chicken, lentils]
- 3 tags in recipe 0 and not in recipe 2 → [rice, tomatoes, oregano]
- 2 tag in recipe 2 and not in recipe 1 → [broccoli potatoes]
WOW effect = 𝑚𝑖𝑛(2, 3, 2) = 2
The second transition, from dish 𝐷1 (recipe 2) to dish 𝐷2 (recipes 1, 3, 4) has WOW
effect = 1 (see example above).
Therefore, the score of this submission is 2 + 1 = 3.