K. Kleptography

Codeforces

IDCF10248K

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

John likes simple ciphers. He had been using the "Caesar" cipher to encrypt his diary until recently, when he learned a hard lesson about its strength by catching his sister Mary browsing through the diary without any problems. Rapidly searching for an alternative, John found a solution: the famous "Autokey" cipher. He uses a version that takes the $26$ lower-case letters '_a_'–'_z_' and internally translates them in alphabetical order to the numbers $0$ to $25$. The encryption key $k$ begins with a secret prefix of $n$ letters. Each of the remaining letters of the key is copied from the letters of the plaintext $a$, so that $k_{n + i} = a_i$ for $i >= 1$. Encryption of the plaintext $a$ to the ciphertext $b$ follows the formula $b_i = a_i + k_i bmod 26$. Mary is not easily discouraged. She was able to get a peek at the last $n$ letters John typed into his diary on the family computer before he noticed her, quickly encrypted the text document with a click, and left. This could be her chance. The input consists of: Output the plaintext of John's diary. ## Input The input consists of: One line with two integers $n$ and $m$ ($1 <= n <= 30$, $n + 1 <= m <= 100$), where $n$ is the length of the keyword as well as the number of letters Mary saw, and $m$ is the length of the text. One line with $n$ lower-case letters, the last $n$ letters of the plaintext. One line with $m$ lower-case letters, the whole ciphertext. ## Output Output the plaintext of John's diary. [samples]

**Definitions** Let $ G = (V, E) $ be an undirected multigraph with: - $ V = \{0, 1, \dots, n-1\} $, the set of nodes, - $ E $, the multiset of fiber links (edges), with $ |E| = m $. Let $ d_G(v) $ denote the degree of node $ v $ in $ G $. Let $ T = (V, E') $ be a spanning tree of $ G $, i.e., a connected acyclic subgraph with $ |E'| = n - 1 $. Let $ d_T(v) $ denote the degree of node $ v $ in $ T $. **Constraints** 1. $ 2 \le n \le 10^4 $ 2. $ 1 \le m \le 10^5 $ 3. $ G $ is connected (possibly with multiple edges). 4. $ T $ must be a spanning tree of $ G $. **Objective** Minimize the number of nodes $ v \in V $ for which $ d_T(v) \ne d_G(v) $. Output: - The minimal number of such mismatched nodes. - Any spanning tree $ T $ achieving this minimum, represented as a list of $ n-1 $ edges.

API Response (JSON)

{
  "problem": {
    "name": "K. Kleptography",
    "description": {
      "content": "John likes simple ciphers. He had been using the \"Caesar\" cipher to encrypt his diary until recently, when he learned a hard lesson about its strength by catching his sister Mary browsing through the ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10248K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "John likes simple ciphers. He had been using the \"Caesar\" cipher to encrypt his diary until recently, when he learned a hard lesson about its strength by catching his sister Mary browsing through the ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be an undirected multigraph with:  \n- $ V = \\{0, 1, \\dots, n-1\\} $, the set of nodes,  \n- $ E $, the multiset of fiber links (edges), with $ |E| = m $.  \n\nLet $ d_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments