M. Forgotten Spell

Codeforces

IDCF10175M

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Three mages are trying to remember a spell. Each of them believes the spell is some string of length n and it is known that each of the mages is mistaken in at most one letter. It is required to restore the forgotten spell. Three strings of the same length n (1 ≤ n ≤ 200000) are given in the input. They consist of lowercase Latin letters. If such a situation is not possible, output «_Impossible_». If there are several spells satisfying the conditions, output «_Ambiguous_». Finally, if the forgotten spell is the only one possible, output it. ## Input Three strings of the same length n (1 ≤ n ≤ 200000) are given in the input. They consist of lowercase Latin letters. ## Output If such a situation is not possible, output «_Impossible_».If there are several spells satisfying the conditions, output «_Ambiguous_».Finally, if the forgotten spell is the only one possible, output it. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ with $ 1 \leq n \leq 200000 $. Let $ s_1, s_2, s_3 \in \Sigma^n $ be three input strings over the alphabet $ \Sigma = \{a, b, \dots, z\} $. Let $ x \in \Sigma^n $ be the target spell. **Constraints** For each $ i \in \{1,2,3\} $, the Hamming distance satisfies $ d_H(s_i, x) \leq 1 $. **Objective** Determine the set $ X = \{ x \in \Sigma^n \mid \forall i \in \{1,2,3\},\ d_H(s_i, x) \leq 1 \} $: - If $ |X| = 0 $, output "Impossible". - If $ |X| > 1 $, output "Ambiguous". - If $ |X| = 1 $, output the unique $ x \in X $.

API Response (JSON)

{
  "problem": {
    "name": "M. Forgotten Spell",
    "description": {
      "content": "Three mages are trying to remember a spell. Each of them believes the spell is some string of length n and it is known that each of the mages is mistaken in at most one letter. It is required to resto",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10175M"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Three mages are trying to remember a spell. Each of them believes the spell is some string of length n and it is known that each of the mages is mistaken in at most one letter. It is required to resto...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 200000 $.  \nLet $ s_1, s_2, s_3 \\in \\Sigma^n $ be three input strings over the alphabet $ \\Sigma = \\{a, b, \\dots, z\\} $.  \nLet $ x \\in \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments