2.2 years ago

Abhilash Kalyanakrishnan • 320

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

5 months ago

Akash 240

Ghaziabad

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.

18 months ago

Mayank Jain • 10

Delhi

Problem 2

Used a Sliding window kind of approach

import java.util.*;
public class Main {
    public static void main(String[] args) {
      Scanner sc=new Scanner(System.in);
      int n=sc.nextInt();
      int k=sc.nextInt();
      int[] arr=new int[n];
      for(int i=0;i<n;i++)
        arr[i]=sc.nextInt();
      Arrays.sort(arr);
      int idx=1;
      int ans=1;
      int l=0, r=1;
      while(r<n){
        while(idx<n&&arr[l]==arr[idx]){
          idx++;
        } 
        if(r<n&&arr[l]+k>=arr[r]-k){ 
          r++;
          ans=Math.max(ans,r-l);
        }
        else{
          l=idx;
        }
        
      }
      System.out.println(ans);
    }
  }

11 months ago

Manpreet Singh Saluja • 0

Guwahati

Problem 2

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {

    int n,k;
    cin>>n>>k;
    
    vector<int>arr(n);
    for(int i=0;i<n;i++){
      cin>>arr[i];
    }
    
    sort(arr.begin(),arr.end());
    
    int ans = 1;
    for(int i=0;i<n;i++)
    {
        int count = 0;
        int it = (arr.begin()+i) - upper_bound(arr.begin(),arr.begin()+i,arr[i]-k-1);
        count += it;
        it = upper_bound(arr.begin()+i,arr.end(),arr[i]+k) - (arr.begin()+i);
        count += it;
        ans = max(ans,count);
    }
    
    cout<<ans<<endl;
     
    return 0;

  }

Getting Wrong answer on 15th test case

3 months ago

Sourav Mohapatra • 0

Dhanbad

Problem 1:

<code>

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
   int n;
   cin >> n;
   string s;
   cin >> s;
   vector<pair<int, int>> pairs;
   stack<pair<char, int>> st;
   for (int i = 0; i < n; i++) {
       if (s[i] == '(') {
           st.push({'(', i});
       } else {
           auto p = st.top();
           st.pop();
           pairs.push_back({p.second, i});
       }
   }

   int ans = 100;

   auto check = [&](int l, int r, int mask) -> bool {
       for (int i = l + 1; i <= r; i++) {
           if (mask & (1 << i)) {
               return true;
           }
       }
       return false;
   };

   for (int mask = 0; mask < (1 << (n + 1)); mask++) {
       int bits = __builtin_popcount(mask);
       if (bits >= ans)
           continue;
       bool ok = true;
       for (const auto &[l, r] : pairs) {
           if (!check(l, r, mask)) {
               ok = false;
               break;
           }
       }
       if (ok)
           ans = bits;
   }

   cout << ans << "\n";
}

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int t;
   cin >> t;
   while (t--) {
       solve();
   }
}

</code>
 

Problem 3:
<code>

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    int m = 2*n - 1;
    vector<ll> p(m + 1, 0);
    for (int i = 1; i <= m + 1 - i; i++) {
        p[i] = p[m + 1 - i] = i;
    }
    for (int i = 1; i <= m; i++) {
        p[i] = p[i - 1] + p[i];
    }

    while (q--) {
        ll x;
        cin >> x;
        int l = 1, r = m;
        while (l < r) {
            int mid = (l + r) / 2;
            if (p[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        cout << r << " ";
    }
    cout << "\n";
}

</code>