10 weeks ago

Abhilash Kalyanakrishnan 190

Question 1

Balanced brackets

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.

Input format

• 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. 

Output format

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

Constraints

1 ≤ T < 10
1≤ N ≤ 10
N is even

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

Question 2

Maximize equal numbers

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.

Task

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

Notes

•  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

Example

Assumptions

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

Approach

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.

Function description

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

Input format

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

0 ≤ k ≤ 10⁹

1 ≤ a_i ≤ 10⁹  

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

Explanation

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]

Question 3

Diagonal number

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² 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.

Task

Determine the diagonal number to which x belongs.

Notes

• 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

Input Format 

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.

Output format

For each query, print a single integer in a new line representing
the diagonal number to which x belongs.

Constraints

• 1 ≤  N ≤  10⁶
• 1 ≤  Q ≤  10⁶  
• 1 ≤  X ≤  N²

Sample Input             Sample Output

5                              1
3                              6
1 16 25                        9

Explanation

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

2 days ago

Akash 220

Problem 2

Approach

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.

Code

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;

}

Complexity 

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