C. Cyclic Song

Codeforces

IDCF10231C

Time5000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Eugene is inventing a new type of musical piece which has a few interesting properties. A valid song of Type $N$ has the following properties: Here are some examples of valid and invalid songs: Eugene would like you to create a _special_ song of type $N$. He will specify two substrings $S$ and $T$ of length $N$. During a performance, the time between a performance of $S$ and the next performance of $T$ should be minimized. The performance of $S$ and $T$ can possibly overlap. Formally, let $X$ be the set of indices at which a substring equal to $S$ begins, and let $Y$ be the set of indices at which a substring equal to $T$ begins. Then we want to minimize $min {y -x : x in X " and "y in Y " and "y >= x}$. For example, for $N = 3$, $S = A A B$, and $S = A B A$, then $A A B A B B B A$ makes Eugene happy (because $A A B$ appears at position 1 and $A B A$ appears at position 2, so the time between their performances is only 1), but $A A B B B A B A$ makes Eugene sad (because $A A B$ appears at position 1, but $A B A$ appears at position 6, so the time between their performances is 5, which is not minimal) Eugene will be very happy if you can help him write a special song of Type $N$ which minimizes the time from a performance of $S$ to a performance of $T$. The first line contains an integer $N$ ($2 <= N <= 20$), the type of the song. The second line contains the string $S$, the first special substring that Eugene wants to see. The third line contains the string $T$, the second special substring that Eugene wants to see. It is guaranteed that $| S | = | T | = N$. Output a single line, a valid song of Type $N$ that makes Eugene happy. If there are multiple such songs that make Eugene happy, output any of them. If Eugene cannot be happy, then output "SAD" (without quotation marks). ## Input The first line contains an integer $N$ ($2 <= N <= 20$), the type of the song.The second line contains the string $S$, the first special substring that Eugene wants to see. The third line contains the string $T$, the second special substring that Eugene wants to see.It is guaranteed that $| S | = | T | = N$. ## Output Output a single line, a valid song of Type $N$ that makes Eugene happy. If there are multiple such songs that make Eugene happy, output any of them. If Eugene cannot be happy, then output "SAD" (without quotation marks). [samples]

**Definitions** Let $ N \in \mathbb{Z} $ with $ 2 \leq N \leq 20 $. Let $ S, T \in \Sigma^N $ be two fixed strings over an alphabet $ \Sigma $ (assumed to be binary or finite, context-dependent). Let $ X \subseteq \mathbb{Z}_{\geq 1} $ be the set of starting indices of occurrences of $ S $ in a song $ W \in \Sigma^* $. Let $ Y \subseteq \mathbb{Z}_{\geq 1} $ be the set of starting indices of occurrences of $ T $ in $ W $. **Constraints** 1. The song $ W $ must be a finite string over $ \Sigma $ such that it contains at least one occurrence of $ S $ and at least one occurrence of $ T $. 2. For any $ x \in X $, $ y \in Y $, we require $ y \geq x $ to compute the delay $ y - x $. **Objective** Minimize $ \min \{ y - x \mid x \in X, y \in Y, y \geq x \} $ over all possible songs $ W $ of Type $ N $. Output any such $ W $ achieving the minimal delay. If no such $ W $ exists, output "SAD".

API Response (JSON)

{
  "problem": {
    "name": "C. Cyclic Song",
    "description": {
      "content": "Eugene is inventing a new type of musical piece which has a few interesting properties. A valid song of Type $N$ has the following properties: Here are some examples of valid and invalid songs: Eug",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10231C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Eugene is inventing a new type of musical piece which has a few interesting properties.\n\nA valid song of Type $N$ has the following properties:\n\nHere are some examples of valid and invalid songs:\n\nEug...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $ with $ 2 \\leq N \\leq 20 $.  \nLet $ S, T \\in \\Sigma^N $ be two fixed strings over an alphabet $ \\Sigma $ (assumed to be binary or finite, context-dependent). ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments