[Solution] Bring Balance Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Bring Balance Codeforces Solution | Codeforces Problem Solution 2022

E. Bring Balance

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Alina has a bracket sequence s$s$ of length 2n$2n$, consisting of n$n$ opening brackets '(' and n$n$ closing brackets ')'. As she likes balance, she wants to turn this bracket sequence into a balanced bracket sequence.

In one operation, she can reverse any substring of s$s$.

What's the smallest number of operations that she needs to turn s$s$ into a balanced bracket sequence? It can be shown that it's always possible in at most n$n$ operations.

Solution Click Below:-  CLICK HERE

As a reminder, 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.

Input

The first line of the input contains a single integer t$t$ (1≤t≤2⋅104$1\le t\le 2\cdot {10}^4$)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n$n$ (1≤n≤105$1\le n\le {10}^5$).

Everything Everywhere All But One Codeforces Solution

Odd Subarrays Codeforces Solution

Circular Local MiniMax Codeforces Solution

Linguistics Codeforces Solution

Bring Balance Codeforces Solution 

Permutation Weight (Easy Version) Codeforces Solution

The second line of each test case contains a string s$s$ of length 2n$2n$, consisting of n$n$ opening and n$n$ closing brackets.

The sum of n$n$ over all test cases doesn't exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, in the first line output a single integer k$k$ (0≤k≤n)$(0\le k\le n)$  — the smallest number of operations required.

The i$i$-th of the next k$k$ lines should contain two integers li,ri$l_i,r_i$ (1≤li≤ri≤2n$1\le l_i\le r_i\le 2n$), indicating that in the i$i$-th operation, Alina will reverse the substring slsl+1…sr−1sr$s_l{s}_{l+1}\dots s_{r-1}{s}_r$. Here the numeration starts from 1$1$.

If there are multiple sequences of operations with the smallest length which transform the sequence into a balanced one, you can output any of them.