A. Edit Distance

Codeforces

IDCF10200A

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

A binary string is a non-empty sequence of $0$'s and $1$'s, e.g., _010110_, _1_, _11101_, etc. The edit distance of two binary strings $S$ and $T$, denoted by $e d i t (S, T)$, is the minimum number of single-character edit (insert, delete, or substitute) to modify $S$ into $T$. For example, the edit distance of _0011_ and _1100_ is $4$, i.e. _0011_ $arrow.r$ _011_ $arrow.r$ _11_ $arrow.r$ _110_ $arrow.r$ _1100_. The edit distance of _1100101_ and _1110100_ is $2$, i.e. _1100101_ $arrow.r$ _1110101_ $arrow.r$ _1110100_. Ayu has a binary string $S$. She wants to find a binary string with the same length as $S$ that maximizes the edit distance with $S$. Formally, she wants to find a binary string $T_{m a x}$ such that $| S | = | T_{m a x} |$ and $e d i t (S, T_{m a x}) >= e d i t (S, T ')$ for all binary string $T '$ satisfying $| S | = | T ' |$. She needs your help! However, since she wants to make your task easier, you are allowed to return any binary string $T$ with the same length as $S$ such that the edit distance of $S$ and $T$ is more than half the length of $S$. Formally, you must return a binary string $T$ such that $| S | = | T |$ and $e d i t (S, T) > frac(| S |, 2)$. Of course, you can still return $T_{m a x}$ if you want, since it can be proven that $e d i t (S, T_{m a x}) > frac(| S |, 2)$ for any binary string $S$. This also proves that there exists a solution for any binary string $S$. If there is more than one valid solution, you can output any of them. Input contains a binary string $S$ ($1 <= | S | <= 2000$). Output in a line a binary string $T$ with the same length as $S$ that satisfies $e d i t (S, T) > frac(| S |, 2)$. _Explanation for the sample input/output #1_ As illustrated in the example above, the edit distance of _0011_ and _1100_ is $4$. Since $4 > frac(4, 2)$, _1100_ is one of the valid output for this sample. ## Input Input contains a binary string $S$ ($1 <= | S | <= 2000$). ## Output Output in a line a binary string $T$ with the same length as $S$ that satisfies $e d i t (S, T) > frac(| S |, 2)$. [samples] ## Note _Explanation for the sample input/output #1_As illustrated in the example above, the edit distance of _0011_ and _1100_ is $4$. Since $4 > frac(4, 2)$, _1100_ is one of the valid output for this sample.

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. Let $ D_k = (d_{k,1}, d_{k,2}, \dots, d_{k,12}) $ be a sequence of 12 distinct integers representing the estimated difficulties of problems A to L in the $ k $-th test case, where $ d_{k,i} $ is the difficulty of the $ i $-th problem. **Constraints** 1. $ 1 \leq T \leq 4096 $ 2. For each $ k \in \{1, \dots, T\} $: - $ 1 \leq d_{k,i} \leq 100 $ for all $ i \in \{1, \dots, 12\} $ - All $ d_{k,i} $ are distinct. **Objective** For each test case $ k $, determine whether the sequence $ D_k $ is in **strictly increasing order**. That is, output "yes" if $ d_{k,1} < d_{k,2} < \dots < d_{k,12} $, otherwise output "no".

API Response (JSON)

{
  "problem": {
    "name": "A. Edit Distance",
    "description": {
      "content": "A binary string is a non-empty sequence of $0$'s and $1$'s, e.g., _010110_, _1_, _11101_, etc. The edit distance of two binary strings $S$ and $T$, denoted by $e d i t (S, T)$, is the minimum number o",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10200A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A binary string is a non-empty sequence of $0$'s and $1$'s, e.g., _010110_, _1_, _11101_, etc. The edit distance of two binary strings $S$ and $T$, denoted by $e d i t (S, T)$, is the minimum number o...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nLet $ D_k = (d_{k,1}, d_{k,2}, \\dots, d_{k,12}) $ be a sequence of 12 distinct integers representing the estimated difficultie...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments