Q1. Great Bank of Spain - Easy Level - Time Limit (20 mins)

El Professor is back with his crew and this time they are planning a heist in the Great Bank of Spain. They have come up with a plan for the heist, but the Professor is struggling with one problem - that is how to unlock the doors of the Grand Vault in the bank which contains all the valuable treasures gathered by Spain from its history. The Grand Vault can only be opened by a right sequence of numbers. Professor asks his favorite crew member Rio to help with this problem.

Rio will be given an array s of n strings s0,s1,....., sn-1 where each string represents a number and integer d, such that every number in s has exactly d digits and none of these digits is 0. Rio will have to provide answer to q queries. The ith query contains two integers k[i] and m[i] and requires him to come up with the k'ith smallest number in a set containing all numbers from array s trimmed to m'ith least significant digits. The solution to the ith query is actually the ith number in the sequence to open the vault. Assuming you are Rio, come up with an algorithm to make this a successful heist.

Function Description:
Complete the function grandVaultSequence in the editor below. The function must return a long integer array of q integers denoting the answers to the consecutive queries.

grandVaultSequence has 4 parameters:
s: The original array of strings.
d: Integer representing the number of digits in every element of array a.
k: Integer array of values where each element in k, denotes the smallest number from the set as described.
m: Integer array of values where each element in m, denotes the value to which the corresponding element in a is trimmed to.

Constraints:

• 1<=n<=1e5
• 1<=d<=15
• 1<=q<=1e5
• 1<=k_i<=n
• 1<=m_i<=d

Sample Input 0:
2
15
21
2
2
1
1
2
2
1

Sample Output 0:
15
1

Explanation 0:
The given array is [15,21]. There are 2 queries to answer. The first of them asks for the smallest number in the array when all numbers are trimmed to 2 least significant digits. These trimmed numbers are [15, 21], so the answer is 15. The second query asks for the smallest number if all numbers are trimmed to the least significant digit. These trimmed numbers are [5, 1] so the answer is 1.

Sample Input 1:
2
99
88
2
2
1
1
2
2
1

Sample Output 1:
88
8

Explanation 1:
The given array is [99,88]. There are 2 queries to answer. The first of them asks for the smallest number in the array when all numbers are trimmed to 2 least significant digits. These trimmed numbers are [99, 88], so the answer is 88. The second query asks for the smallest number if all numbers are trimmed to the least significant digit. These trimmed numbers are [9, 8] so the answer is 8.

Sample Input 2:
2
991
881
3
3
1
1
2
3
3
1
1

Sample Output 2:
881
1
1

Q2. Matrix Strength Maximization - Medium Level - Time Limit (30 mins)

You have a hypothetical network of distributed systems which can be represented in the form of a two dimensional grid s, consisting of '#' and '.' only, where '#' represents that there is a system at this location.

Two systems located at cells (r1,c1) and (r2, c2) respectively have a connectivity strength equal to abs(r1-r2) + abs(c1-c2).

You need to select a group of systems for your use case such that it meets the following conditions:
• The difference between the column numbers of any two computers in the set should not exceed a gyen integer k.
• The total sum of connectivity strength between all ordered pairs of systems should be maximized.

NOTE: If a set contains only one system, then the connectivity strength of the group is 0.

Input Format
Locked stub code in the editor reads the following input from stdin and passes it to the function:
The first and second line contains 2 integers n & m, denoting the number of rows and columns in grid s.
Each line i of the n subsequent lines (where 1<=i<=n) contains m space- separated character, where jth character describing s[i][j](where 1<=j<=m).
The last line contains integer k.

Constraints:
• 2<=n,m<=1000
• s[i][j] = {'.', '#'}
• 1<=k<m

Output Format
The function must return a long integer denoting the max connectivity strength sum that can be obtained from any one of these groups. This is printed to stdout by locked stub code in the editor.

Sample Input 0:
3
3
Row 1 - . # .
Row 2 - . # .
Row 3 - # . #
2

Sample Output 0:
13

Explanation 0:
The positions of '#' in the grid are - (1,2), (2,2), (3,1), (3,3) [1-based Indexing] and k=2. The optimal case would be to consider all the systems as maximum and minimum column numbers are 3 and 1 respectively and 3 - 1 = 2. The pairs with the connectivity strength between them in this group are :

1. (1,2), (2,2) -> |2-1|+|2-2| = 1.
2. (1,2), (3,1) -> |3-1|+|1-2| = 3.
3. (1,2), (3,3) -> |3-1|+|3-2| = 3.
4. (2,2), (3,1) -> |2-3|+|2-1| = 2.
5. (2,2), (3,3) -> |3-2|+|3-2| = 2.
6. (3,1), (3,3) -> |3-3|+|3-1| = 2.
   Therefore the sum is 1+3+3+2+2+2 = 13.

Sample Input 1:
3
4
Row 1 - # # . .
Row 2 - . . # .
Row 3 - . # . #
2

Sample Output 1:
14

Explanation 1:
The positions of '#' in the grid are - (1,1), (1,2), (2,3), (3,2), (3,4) [1-based Indexing] and k is 2. Possible groups:

Group1 connectivity strength sum: 1+3+3+2+2+2 = 13

1. (1,1), (1,2) -> |1-1|+|2-1| = 1.
2. (1,1), (2,3) -> |2-1|+|3-1| = 3.
3. (1,1), (3,2) -> |3-1|+|2-1| = 3.
4. (1,2), (2,3) -> |2-1|+|3-2| = 2.
5. (1,2), (3,2) -> |3-1|+|2-2| = 2.
6. (2,3), (3,2) -> |3-2|+|2-3| = 2.

Group2 connectivity strength sum: 2+2+4+2+2+2 = 14

1. (1,2), (2,3) -> |2-1|+|3-2| = 2.
2. (1,2), (3,2) -> |3-1|+|2-2| = 2.
3. (1,2), (3,4) -> |3-1|+|4-2| = 4.
4. (2,3), (3,2) -> |3-2|+|2-3| = 2.
5. (2,3), (3,4) -> |3-2|+|4-3| = 2.
6. (3,2), (3,4) -> |3-2|+|3-4| = 2.

Group2 has maximum connectivity strength sum which is equal to 14.

Sample Input 2:
2
2
Row 1 - . #
Row 2 - # .
1

Sample Output 2:
2

Explanation 2:
The positions of '#' in the grid are - (1,2), (2,1) [1-based Indexing] and k=1. In this case, there will be only one group(the complete array itself). The systems in this group are:

1. (1,2), (2,1) -> |2-1|+|1-2| = 2.
   Therefore the connectivity strength sum is 2.

Q3. Find Number of Platforms - Medium Level - Time Limit (30 mins)

Your friend Alex sends you the position of engine and rear coach of various trains present at a railway station. With the information you receive, can you compute the number of platforms of the railway station, given that the station is working at the top of its capacity, utilizing every available platform?

Function Description:
Complete the computePlatforms function in the editor below. It has the following parameters -
• An integer array named enginePositions representing the position of engine of various trains.
• An integer array named rearCoachPositions representing the position of rear coach of various trains.

You need to return an integer denoting the number of platforms of the railway station.

Constraints:
• 1<= |trains| <=1e5
• 1<= enginePositions <=1e9
• 1<= rearCoachPositions <=1e9

Input Format For Custom Testing:
The first line contains an integer, n, denoting the number of elements in enginePositions.
Each line i of the n subsequent lines (where 0<=i<=n) contains an integer describing enginePositionsi.
The next line contains an integer, denoting the number of elements in rearCoachPositions.
Each line j of the n subsequent lines (where 0<=i<=n) contains an integer describing rearCoachPositionsj.

Sample Input 0:
2
1
2
2
2
3

Sample Output 0:
2

Explanation 0:
There are two trains with
• Engines at 1st and 2nd positions : Rear coaches at 2nd and 3rd positions.
• The trains cannot be at the same platform since in that case the rear coach of first train and engine Of second train clash at position 2.
So, the answer is 2.

Sample Input 1:
2
1
3
2
2
4

Sample Output 1:
1

Explanation 1:
There are two trains with
• Engines at 1st and 3rd positions : Rear coaches at 2nd and 4th positions.
• The trains can be at the same platform with first train from 1-2 positions followed by the next train covering 3-4 positions.
So, the answer is 1.