10 weeks ago

Rohit • 610

Hyderabad

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

Print the answer.

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]

A sum of coins

You have N coins whose amount ranges from 0 to N-1 respectively.

Your friend 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 modulo 109 + 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 return the answer

 

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

• mr. Represents the integer value

• r. Represents the number of coins

Input format

Note: This is the input format that you must use to provide custom

input (avallable above the Compile and Test button).

• The first line contains 3 space separated integers N. K, and M.

Output format

Print the answer.

Constraints

15≤  N ≤ 10^3

15 ≤ K ≤ 10^2

15 ≤  M <10^3

Code snippets (also called starter code/boilerplate code)

This question has code snippets from C , CPP, Java and Python

Sample input                             Sample output

4 2 2                                                2

Explanation

There are 2 ways

(1, 3) (2, 4)

 The following test cases are the actual test cases of this question

that may be used to evaluate your submission

Sample input 1                    Sample output 1

100 10 5                                61867206

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.

8 months ago

Shikhar Mehrotra 480

Chennai

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].

13 months ago

Vaibhav Agarwal • 30

Editorial for Question 1:

1. We can use dp to solve this problem.

   • dp[i][j][k] = number of ways to choose j elements from 0 to i such that sum mod m(given) is k.
   • our final answer would bedp[n-1][k][0].

2. Now , to calculate dp[i][j][k] we can either choose i or not choose i:

   • not choose i: dp[i][j][k] = dp[i-1][j][k]
   • choose i: dp[i][j][k] = dp[i-1][j-1][(k-i%m+m)%m], here (k-i%m+m)%m is the remainder of k-i when divided by m, we add m to make sure it is positive
   • we add up both cases and take modulo

2.1 years ago

koooo • 10

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.

Our answer will be dp[N-1][K][M].

How do we construct the DP?

• Lets say we need to calculate dp[idx][sz][rem]. There are two cases:
• Either you don't take the value "idx" as a part of your subset: dp[idx][sz][rem] += dp[idx - 1][sz][rem]
• Or you take it into your subset: dp[idx][sz][rem] += dp[idx-1][sz-1][(rem - idx + m) % m]

15 months ago

Systumm • 200

Mumbai

q2 link is not working its rendering all problems not q2