codeforces-scrape

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

1726C.md (2565B)


      1 Source: https://codeforces.com/problemset/problem/1726/C
      2 
      3 C. Jatayu's Balanced Bracket Sequence
      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 Last summer, Feluda gifted Lalmohan-Babu a balanced bracket sequence $s$ of length $2 n$.
     22 
     23 Topshe was bored during his summer vacations, and hence he decided to draw an undirected graph of $2 n$ vertices using the balanced bracket sequence $s$. For any two distinct vertices $i$ and $j$ ($1 \le i \lt j \le 2 n$), Topshe draws an edge (undirected and unweighted) between these two nodes if and only if the subsegment $s[i \ldots j]$ forms a balanced bracket sequence.
     24 
     25 Determine the number of connected components in Topshe's graph.
     26 
     27 See the Notes section for definitions of the underlined terms.
     28 
     29 Input
     30 
     31 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Description of the test cases follows.
     32 
     33 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of opening brackets in string $s$.
     34 
     35 The second line of each test case contains a string $s$ of length $2 n$ — a balanced bracket sequence consisting of $n$ opening brackets "(", and $n$ closing brackets ")".
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     38 
     39 Output
     40 
     41 For each test case, output a single integer — the number of connected components in Topshe's graph.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 4
     49 
     50 1
     51 
     52 ()
     53 
     54 3
     55 
     56 ()(())
     57 
     58 3
     59 
     60 ((()))
     61 
     62 4
     63 
     64 (())(())
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 1
     71 2
     72 3
     73 3
     74 ```
     75 
     76 Note
     77 
     78 Sample explanation:
     79 
     80 In the first test case, the graph constructed from the bracket sequence (), is just a graph containing nodes $1$ and $2$ connected by a single edge.
     81 
     82 In the second test case, the graph constructed from the bracket sequence ()(()) would be the following (containing two connected components):
     83 
     84  ![](https://espresso.codeforces.com/aa2eec032f75bb3896af632d6c4cb02942a32c1c.png) 
     85 
     86 Definition of Underlined Terms:
     87 
     88 * A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters $+$ and $1$. For example, sequences (())(), (), and (()(())) are balanced, while )(, ((), and (()))( are not.
     89 * The subsegment $s[l \ldots r]$ denotes the sequence $[s_l, s_{l + 1}, \ldots, s_r]$.
     90 * A connected component is a set of vertices $X$ such that for every two vertices from this set there exists at least one path in the graph connecting these vertices, but adding any other vertex to $X$ violates this rule.