E. Bisection

Codeforces

IDCF10097E

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Pavel has developed the best game in the world — «Bisection». In this game the square grid of size n × n is given to a player. Some of the cells on the grid are selected and form a figure. A player should paint every cell of this figure in one of two colors so that the resulting figures of both colors would be equal. The figures are equal if one of them could be transformed into the other by translations, reflections relative to horizontal and vertical axes and turns by right angles. Pavel has created an extra level for this game, but he can't understand if it has any solution. You have to find it out. The first line contains a single integer n (1 ≤ n ≤ 50) — the size of the grid. Each of the next n lines contains n characters. The character is «_._» if this cell doesn't belong to the figure, and «_#_» if it does. It's guaranteed that the input contains positive even number of «_#_» characters. If there is no solution, output «_NO_» (without quotes). Otherwise in the first line output «_YES_» (without quotes), and then output n lines of n characters describing the coloring of the figure. Characters «_._» from the input shouldn't be touched, and characters «_#_» should be replaced with «_A_» or «_B_», depending on the color that should be used to paint this cell. If there are many possible solutions, output any of them. ## Input The first line contains a single integer n (1 ≤ n ≤ 50) — the size of the grid.Each of the next n lines contains n characters. The character is «_._» if this cell doesn't belong to the figure, and «_#_» if it does.It's guaranteed that the input contains positive even number of «_#_» characters. ## Output If there is no solution, output «_NO_» (without quotes).Otherwise in the first line output «_YES_» (without quotes), and then output n lines of n characters describing the coloring of the figure. Characters «_._» from the input shouldn't be touched, and characters «_#_» should be replaced with «_A_» or «_B_», depending on the color that should be used to paint this cell.If there are many possible solutions, output any of them. [samples]

**Definitions** Let $ n \in \mathbb{Z} $, $ 1 \leq n \leq 50 $, be the grid size. Let $ G \subseteq \{1, \dots, n\} \times \{1, \dots, n\} $ be the set of cells belonging to the figure, i.e., $ G = \{ (i,j) \mid \text{grid}[i][j] = \# \} $. Let $ |G| = 2m $ for some $ m \in \mathbb{Z}^+ $ (given even). A *coloring* is a function $ c: G \to \{A, B\} $ such that the two colored subsets $ G_A = c^{-1}(A) $, $ G_B = c^{-1}(B) $ satisfy $ |G_A| = |G_B| = m $, and $ G_A $ is congruent to $ G_B $ under the group of isometries generated by translations, reflections over horizontal/vertical axes, and rotations by $ 90^\circ $. **Constraints** 1. $ 1 \leq n \leq 50 $ 2. $ |G| $ is even and positive 3. The grid is given as an $ n \times n $ matrix with entries in $ \{ \text{.}, \# \} $ **Objective** Determine whether there exists a coloring $ c: G \to \{A, B\} $ such that $ G_A \cong G_B $ under the specified isometries. - If yes: output "YES" and an $ n \times n $ grid with $ \# \to A $ or $ B $, and $ \text{.} $ unchanged. - If no: output "NO".

API Response (JSON)

{
  "problem": {
    "name": "E. Bisection",
    "description": {
      "content": "Pavel has developed the best game in the world — «Bisection». In this game the square grid of size n × n is given to a player. Some of the cells on the grid are selected and form a figure. A player sh",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10097E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Pavel has developed the best game in the world — «Bisection». In this game the square grid of size n × n is given to a player. Some of the cells on the grid are selected and form a figure. A player sh...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 50 $, be the grid size.  \nLet $ G \\subseteq \\{1, \\dots, n\\} \\times \\{1, \\dots, n\\} $ be the set of cells belonging to the figure, i.e., $ G ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments