E. Knight Paths

Codeforces

IDCF10264E

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

A knight stands in the top-left corner of an $8 times 8$ chessboard. You can move it *at most* $k$ times. Count such possible paths modulo $2^(32)$. Formally, count paths of cells $(C_1, C_2, \\dots, C_s)$ such that $1 <= s <= k + 1$ and a knight can move from $C_i$ to $C_{i + 1}$ for every $i$. (A chess knight moves to a square that is two squares away horizontally and one square vertically, or one away horizontally and two vertically.) An integer $k$ ($0 <= k <= 10^9$). Print the answer modulo $2^(32) = 4294967296$. In the first sample test, a knight can either stay in the initial cell $(1, 1)$ or move to $(2, 3)$ or $(3, 2)$. That's 3 ways in total. ## Input An integer $k$ ($0 <= k <= 10^9$). ## Output Print the answer modulo $2^(32) = 4294967296$. [samples] ## Note In the first sample test, a knight can either stay in the initial cell $(1, 1)$ or move to $(2, 3)$ or $(3, 2)$. That's 3 ways in total.

**Definitions** Let $ G = (V, E) $ be a directed graph with $ |V| = n $, $ |E| = m $, where all vertices are initially strongly connected. Let $ k \in \mathbb{Z} $, $ 0 \leq k < n $, be the number of edges to retain. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ n \leq m \leq 2 \cdot 10^5 $ 3. $ 0 \leq k < n $ 4. All edges are distinct, no self-loops. 5. Initially, $ G $ is strongly connected. **Objective** Select a subset $ E' \subseteq E $ with $ |E'| = k $ such that the subgraph $ G' = (V, E') $ has the **maximum possible number of strongly connected components**. Output: - The maximum number of strongly connected components in $ G' $. - Any subset of $ k $ edge indices achieving this maximum.

API Response (JSON)

{
  "problem": {
    "name": "E. Knight Paths",
    "description": {
      "content": "A knight stands in the top-left corner of an $8 times 8$ chessboard. You can move it *at most* $k$ times. Count such possible paths modulo $2^(32)$. Formally, count paths of cells $(C_1, C_2, \\\\dots,",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10264E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A knight stands in the top-left corner of an $8 times 8$ chessboard. You can move it *at most* $k$ times. Count such possible paths modulo $2^(32)$.\n\nFormally, count paths of cells $(C_1, C_2, \\\\dots,...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be a directed graph with $ |V| = n $, $ |E| = m $, where all vertices are initially strongly connected.  \nLet $ k \\in \\mathbb{Z} $, $ 0 \\leq k < n $, be the number...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments