F. Erasing Substrings

Codeforces

IDCF938F

Time1000ms

Memory256MB

Difficulty—

bitmasksdpgreedy

English · Original

Chinese · Translation

Formal · Original

You are given a string _s_, initially consisting of _n_ lowercase Latin letters. After that, you perform _k_ operations with it, where . During _i_\-th operation you **must** erase some substring of length exactly 2_i_ - 1 from _s_. Print the lexicographically minimal string you may obtain after performing _k_ such operations. ## Input The only line contains one string _s_ consisting of _n_ lowercase Latin letters (1 ≤ _n_ ≤ 5000). ## Output Print the lexicographically minimal string you may obtain after performing _k_ operations. [samples] ## Note Possible operations in examples: 1. adcb**c**a a**dc**ba aba; 2. ab**a**cabadabacaba a**bc**abadabacaba aaba**daba**caba aabacaba.

给定一个字符串 #cf_span[s]，初始时由 #cf_span[n] 个小写拉丁字母组成。之后，你对它执行 #cf_span[k] 次操作，其中。在第 #cf_span[i] 次操作中，你*必须*删除 #cf_span[s] 中一个长度恰好为 #cf_span[2i - 1] 的子串。输出经过 #cf_span[k] 次操作后可能得到的字典序最小的字符串。唯一的一行包含一个由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]（#cf_span[1 ≤ n ≤ 5000]）。请输出经过 #cf_span[k] 次操作后可能得到的字典序最小的字符串。示例中的可能操作： ## Input 唯一的一行包含一个由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]（#cf_span[1 ≤ n ≤ 5000]）。 ## Output 请输出经过 #cf_span[k] 次操作后可能得到的字典序最小的字符串。 [samples] ## Note 示例中的可能操作： adcb*c*a → a*dc*ba → aba； ab*a*cabadabacaba → a*bc*abadabacaba → aaba*daba*caba → aabacaba。

**Definitions** Let $ s \in \Sigma^n $ be the initial string, where $ \Sigma = \{a, b, \dots, z\} $ and $ n \in \mathbb{Z}^+ $, $ 1 \le n \le 5000 $. Let $ k \in \mathbb{Z}^+ $ be the number of operations, where $ k = \left\lfloor \frac{n}{2} \right\rfloor $. For each operation $ i \in \{1, \dots, k\} $, you must remove a contiguous substring of length $ 2i - 1 $. **Constraints** 1. $ 1 \le n \le 5000 $ 2. For each operation $ i \in \{1, \dots, k\} $, the substring removed has length $ 2i - 1 $. 3. After $ k $ operations, the remaining string has length $ n - \sum_{i=1}^k (2i - 1) = n - k^2 \ge 0 $. **Objective** Find the lexicographically minimal string obtainable after performing exactly $ k $ operations, each removing a substring of length $ 2i - 1 $ in the $ i $-th step.

Samples

Input #1

adcbca

Output #1

aba

Input #2

abacabadabacaba

Output #2

aabacaba

API Response (JSON)

{
  "problem": {
    "name": "F. Erasing Substrings",
    "description": {
      "content": "You are given a string _s_, initially consisting of _n_ lowercase Latin letters. After that, you perform _k_ operations with it, where . During _i_\\-th operation you **must** erase some substring of l",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF938F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a string _s_, initially consisting of _n_ lowercase Latin letters. After that, you perform _k_ operations with it, where . During _i_\\-th operation you **must** erase some substring of l...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个字符串 #cf_span[s]，初始时由 #cf_span[n] 个小写拉丁字母组成。之后，你对它执行 #cf_span[k] 次操作，其中 。在第 #cf_span[i] 次操作中，你*必须*删除 #cf_span[s] 中一个长度恰好为 #cf_span[2i - 1] 的子串。\n\n输出经过 #cf_span[k] 次操作后可能得到的字典序最小的字符串。\n\n唯一的一行包含一个由 #cf...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\Sigma^n $ be the initial string, where $ \\Sigma = \\{a, b, \\dots, z\\} $ and $ n \\in \\mathbb{Z}^+ $, $ 1 \\le n \\le 5000 $.  \nLet $ k \\in \\mathbb{Z}^+ $ be the number of op...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments