C. Encrypted Password

Codeforces

IDCF10015C

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Encrypting passwords is one of the most important problems nowadays, and you trust only the encryption algorithms which you invented, and you have just made a new encryption algorithm. Given a password which consists of only lower case English letters, your algorithm encrypts this password using the following 3 steps (in this given order): And the encrypted password is the output of step three. You have just finished implementing the above algorithm and applied it on many passwords. Now you want to make sure that there are no bugs in your implementation, so you decided to write another program which validates the output of the encryption program. Given the encrypted password and the original password, your job is to check whether the encrypted password may be the result of applying your algorithm on the original password or not. The input consists of two lines. The first line contains the encrypted password. The second line contains the original password. Both the encrypted password and the original password are at least 1 and at most 100,000 lower case English letters (from 'a' to 'z'), and the length of the original password is less than or equal the length of the encrypted password. Print on a single line one word, "YES" (without the quotes) if applying the algorithm on the original password may generate the encrypted password, otherwise print "NO" (without the quotes). ## Input The input consists of two lines. The first line contains the encrypted password. The second line contains the original password. Both the encrypted password and the original password are at least 1 and at most 100,000 lower case English letters (from 'a' to 'z'), and the length of the original password is less than or equal the length of the encrypted password. ## Output Print on a single line one word, "YES" (without the quotes) if applying the algorithm on the original password may generate the encrypted password, otherwise print "NO" (without the quotes). [samples]

**Definitions** Let $ P = p_1 p_2 \dots p_n $ be the original password, where $ p_i \in \{a, b, \dots, z\} $ and $ n = |P| $. Let $ E = e_1 e_2 \dots e_m $ be the encrypted password, where $ e_j \in \{a, b, \dots, z\} $ and $ m = |E| $, with $ n \leq m $. **Constraints** 1. $ 1 \leq n \leq m \leq 100000 $ 2. All characters in $ P $ and $ E $ are lowercase English letters. **Objective** Determine whether there exists a sequence of three deterministic operations (as described in the unprovided algorithm steps) that transforms $ P $ into $ E $. **Note**: Since the three encryption steps are not specified, the problem is formally underspecified. However, the task is to validate whether $ E $ *could* result from applying the (unknown) algorithm to $ P $. Thus, the formal objective is: $$ \text{Is } E \in \mathcal{F}(P) \text{?} $$ where $ \mathcal{F} $ is the unknown function defined by the three-step encryption algorithm. **Output** $$ \begin{cases} \text{YES} & \text{if } E \in \mathcal{F}(P) \\ \text{NO} & \text{otherwise} \end{cases} $$

API Response (JSON)

{
  "problem": {
    "name": "C. Encrypted Password",
    "description": {
      "content": "Encrypting passwords is one of the most important problems nowadays, and you trust only the encryption algorithms which you invented, and you have just made a new encryption algorithm. Given a passwo",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10015C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Encrypting passwords is one of the most important problems nowadays, and you trust only the encryption algorithms which you invented, and you have just made a new encryption algorithm.\n\nGiven a passwo...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ P = p_1 p_2 \\dots p_n $ be the original password, where $ p_i \\in \\{a, b, \\dots, z\\} $ and $ n = |P| $.  \nLet $ E = e_1 e_2 \\dots e_m $ be the encrypted password, where $ e_j \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments