ESO207: Data Structures and Algorithms Programming Assignment 2 Solved

Description

 

 

Question 1  Another minimum sum

Description:

Given an array A consisting of N elements, find the smallest sum of contiguous elements that is strictly greater than K.

Input:

First line will contain a single number N, denoting the number of elements in the array A.

Second line will contain the N elements of the array. Third line will contain the integer K.

Output:

Output a single integer S, the minimum sum of contiguous elements that is strictly greater than K. If no sum exists that is strictly greater K, then output −1.

Constraints:

1 ≤ N ≤ 10⁵

− 10⁶ ≤ A[i] ≤ 10⁶ 1 ≤ k ≤ 10⁶

Example:

Sample Input:

5

1      -5     3     -7     8

3

Sample Output: 4

Explanation:

The contiguous sequence 3     -7       8 has the smallest sum strictly greater 3 i.e. 4.

Note: the sum of the sequence -5      3      -7 is -9 but its not strictly greater 3

Question 2 Finding products

Description:

Given two sorted (in non decreasing order) arrays of positive integers A and B having sizes M and N respectively, and an integer K, find the Kth smallest product A[i] · B[j], where 0 ≤ i ≤ M − 1 and

• ≤ j ≤ N − 1.

Input:

First line contains two integers, M and N, denoting the sizes of the two arrays A and B respectively.

Next line contains M positive integers in non decreasing order, the elements of A

Next line contains N positive integers in non decreasing order, the elements of B

Last line contains the integer K

Output:

Output a single integer P that is the Kth smallest product A[i] · B[j]

Constraints:

• ≤ N,M ≤ 100000

1 ≤ A[i],B[i] ≤ 10000

1 ≤ k ≤ N ∗ M

Example:

Sample Input:

3    4

• 3 4
• 4 6               8

5

Sample Output: 8

Explanation:

The products A[i] · B[j] after sorting in non-decreasing order are as follows

2    4    6    6    8     8    12    16    18    24    24    32

The 5th smallest element in the above list is 8.

Question 3 (30 points) Greater to the left

Description:

Given an array A of N elements, Find for each element A[i], how many elements A[j] are greater than or equal to A[i] such that j<i

Input:

First line contains an integer N, the number of elements in the array A. Second line contains N elements, the contents of the array A.

Output:

Print N elements, where the ith element represents the number of elements A[j] greater than or equal to A[i]

Constraints:

1 ≤ N ≤ 500000 1 ≤ A[i] ≤ 100000

Example:

Sample Input:

4

5    4    2    5

Sample Output:

0 1 2 1

Explanation:

There are 0 elements ≥ 5 to its left

There is 1 element ≥ 4 to its left i.e 5

There are 2 elements ≥ 2 to its left i.e. 5 and 4

There is 1 element ≥ 5 to its left i.e. 5

Question 4 Sonic and coins

Description:

Sonic is busy collecting coins. He is traveling through a binary search tree having N nodes, where every node in the tree has one coin. When he travels from the node p to q he will collect all the coins in the path from p to q (including the coins in the nodes p and q).

Given K queries, where each query will have two numbers, p and q. Print one number, denoting the total number of coins Sonic will collect when traveling from the node p to q.

Input:

First line will contain N and K, denoting the number of nodes in the tree and number of queries respectively.

Next line will contain N integers, denoting the pre-order traversal of the nodes of the tree (all N numbers will be unique).

Next K lines will denote two integers p,q each, denoting the start and end node of the path that sonic will travel.

Output:

Print K numbers, where each number represents the number of coins Sonic will collect.

 

Constraints:

1 ≤ N ≤ 100000 1 ≤ K ≤ 100000

Example:

Sample Input:

5      2

3      1    0     2     4

2      3

0      4

Sample Output:

3

4

Explanation:

• Sonic’s first run, collects 3 coins.

 

• Sonic’s second run, collects 4 coins.