D. Guessing Messages

Codeforces

IDCF10230D

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Samuelo is a very good friend of Roppa. Whenever they feel bored, they like to exchange secret messages. To do that, they craft some text in such a way so that the hidden message is a subsequence of it. To make things harder, they never use whitespaces. An example of message exchanged in the past is (hidden message is red and underlined): It can be very hard to uncover a message hidden like that, but it's usually not a problem for them since their minds are pretty much in sync. Samuelo just wrote one of those messages. Roppa decided to take a step further this time and test their friendship by trying to guess the hidden message before even receiving it. Given the message that Samuelo wrote and Roppa's guess, help Roppa on figuring out if his guess is in fact hidden in Samuelo's message. The first line the input contains a string $s$ ($1 <= lvert s rvert <= 10^6$), indicating the message that Samuelo wrote. The second line of the input contains a string $t$ ($1 <= lvert t rvert <= 10^6$), indicating Roppa's guess. Both strings are composed only of lowercase English letters. Output YES if Roppa's guess is hidden in Samuelo's message. Otherwise, output NO. ## Input The first line the input contains a string $s$ ($1 <= lvert s rvert <= 10^6$), indicating the message that Samuelo wrote. The second line of the input contains a string $t$ ($1 <= lvert t rvert <= 10^6$), indicating Roppa's guess.Both strings are composed only of lowercase English letters. ## Output Output YES if Roppa's guess is hidden in Samuelo's message. Otherwise, output NO. [samples]

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ denote the number of features desired by Prof. Xie and Prof. Zhang, respectively. Let $ W = (w_1, w_2, \dots, w_{n+m}) \in \mathbb{Z}^{n+m} $ be the weight vector, where $ w_i > 0 $ is the weight of feature $ i $. Let $ F_X = \{1, 2, \dots, n\} $ be the set of features desired by Prof. Xie. Let $ F_Z = \{n+1, n+2, \dots, n+m\} $ be the set of features desired by Prof. Zhang. Let $ C \subseteq F_X \times F_Z $ be the set of conflicting pairs, with $ |C| = k $. **Constraints** 1. $ 1 \le n, m \le 100 $ 2. $ 1 \le k \le 10000 $ 3. $ 1 \le w_i \le 10^7 $ for all $ i \in \{1, \dots, n+m\} $ 4. For each conflict $ (p_i, q_i) \in C $: $ p_i \in F_X $, $ q_i \in F_Z $ **Objective** Find a subset $ S \subseteq F_X \cup F_Z $ such that: - $ S \cap C = \emptyset $ (no conflicting pair is selected), - The total weight $ \sum_{i \in S} w_i $ is maximized. Output the maximum total weight.

API Response (JSON)

{
  "problem": {
    "name": "D. Guessing Messages",
    "description": {
      "content": "Samuelo is a very good friend of Roppa. Whenever they feel bored, they like to exchange secret messages. To do that, they craft some text in such a way so that the hidden message is a subsequence of ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10230D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Samuelo is a very good friend of Roppa. Whenever they feel bored, they like to exchange secret messages.\n\nTo do that, they craft some text in such a way so that the hidden message is a subsequence of ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of features desired by Prof. Xie and Prof. Zhang, respectively.  \nLet $ W = (w_1, w_2, \\dots, w_{n+m}) \\in \\mathbb{Z}^{n+m} $ be the w...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments