Problem E
Colourful New World
You may be familiar with the philosophical thought experiment referred to as Mary’s Room. If not, it goes as follows:
Mary is a scientist who has lived in a black and white room her entire life. She has also spent her whole life studying biological colour perception and the physical properties of colour: retinas, cones, wavelengths, and so on. She knows all there is to know, quantifiably, about colour. But if Mary finally leaves the room and experiences seeing colour for the first time, would she learn anything new about colour?
This is a well-known argument against a philosophical position called physicalism, but you don’t have to worry about arguing with philosophers while working on this problem. Instead, you have been contacted by Mary, who has just received word that she will be permitted to leave her room for a single day this year (the experimenters behind Mary’s Room were getting a bit worried about the newly formed Thought Experiment Ethics Review Board).
Because of hypothetical travel restrictions, Mary is limited to visiting places in her local region. The experimenters have kindly obtained and provided you with a list of all the potential locations she can travel to and the colours associated with each location. Since she has just one day to explore, she only has time to visit at most $V$ of the locations.
The experimenters have also decided to give Mary a special experimental camera designed to take black and white photographs with a single accent colour. (They have begun planning a missing-shade-of-blue experiment for when Mary returns to her room again.) Note that the camera can always be recalibrated between photographs to capture a different accent colour. However, since the camera was developed by die-hard film photographers, the number of photographs one can take with it is limited by the sizes of rolls of film. Mary must use a different roll of film at each location, which means that she can take at most $R$ photos (and therefore can capture at most $R$ distinct colours) at each location.
Mary would like to capture as many colours as possible, but she isn’t sure how best to do this, so she has requested that you provide her with an itinerary which maximizes the total number of distinct colours she can capture in one day.
Input
The first line of input contains three space-separated integers, $L$, $V$, and $R$, where $L$ is the total number of locations in Mary’s local region $(1 \leq L \leq 10)$, $V$ is the number of locations Mary has time to visit $(1 \leq V \leq L)$, and $R$ is the maximum number of photos Mary can take at each location $(1 \leq R \leq 36)$.
$L$ lines follow. The $i^{\textrm{th}}$ of these $L$ lines contains a string denoting the name of the $i^{\textrm{th}}$ location, followed by an integer $C_ i$ ($1 \leq C_ i \leq 200$) indicating the number of colours present at this location, followed by $C_ i$ space-separated strings, each of which is the name of a colour Mary could capture at the $i^{\textrm{th}}$ location. The names of the $C_ i$ colours are guaranteed to be pairwise distinct for each location, and the name of a colour is never the same as the name of any location.
The $L$ locations have distinct names, every colour has exactly one name, and distinct colours have distinct names. There are no more than $200$ distinct colours over all locations. Every string contains between $1$ and $30$ characters, each of which is either a letter (a–z, A–Z) or the underscore character (_). Note that location and colour names are case-sensitive.
Output
The first line of output should contain two space-separated integers: $M$, the maximum number of colours that Mary can photograph in a day, and $N$, the number of locations visited in an itinerary that enables Mary to capture $M$ colours. If there is more than one set of locations that meets these requirements, any one will do.
Next print $N$ lines containing the locations Mary should visit, along with the colours she should photograph at each location. Each of these $N$ lines should consist of the name of a location, followed by an integer $k \geq 1$, the number of colours Mary should photograph at this location, followed by the names of the $k$ colours. Adjacent tokens should be separated by a single space, and there should be no leading or trailing spaces on any line.
Each of the $N$ locations in the itinerary, and each of the $M$ colours Mary should photograph, must appear exactly once in the output. The $N$ lines can be in any order, and the colours in any line can be in any order.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 2 forest 3 green brown blue library 5 red brown amber navy green meadow 2 green blue |
5 3 forest 2 green brown library 2 red amber meadow 1 blue |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 2 3 lake 2 blue green desert 2 dun orange somewhere_over_the_rainbow 7 red orange yellow green blue indigo violet |
5 2 lake 2 blue green somewhere_over_the_rainbow 3 red orange yellow |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 3 5 Lothlorien 3 green silver gold Anarres 4 grey black tan beige Sweetwater 5 tan beige brown blue grey The_Library_of_Babel 6 white black grey beige brown crimson Omelas 10 green red blue yellow mauve grey brown gold silver white |
13 3 Lothlorien 3 green silver gold The_Library_of_Babel 5 white black beige brown crimson Omelas 5 red blue yellow mauve grey |
