codeforces-scrape

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

2223A.md (2690B)


      1 Source: https://codeforces.com/problemset/problem/2223/A
      2 
      3 A. Zhily and Bracket Swapping
      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 Deep in the wilderness, Zhily and Jily discovered two sequences composed of brackets. Each sequence carries some logical structure, but neither of them is necessarily a regular bracket sequence on its own. They found that by swapping brackets between the two sequences, they could repair them. They wish to make both sequences regular bracket sequences by swapping brackets between them.
     22 
     23 A regular bracket sequence is a sequence consisting of '(' and ')', which can be turned into a valid math expression by inserting 1 and + any number of times into the sequence. For example, the sequence "()(()())" is a regular bracket sequence, while "())((" or "(()" are not regular bracket sequences.
     24 
     25 You are given two bracket sequences $a$ and $b$ of even length $n$. You can perform the following operation any number of times:
     26 
     27 * Choose a position $i$ ($1 \leq i \leq n$) and swap $a_i$ and $b_i$.
     28 
     29 Determine whether you can turn both $a$ and $b$ into regular bracket sequences.
     30 
     31 Input
     32 
     33 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.
     34 
     35 The first line of each test case contains a single integer $n$ ($2 \leq n \leq 2\cdot 10^5$, $n$ is even) — the length of the strings $a$ and $b$.
     36 
     37 The second line of each test case contains a sequence $a$ of length $n$ consisting only of characters '(' and ')'.
     38 
     39 The third line of each test case contains a sequence $b$ of length $n$ consisting only of characters '(' and ')'.
     40 
     41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, output "YES" if you can turn both $a$ and $b$ into a regular bracket sequences, "NO" otherwise. You can output "YES" and "NO" in any case (for example, "yES", "yes", and "Yes" will be recognized as a positive response).
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 7
     53 
     54 2
     55 
     56 ()
     57 
     58 ()
     59 
     60 4
     61 
     62 ))((
     63 
     64 (())
     65 
     66 4
     67 
     68 ((((
     69 
     70 ))))
     71 
     72 4
     73 
     74 ()()
     75 
     76 (())
     77 
     78 6
     79 
     80 (((())
     81 
     82 ()()))
     83 
     84 8
     85 
     86 ()()()()
     87 
     88 (((())))
     89 
     90 4
     91 
     92 ((((
     93 
     94 ((((
     95 ```
     96 
     97 Output
     98 
     99 ```
    100 YES
    101 
    102 NO
    103 
    104 NO
    105 
    106 YES
    107 
    108 YES
    109 
    110 YES
    111 
    112 NO
    113 ```
    114 
    115 Note
    116 
    117 In the first, fourth, and sixth test cases, both $a$ and $b$ are initially regular bracket sequences.
    118 
    119 In the second and third test cases, either $a_1$ or $b_1$ will be ')', which makes it impossible for them to be regular.
    120 
    121 In the fifth test case, the final sequences may be $\texttt{(((}\color{red}{\texttt{)}}\texttt{))}$ and $\texttt{()(}\color{red}{\texttt{(}}\texttt{))}$, where the brackets to be swapped are colored red.