C. Bracket Subsequence

Codeforces

IDCF1023C

Time2000ms

Memory256MB

Difficulty—

greedy

English · Original

Chinese · Translation

Formal · Original

A bracket sequence is a string containing only characters "_(_" and "_)_". A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "_1_" and "_+_" between the original characters of the sequence. For example, bracket sequences "_()()_" and "_(())_" are regular (the resulting expressions are: "_(1)+(1)_" and "_((1+1)+1)_"), and "_)(_", "_(_" and "_)_" are not. _Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements._ You are given a regular bracket sequence $s$ and an integer number $k$. Your task is to find a regular bracket sequence of length exactly $k$ such that it is also a subsequence of $s$. It is guaranteed that such sequence always exists. ## Input The first line contains two integers $n$ and $k$ ($2 \le k \le n \le 2 \cdot 10^5$, both $n$ and $k$ are even) — the length of $s$ and the length of the sequence you are asked to find. The second line is a string $s$ — regular bracket sequence of length $n$. ## Output Print a single string — a regular bracket sequence of length exactly $k$ such that it is also a subsequence of $s$. It is guaranteed that such sequence always exists. [samples]

括号序列是仅包含字符 "_(_" 和 "_)_" 的字符串。正则括号序列是指可以通过在原序列的字符之间插入字符 "_1_" 和 "_+_" 转换为正确算术表达式的括号序列。例如，括号序列 "_()()_" 和 "_(())_" 是正则的（对应的表达式分别为 "_(1)+(1)_" 和 "_((1+1)+1)_"），而 "_)(_"、"_(_" 和 "_)_" 则不是。 _子序列是从另一个序列中删除某些元素而不改变剩余元素顺序所得到的序列。_ 给定一个正则括号序列 $s$ 和一个整数 $k$，你的任务是找到一个长度恰好为 $k$ 的正则括号序列，且它是 $s$ 的子序列。题目保证这样的序列一定存在。第一行包含两个整数 $n$ 和 $k$（$2 lt.eq k lt.eq n lt.eq 2 dot.op 10^5$，且 $n$ 和 $k$ 均为偶数）——分别表示 $s$ 的长度和你需要找到的序列的长度。第二行是一个字符串 $s$——长度为 $n$ 的正则括号序列。请输出一个字符串——一个长度恰好为 $k$ 的正则括号序列，且它是 $s$ 的子序列。题目保证这样的序列一定存在。 ## Input 第一行包含两个整数 $n$ 和 $k$（$2 lt.eq k lt.eq n lt.eq 2 dot.op 10^5$，且 $n$ 和 $k$ 均为偶数）——分别表示 $s$ 的长度和你需要找到的序列的长度。第二行是一个字符串 $s$——长度为 $n$ 的正则括号序列。 ## Output 请输出一个字符串——一个长度恰好为 $k$ 的正则括号序列，且它是 $s$ 的子序列。题目保证这样的序列一定存在。 [samples]

**Definitions** Let $ n, k \in \mathbb{Z} $ be even integers such that $ 2 \leq k \leq n \leq 2 \cdot 10^5 $. Let $ s \in \{ (, ) \}^n $ be a regular bracket sequence of length $ n $. A *bracket sequence* is a string over the alphabet $ \{ (, ) \} $. A *regular bracket sequence* is a bracket sequence that is balanced (equal number of opening and closing brackets, and every prefix has at least as many opening as closing brackets). A *subsequence* of $ s $ is a sequence obtained by deleting zero or more characters from $ s $ without changing the order of the remaining characters. **Constraints** 1. $ n, k $ are even. 2. $ s $ is a regular bracket sequence of length $ n $. 3. $ 2 \leq k \leq n $. **Objective** Find a regular bracket sequence $ t \in \{ (, ) \}^k $ such that $ t $ is a subsequence of $ s $. **Output** Output any such $ t $.

Samples

Input #1

6 4
()(())

Output #1

()()

Input #2

8 8
(()(()))

Output #2

(()(()))

API Response (JSON)

{
  "problem": {
    "name": "C. Bracket Subsequence",
    "description": {
      "content": "A bracket sequence is a string containing only characters \"_(_\" and \"_)_\". A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting ch",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1023C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A bracket sequence is a string containing only characters \"_(_\" and \"_)_\". A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting ch...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "括号序列是仅包含字符 \"_(_\" 和 \"_)_\" 的字符串。正则括号序列是指可以通过在原序列的字符之间插入字符 \"_1_\" 和 \"_+_\" 转换为正确算术表达式的括号序列。例如，括号序列 \"_()()_\" 和 \"_(())_\" 是正则的（对应的表达式分别为 \"_(1)+(1)_\" 和 \"_((1+1)+1)_\"），而 \"_)(_\"、\"_(_\" 和 \"_)_\" 则不是。\n\n_子序列是从另一个序列中删...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ be even integers such that $ 2 \\leq k \\leq n \\leq 2 \\cdot 10^5 $.  \nLet $ s \\in \\{ (, ) \\}^n $ be a regular bracket sequence of length $ n $.  \n\nA *bracke...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments