codeforces-scrape

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

2190B1.md (3051B)


      1 Source: https://codeforces.com/problemset/problem/2190/B1
      2 
      3 B1. Sub-RBS (Easy Version)
      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 This is the easy version of the problem. The difference between the versions is that in this version, you only need to evaluate for whole string $s$, $s$ is regular, and the constraints on $n$ are higher.
     22 
     23 We say that a bracket sequence $a$ is better than a bracket sequence $b$ if one of the following holds:
     24 
     25 * $b$ is a prefix of $a$, but $a \ne b$; or
     26 * let $i$ be the first position (if it exists) where $a_i \neq b_i$, then $\color{red}{a_i = \texttt{(}}$ and $\color{red}{b_i = \texttt{)}}$.
     27 
     28 You are given a regular bracket sequence$^{\text{∗}}$ $s$ of even length $n$.
     29 
     30 Among all non-empty subsequences $^{\text{†}}$ $t$ of $s$ that are regular bracket sequences, find the maximum possible length of $t$ such that $t$ is better than $s$. If no such $t$ exists, report it.
     31 
     32 $^{\text{∗}}$A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting the characters $\texttt{1}$ and $\texttt{+}$ between the original characters of the sequence. For example:
     33 
     34 * bracket sequences $\texttt{()()}$ and $\texttt{(())}$ are regular (the resulting expressions are $\texttt{(1)+(1)}$ and $\texttt{((1+1)+1)}$);
     35 * bracket sequences $\texttt{)(}$, $\texttt{(}$, and $\texttt{)}$ are not.
     36 
     37 $^{\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.
     38 
     39 Input
     40 
     41 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     42 
     43 The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$, $n$ is even) — the length of the string $s$.
     44 
     45 The second line of each test case contains a sequence $s$ of length $n$ consisting only of characters $\texttt{(}$ and $\texttt{)}$.
     46 
     47 It is guaranteed that the given sequence $s$ is a regular bracket sequence.
     48 
     49 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     50 
     51 Output
     52 
     53 For each test case, print a single integer — the maximum possible length of a non-empty subsequence $t$ of $s$ that is a regular bracket sequence and is better than $s$. If no such $t$ exists, print $-1$.
     54 
     55 Example
     56 
     57 Input
     58 
     59 ```
     60 3
     61 
     62 2
     63 
     64 ()
     65 
     66 8
     67 
     68 (()(()))
     69 
     70 6
     71 
     72 (())()
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 -1
     79 
     80 6
     81 
     82 -1
     83 ```
     84 
     85 Note
     86 
     87 In the first example, the only non-empty regular bracket subsequence of $s$ is $t = s = \texttt{()}$. Since $t$ is not better than $s$, we output $-1$.
     88 
     89 In the second example, we can choose $t = \texttt{((()))}$. The first index where $t$ and $s$ differ is $i = 3$. Since $t_3 = \texttt{(}$ and $s_3 = \texttt{)}$, $t$ is better than $s$. We cannot choose a longer subsequence because the only longer regular bracket subsequence is $s$ itself, which is not better than $s$. Thus, we output $6$.