codeforces-scrape

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

1167D.md (2460B)


      1 Source: https://codeforces.com/problemset/problem/1167/D
      2 
      3 D. Bicolored RBS
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 A string is called bracket sequence if it does not contain any characters other than "(" and ")". A bracket sequence is called regular (shortly, RBS) if it is possible to obtain correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, "", "(())" and "()()" are RBS and ")(" and "(()" are not.
     22 
     23 We can see that each opening bracket in RBS is paired with some closing bracket, and, using this fact, we can define nesting depth of the RBS as maximum number of bracket pairs, such that the $2$-nd pair lies inside the $1$-st one, the $3$-rd one — inside the $2$-nd one and so on. For example, nesting depth of "" is $0$, "()()()" is $1$ and "()((())())" is $3$.
     24 
     25 Now, you are given RBS $s$ of even length $n$. You should color each bracket of $s$ into one of two colors: red or blue. Bracket sequence $r$, consisting only of red brackets, should be RBS, and bracket sequence, consisting only of blue brackets $b$, should be RBS. Any of them can be empty. You are not allowed to reorder characters in $s$, $r$ or $b$. No brackets can be left uncolored.
     26 
     27 Among all possible variants you should choose one that minimizes maximum of $r$'s and $b$'s nesting depth. If there are multiple solutions you can print any of them.
     28 
     29 Input
     30 
     31 The first line contains an even integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of RBS $s$.
     32 
     33 The second line contains regular bracket sequence $s$ ($|s| = n$, $s_i \in \{$"(", ")"$\}$).
     34 
     35 Output
     36 
     37 Print single string $t$ of length $n$ consisting of "0"-s and "1"-s. If $t_i$ is equal to 0 then character $s_i$ belongs to RBS $r$, otherwise $s_i$ belongs to $b$.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 2
     45 ()
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 11
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 4
     58 (())
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 0101
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 10
     71 ((()())())
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 0110001111
     78 ```
     79 
     80 Note
     81 
     82 In the first example one of optimal solutions is $s = $ "$\color{blue}{()}$". $r$ is empty and $b = $ "$()$". The answer is $\max(0, 1) = 1$.
     83 
     84 In the second example it's optimal to make $s = $ "$\color{red}{(}\color{blue}{(}\color{red}{)}\color{blue}{)}$". $r = b = $ "$()$" and the answer is $1$.
     85 
     86 In the third example we can make $s = $ "$\color{red}{(}\color{blue}{((}\color{red}{)()}\color{blue}{)())}$". $r = $ "$()()$" and $b = $ "$(()())$" and the answer is $2$.