Let's Play Games!
Time limit5sMemory limit2048 MB
Given a table of game ratings, build an ASCII yes/no decision diagram that always leads to a game with the smallest maximum rating difference.
- Level
Hard8 of 10
- Topics
- Geometry, Implementation, Brute force
- Solved
- No attempts yet
Problem
This is the contest introduction.
Everyone loves games! They represent an exciting new era of entertainment, offering not only enjoyment but also valuable opportunities for learning. Games can be instrumental in educating children and developing essential skills. With an endless array of genres available, there is something for everyone. Everyone can find a game that matches their personal interests.
Different people have unique preferences when it comes to gaming. Some are drawn to classical board games, where strategy and skill reign supreme. Others enjoy puzzle games that test problem-solving across various levels of complexity. Some people thrive in competitive programming, where ingenuity and coding skills are put to the ultimate test. Some gamers prefer experiences that are entirely in their control, such as two-player games that rely solely on skill and strategy, with no randomness. Many others enjoy games with an element of chance, which adds unpredictability. For a more casual experience, simple games need no special materials and deliver instant fun. The rise of multiplayer cooperative video games also gives players a setting where teamwork and collaboration are essential for success.
Whether you prefer strategic control, the excitement of chance, or collaborative play, there is a world of gaming experiences to suit every taste.
Most gamers have a clear idea of their tastes. What about those who are lost in the vast sea of choices? How can we guide them toward the game that suits them best? Let us build an interactive diagram that shows the path to each player's ideal game.
Consider a set of games, each rated across several categories. For each game , we write its scores as a vector , where is the game index and is the category index.
When a player sets their own preferences for each category, we write them as a vector . For each game , compute the maximum rating difference across categories, . The optimal game for the player is a game whose is the smallest among all games. Several games may share the minimum .
Finding the best game is difficult. Let us simplify the process. We guide the player through a series of simple yes-or-no questions, such as "Do you prefer this?" or "Do you dislike that?" Each answer leads to the next question until the best option is revealed.
Since preferences vary widely, we must be ready for any answer. Your task is to design a complete decision diagram. Each node is either a terminal node that names a game, or an intermediate node that asks a question about the player's ratings. An intermediate node has two outgoing paths, one for "Yes" and one for "No", and each path leads to a different node.
The diagram must follow these constraints:
- There must be exactly one starting node, which is a node with no incoming link.
- Every intermediate node must have exactly two outgoing links, one for "
Yes" and one for "No". - The two outgoing links from a node must go to different nodes. Also, a link cannot go from a node to itself.
- Questions must have the format "
<category> <sign> <value>", where:- "
<category>" is the name of a rating category. - "
<sign>" is "<", ">", or "=". - "
<value>" is an integer from to .
- "
- Questions that are always meaningless, meaning those that ask whether a rating is less than or greater than , are not allowed.
- The total number of nodes must not exceed .
- It is permitted to have several terminal nodes that name the same game, and several non-terminal nodes that check the same condition.
- The labels "
Yes" and "No" are written as the letters "Y" and "N". Each label must be adjacent to its node and to the outgoing link it labels. Adjacent means grid cells that share a side. The label must occupy the grid cell next to the node in the clockwise direction. Finally, a label cannot be adjacent to more than one node. - The constructed paths must guarantee that, for any set of ratings, the path reaches one of the optimal choices. In other words, no other game may fit better.
Input
The input is a table of ratings. The columns are rating categories, the rows are games, and each cell holds a rating from to . The rating numbers are aligned directly beneath their category names. There is at least one space between consecutive columns.
The number of games and the number of rating categories are each at least and at most . Category names may contain uppercase and lowercase English letters. Game names may contain uppercase and lowercase letters, digits, dashes, commas, and spaces. Names have no leading or trailing spaces. The length of each game name and each rating category name is at least and at most .
Output
Your output must be a diagram in the format described above. The number of rows and the number of columns in each row must not exceed . Each node must follow this format:
*--------*
| <text> |
*--------*
There must be exactly one space before and after the text.
Links between nodes use the following characters:
- "
/": a diagonal connection from top to left, or from bottom to right. - "
\\": a diagonal connection from top to right, or from bottom to left. - "
|": a vertical connection between top and bottom. - "
-": a horizontal connection between left and right. - "
+": a crossing where a vertical and a horizontal line meet. The two lines do not merge. Each continues on its own path.
The output must contain no extra or dangling characters, such as an asterisk surrounded by spaces or a link that leads nowhere. Each diagonal connection must be used by exactly one link.
Hint
The answer for the second example is not available. You can still test your solution on it with the "test on samples" feature in the contest system. If you are unsure whether something is permitted, test it on the samples.