F. Fairy, the treacherous mailman

Codeforces

IDCF10202F

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Fairy is a very excentric mailman. Every now and then, he likes to change some correspondences that he is responsible for, swapping than to different addresses, as he enjoys the consequent turmoil. One day, Fairy was in his most inspired self and decided to swap all correspondences from their original addresses. No address should receive its intended correspondence. It will be Fairy's ultimate masterpiece. Although he is keen to chaos, Fairy is also a very curious person, and he asked himself about how many ways he could swap the correspondences so none of the addresses receive the correct message. As he's very lazy, he decided to ask your help to fulfill his objectives. You'll receive an integer number $N$, that stands for the correspondences amount, to which you should generate another integer $S$ that stands for the amount of ways he can swap the correspondences. Help Fairy in his mischievous plan, or he might change your correspondence as well. A unique integer $N$, ($1 <= N <= 20$) standing for the amount of correspondences. A unique integer $S$, representing the amount of ways Fairy can swap the correspondences. As the possibilities amount can be very big, the answer should be given as $S$ $m o d$ $10^9 + 7$. ## Input A unique integer $N$, ($1 <= N <= 20$) standing for the amount of correspondences. ## Output A unique integer $S$, representing the amount of ways Fairy can swap the correspondences. As the possibilities amount can be very big, the answer should be given as $S$ $m o d$ $10^9 + 7$. [samples]

**Definitions** Let $ r, c \in \mathbb{Z} $ denote the number of rows and columns of the honeycomb grid. Let $ G = (V, E) $ be a graph representing the honeycomb, where: - Each vertex $ v \in V $ corresponds to a cell at position $ (i, j) $, with $ i \in \{1, \dots, r\} $, $ j \in \{1, \dots, c\} $. - An edge $ (u, v) \in E $ exists if cells $ u $ and $ v $ are adjacent (share a non-removed wall). Let $ S = (i_s, j_s) $ be the unique starting cell marked by "S". Let $ T = (i_t, j_t) $ be the unique target cell marked by "T". **Constraints** 1. $ 2 \le r, c \le 10^3 $ 2. The honeycomb is closed (outermost walls exist). 3. Exactly one "S" and one "T" appear in the grid. 4. The total sum of $ r \cdot c $ across all test cases $ \le 2 \times 10^6 $. 5. Adjacency is determined by the presence of edges in the input: - Horizontal adjacency: via "___" in odd rows. - Diagonal adjacencies: via "/" or "\" in even rows. - Offset: cells in even columns are shifted down relative to odd columns. **Objective** Compute the minimum number of cells visited on a path from $ S $ to $ T $, including both endpoints. If no path exists, return $-1$. This is equivalent to finding the shortest path in $ G $ from $ S $ to $ T $ in terms of number of vertices traversed. $$ \min \{ |P| \mid P \text{ is a path from } S \text{ to } T \text{ in } G \} $$ where $ |P| $ is the number of cells in path $ P $.

API Response (JSON)

{
  "problem": {
    "name": "F. Fairy, the treacherous mailman",
    "description": {
      "content": " Fairy is a very excentric mailman. Every now and then, he likes to change some correspondences that he is responsible for, swapping than to different addresses, as he enjoys the consequent turmoil. O",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10202F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Fairy is a very excentric mailman. Every now and then, he likes to change some correspondences that he is responsible for, swapping than to different addresses, as he enjoys the consequent turmoil. On...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ r, c \\in \\mathbb{Z} $ denote the number of rows and columns of the honeycomb grid.  \nLet $ G = (V, E) $ be a graph representing the honeycomb, where:  \n- Each vertex $ v \\in V ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments