Entering edit mode

You are given a string S of length M. It consists of only two

characters;

- (: Opening bracket
- ): Closing bracket

S is a balanced bracket sequence. Formally, a sequence of brackets is balanced-if the following conditions are met:

- It contains no unmatched brackets.
- The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets.

You are required to insert the character '+' in S such that there exists at least one '+' enclosed within each pair of matched

bracket sequence. Find the minimum number of ' characters to be inserted in S to satisfy the provided condition.

- The first line contains an integer T denoting the number of test cases. For each test case :-
- The of first line of each test case contains an integer -N denoting the length of string S
- The next line of each test case contains a string S.

For each test case. print the minimum number of characters that must be be inserted in string S in a new line.

1 ≤ T < 10

1≤ N ≤ 10

N is even

```
Sample Input Sample Output
1 2
6
()(())
```

Click here to Practice

Submit Problem to OJ

You are given the following:

- An array a consisting of n elements
- Integer k

For each (1 ≤ i ≤ n), perform the following operation exactly one

time:

- Replace a, by a, + x where z € [-k, k) which denotes should lie in the range of -k and k, both inclusive.

Determine the maximum length of the subsequence of array a, such that all numbers in that subsequence are equal after applying the given operation.

- A subsequence of array a is an array that can be derived from array a by removing some elements from it. (maybenone or all of them)
- Assume 1 based indexing

- n = 4
- k = 1
- Array a = [2, 5, 1, 2]

Applying one operation on indices 1, 2, and 4, with x = 0 to get

array a as [2, 5, 1, 2].

Applying one operation on index 3, with x = 1 to get array a as [2, 5, 2, 2]

Therefore, the maximum length of the subsequence with equal numbers is 3.

Complete the Maximize qualNumbers function provided in the editor. This function takes the following 3 parameters and returns the maximum length of the subsequence:

- n. Represents the size of array a
- k. Represents the integer k
- a. Represents the array a of length n

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

0 ≤ k ≤ 10^{9}

1 ≤ a_{i }≤ 10^{9 }

```
Sample Input Sample Output
2 2
4 0 2
2 2 5 6
3 2
1 5 6
```

The first line represents the number of test cases

For test case 1:

Applying one operation with x - 0 on index 1, 2, 3, and 4 to get array

as [2, 2,5, 6]

Consider a square matrix of size N sorted diagonally (bottom left to the top right). The diagonals in the matrix are numbered and filled with integer values from 1 to N^{2 }as given below.

For example, consider a square matrix of size N = 3 then we have

the following matrix. You are given Q queries

and each query has an Integer x.

Determine the diagonal number to which x belongs.

- The matrix is filled diagonally (bottom left to the top right). A diagonal is filled only all the previous diagonals are filled

- The diagonals are filled starting with integer value 1 and so on

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains an integer N denoting the size of the matrix.

• The next line contains an integer Q denoting the number queries.

• The next line contains Q space-separated integers denoting x for each query.

For each query, print a single integer in a new line representing

the diagonal number to which x belongs.

- 1
**≤**N**≤**10^{6} - 1
**≤**Q**≤**10^{6 } - 1
**≤**X**≤**N^{2}

```
Sample Input Sample Output
5 1
3 6
1 16 25 9
```

Consider a square matrix of size N = 5

For Query 1,1 occurs in the diagonal numbered 1

For Query 2,16 occurs in the diagonal numbered 6

For Query 3,25 occurs in the diagonal numbered 9

Entering edit mode

Since every element can be from a{i}-k to a{i}+k we will calculate the range of numbers an element can be and then calculate the maximum overlapping range.

Then

- The idea is to store coordinates in a new vector of pair mapped with characters ‘x’ and ‘y’, to identify coordinates.
- Sort the vector.
- Traverse the vector, if an 'x' coordinate is encountered it means a new range is added, so update count and if 'y' coordinate is encountered that means a range is subtracted.
- Update the value of the count for every new coordinate and take the maximum.

```
void solve() {
int n, k;
cin >> n >> k;
int ans = 0;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
/*since every element can be from a{i}-k to a{i}+k we will
calculate the range of numbers an element can be and then
calculate the maximum overlapping range */
vector<pair<int, char>> v;
for (int i = 0; i < n; i++) {
v.push_back({a[i] - k, 'x'});
v.push_back({a[i] + k, 'y'});
}
sort(v.begin(), v.end());
int count = 0;
for (int i = 0; i < v.size(); i++) {
// if x occur it means a new range
// is added so we increase count
if (v[i].second == 'x')
count++;
// if y occur it means a range
// is ended so we decrease count
if (v[i].second == 'y')
count--;
// updating the value of ans
// after every traversal
ans = max(ans, count);
}
cout << ans << endl;
return;
}
```

O(n log n) n is the size of the array.

A vector of pair is not required I believe, You can just sort the given array and use a sliding window approach to maximise the overlapping intervals.