ESO207- Programming Assignment 3 Solved

Question 1                              BST to Greater Tree

Given a binary search tree T, the greater tree T0 corresponding to T is defined as follows:

-   the tree structure of T0 is the same as the tree structure of T.

-   the value of a node v in T0 is the sum of all the keys greater than or equal to the value of the key in the node v in T.

For example consider a BST T and its corresponding greater tree T0.

 

                                       (a) binary search tree T                                             (b) corresponding greater tree T0

Given the preorder traversal of a BST T, you need to output the preorder traversal of the corresponding greater tree T0.

Input:

First line will contain a single number N, denoting the number of nodes in the BST.

Next line will contain N integers, denoting the preorder traversal of the BST (all N numbers will be unique).

Output:

Output the preorder traversal of the corresponding greater tree.

Constraints:

0     ≤ N ≤ 105

0 ≤ key value at a node ≤ 105

Example:

Sample Input:

9

        4         1 0 2 3 6 5 7 8

Sample Output:

       30        36 36 35 33 21 26 15 8

Question 2                             Covid spread

Moni is the head nurse at city hospital which has wards arranged in a rectangular grid shape with R rows and C columns.

You are given a R×C matrix Mat where each cell Mat can have values 0, 1 or 2 which has the following meaning:

0  : Empty ward

1  : Wards without infected patients

2  : Wards with infected patients

An infected patient at ward (i,j) can infect other uninfected patients at wards (i − 1,j), (i + 1,j), (i,j − 1) and (i,j + 1) (i.e. up, down, left and right) in one unit of time. Help Moni determine the minimum units of time after which there won’t remain any uninfected patient i.e all patients would be infected. If all patients are not infected after infinite units of time then simply return −1.

Input:

First line contains two integers R and C, the number of rows and columns. Next R lines contain the 2-D Matrix Mat with C entries per line.

Output:

Print the minimum units of time in which all patients will be infected or −1 if it is impossible.

Constraints:

1     ≤ R,C ≤ 1000 0 ≤ Mat(i,j) ≤ 2

Example:

Sample Input:

        3    5

2     1               0             2             1

        1    0    1    2    1

        1    0    0    2    1

Sample Output: 2

Explanation:

Patients at positions {0,0}, {0, 3}, {1, 3} and {2, 3} will infect patient at {0, 1},{1, 0},{0, 4}, {1, 2}, {1, 4}, {2, 4} during 1st unit time.

And, during 2nd unit time, patient at {1, 0} will get infected and will infect patient at {2, 0}. Hence, total 2 unit of time is required to infect all patients.

Question 3                             Number of Islands

In a m×n 2D binary grid A, a cell with 1 represents land and a cell with 0 represents water. An island is a connected subset of 1’s surrounded by all 0’s. Two 1’s are said to be connected if they are horizontally or vertically adjacent.

Given such a grid find the total number of islands.

Input:

First line contains two integers m and n, the number of rows and columns. Next m lines contain the 2-D Matrix A with n entries per line.

Output:

Print single integer representing total number of islands present in the 2D grid A.

Constraints:

1 ≤ m,n ≤ 300 0 ≤ grid value ≤ 1 Example:

Sample Input:

        4    5

        1    1    0    0    0

        1    1    0    0    0

        0    0    1    0    0

0     0               0             1             1

Sample Output: 3

Explanation:

 

(a) Different blocks represent islands

Question 4                             Brother from different roots

You are given the preorder traversal of two BSTs T1 and T2 containing n1 and n2 nodes respectively, and a number k. Assume all values of T1 and T2 are distinct within that tree. The problem is to count the number of pairs of nodes such that the first node is from T1 an the second node is from T2, and the value of the sum of these two nodes equals k.

Input:

-   First line will contain a single number n1, denoting the number of nodes in the T1.

-   Second line will contain n1 integers, denoting the preorder traversal of T1 (all n1 numbers are unique).

-   Third line will contain a single number n2, denoting the number of nodes in the T2.

-   Fourth line will contain n2 integers, denoting the preorder traversal of T2 (all n2 numbers are unique).

-   Next line will contain a single integer k.

Output:

Output the number of pairs from two BSTs whose sum is equal to a given value k.

Constraints:

1     ≤ n1,n2 ≤ 5000

−109 ≤ Node.Value ≤ 109 −109 ≤ k ≤ 109

Example:

Sample Input:

3

2     1 4

3

        1    0 3

5

Sample Output: 2

Explanation:

If we see in below figure there are total 2 pairs with sum 5 i.e. {2,3} and {4,1}

 

(a)