codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2233C.md (2561B)


      1 Source: https://codeforces.com/problemset/problem/2233/C
      2 
      3 C. Cost of a Bracket Sequence
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Let the cost of an arbitrary bracket string be the length of it's longest subsequence$^{\text{∗}}$ that is a regular bracket sequence$^{\text{†}}$.
     22 
     23 You are given a bracket string $s$ and an integer $k$. Your task is to remove at most $k$ characters from the string $s$ so that the cost of the resulting string is minimized.
     24 
     25 $^{\text{∗}}$A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) element from arbitrary positions.
     26 
     27 $^{\text{†}}$A bracket sequence is called regular if it is possible to obtain a correct arithmetic expression by inserting the characters $+$ and $1$ into this sequence. For example, the sequences "$\texttt{(())()}$", "$\texttt{()}$", and "$\texttt{(()(()))}$" are regular, while "$\texttt{)(}$", "$\texttt{(()}$", and "$\texttt{(()))(}$" — are not.
     28 
     29 Input
     30 
     31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.
     32 
     33 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 5\,000$; $0 \le k \le n$) — the length of the string $s$ and the maximum number of deletions.
     34 
     35 The second line of each test case contains a string $s$ of length $n$ consisting of the characters "$\texttt{(}$" and/or "$\texttt{)}$".
     36 
     37 Additional input constraints:
     38 
     39 * the sum of $n$ over all test cases does not exceed $5\,000$.
     40 
     41 Output
     42 
     43 For each test case, output a binary string of length $n$. The $i$-th character should be equal to "1" if the corresponding character of the string $s$ is removed, and "0" otherwise.
     44 
     45 The number of ones in the string must not exceed $k$. The cost of the string obtained after removing the marked characters must be as small as possible.
     46 
     47 If there are several answers, output any of them.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 10
     55 
     56 2 1
     57 
     58 )(
     59 
     60 2 0
     61 
     62 ()
     63 
     64 4 1
     65 
     66 (())
     67 
     68 4 1
     69 
     70 ())(
     71 
     72 5 1
     73 
     74 ((())
     75 
     76 6 2
     77 
     78 ()()()
     79 
     80 6 2
     81 
     82 (()())
     83 
     84 6 2
     85 
     86 ())(()
     87 
     88 7 3
     89 
     90 (()((()
     91 
     92 10 3
     93 
     94 (()())())(
     95 ```
     96 
     97 Output
     98 
     99 ```
    100 00
    101 00
    102 1000
    103 1000
    104 00010
    105 101000
    106 001001
    107 100001
    108 1100001
    109 0101001000
    110 ```
    111 
    112 Note
    113 
    114 In the first test case, the cost of the string is already $0$, so it is possible not to delete anything.
    115 
    116 In the third test case, it is impossible to obtain a string of cost $0$ after one deletion, but it is possible to obtain a string of cost $2$ by deleting any character.