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.