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.