Under construction

Still being built. Things may change

Let's Play Games!

Time limit5sMemory limit2048 MB

Summary
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 ii, we write its scores as a vector gi={gi,j}g_i = \{g_{i,j}\}, where ii is the game index and jj is the category index.

When a player sets their own preferences for each category, we write them as a vector r={rj}r = \{r_j\}. For each game ii, compute the maximum rating difference across categories, di=max⁡j∣gi,j−rj∣d_i = \max_j |g_{i,j} - r_j|. The optimal game for the player is a game ii whose did_i is the smallest among all games. Several games may share the minimum did_i.

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:

  1. There must be exactly one starting node, which is a node with no incoming link.
  2. Every intermediate node must have exactly two outgoing links, one for "Yes" and one for "No".
  3. The two outgoing links from a node must go to different nodes. Also, a link cannot go from a node to itself.
  4. 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 11 to 55.
  5. Questions that are always meaningless, meaning those that ask whether a rating is less than 11 or greater than 55, are not allowed.
  6. The total number of nodes must not exceed 350350.
  7. It is permitted to have several terminal nodes that name the same game, and several non-terminal nodes that check the same condition.
  8. 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.
  9. 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 11 to 55. 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 22 and at most 88. 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 66 and at most 2525.

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 1,0001,000. 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.

Examples2

  1. Example 1

    Input
                          Addicting  Popularity
    Sea battle            3          4
    Tic-Tac-Toe version 2 5          1
    
    Expected output
    *---------------*--\
    | Addicting < 3 |N//         /------------\
    *---------------* |          |Y           |
       Y|             |  *----------------*/\ |
        |             \--| Popularity > 2 |/| |
        |                *----------------*N| |
    *------------*                          | |
    | Sea battle |--------------------------+-/
    *------------*                          |
                     *-----------------------*
                     | Tic-Tac-Toe version 2 |
                     *-----------------------*
    
  2. Example 2

    Input
                              Originality  Clarity  Mathematics  Engagement  Effort
    Surrounding Chess Pieces   1               5      1              2          3
    The Great Lever Challenge    4           2                1        4        5
    Interactive Problems           2             1     1            1          4
    Coin Game                    3              2       1               3      2
    Dice Encryption Algorithm  4             3      1            3               3
    Rock, Paper, Scissors      4               4    1                   4       2
    We Were Here to Code      5               2               1          5   5
    
    Expected output
    <Not Available>