Question: Zepto, Recently Asked On-Campus Questions in IITs, October 2022
0
Entering edit mode

Question 1

A Sum of Coins

You have N coins whose amount ranges from 0 to N-1 respectively. Your friends wants to take K coins out of your coins. You can only give the coins if the set of K coins is useful. A set of coins is useful if the sum of the coins is divisible by a given integer M. Task Determine the number of ways in which your friend can get K coins. Since the answer can be large, print the answer module 10^9 + 7.

Example

Assumptions

• K = 1
• N = 3
• M = 1

Approach

You can take coins 0, 1, and 2. All are divisible by M = 1. Therefore the answer is 3.

Function description

Complete the solve function provided in the editor. This function takes the following 3 parameters and returns the answer:

• k: Represents the amount of coin your friend wants
• m: Represents the Integer value
• n: Represents the number of coins

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 3 space separated Integers N, K, and M.

Output format

Constraints

1 <= N <= 10^3

1 <= K <= 10^2

1 <= M <= 10^3

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.

Sample input

``````4 2 2
``````

Sample output

``````2
``````

Explanation

There are 2 ways :

[1, 3]

[2, 4]

Question 2

Minimize Path Value

Given a graph G with N nodes and M edges (edges are bi-directional). Every node is assigned a value A[i]. We define a value of path as :

A path consists of a sequence of nodes starting with start node S and end node E.

S -> u1 -> ..... -> E where u1, u2, ... are nodes in G.

Value of path = Maximum of (absolute difference between values of adjacent nodes in Path).

Given a start node S and end node E, find the minimum possible "value of path" which starts with node S and ends with node E.

Example

If N = 5, M = 6, S = 1, E = 4 and A = [3,12,4,7,13].

There are 4 simple paths from node 1 to node 4.

• 1 - 2 - 4: Value of path = Max(12 - 3, 12 - 7) = 9
• 1 - 3 - 4: Value of path = Max(4 - 3, 7 - 4) = 3
• 1 - 3 - 5 - 2 - 4: Value of path = 9 (because of edge 3 - 5)
• 1 - 2 - 5 - 3 - 4: Value of path = 9 (because of edge 3 - 5)

Hence, the minimum possible value of the path is 3.

Function Description

Complete the pathValue function provided in the editor. This function takes the following 6 parameters and returns minimum possible value of path.

• N : Represents the number of nodes in graph G.
• M : Represents the number of edges in graph G.
• S : Represents the number of nodes in graph G.
• E : Represents the end node of path.
• edge : Represents the edges present in graph G.
• A : Represents the value of nodes in graph G.

Input :

1. First line contains two space-separated integers N M
2. Second line contains two space-separated integers S E
3. Next M lines contain two space-separated integers u v, denoting an edge between node u and v
4. Next line contains N space-separated integers denoting values of nodes.

Constraints :

1 <= N <= 10^5

N - 1 <= M <= 10^6

1 <= A[i] <= 10^6

Output :

Minimum possible "value of path" between node S and E

NOTE :

Use fast I/O.

Sample input

``````5 7
2 5
1 2
2 3
3 4
4 5
1 3
1 4
1 5
20 23 21 45 21
``````

Sample output

``````2
``````

Explanation

Path : 2 -> 3 -> 1 -> 5 will give the minimum possible path value = 2.

Remember there can be multiple paths that give the same minimum path value.

4
Entering edit mode

Q2)

Solution for 2

• First of all add weights to edges as their difference of absolute values of nodes, for example if there is an edge (u-v) then add weight to this edge as abs(value[u]-value[v]).
• Now you have constructed the weighted graph , the question is to find the minimum value of the maximum edge weight of path from S to E
• There are 2 ways to approach the problem
• Binary Search
• Since it is the min-max problem , so first intuition comes to mind is Binary Search. So if F(W) represent is it possible to reach from node S to node E if considering only those edges which have weights atmost W
• It can be shown that F(W) is monotonic function.
• Now the question arises how to find the value of F(W). It is quite straight forward , just select edges with weights atmost W, and check whether there exists a path from S to E which can be done either by doing DFS/BFS from S and check whether E visited or not
• Djisktra's Algorithm
• Since we need to minimize the maximum edge's weight, if we are having various valid choices of path then greedily it will be always better to pick the edge with minimum weight.
• Let's suppose if we come to a node X with neighbours {n1,n2,,} with maximum edge weight as mx[X], then check will it update the neighbours's mx , like mx[n1]>max(mx[X],edge_weight(X,n1)), then we got a much better option to minimize mx[n1].
1
Entering edit mode

Solution for Q1

Define dp[idx][sz][rem] = number of subsets of {0, .. , idx} of size "sz" whose sum leaves a remainder of "rem" when divided with M.