10 weeks ago

Rohit • 610

Hyderabad

Question 1

A footwear company has N outlets that have unique id from 0 to N-1. The outlets are connected using the bi directional roads directly or via other outlets. There is a cost of stock transfer between the directly connected outlets. Initially, the warehouses were established at K outlets. As the demand of the products increases unexpectedly during the festival seasons, so the stocks need to be transferred quickly among the warehouses. The company has decided to provide the trucks to transport the stock from one warehouse to another but it puts extra overhead on the company. The company has decided to start the truck between the closest warehouses initially. The company wants to find the minimum stock transfer cost between any two warehouses which will be incurred on the company.

Write an algorithm to find the minimum stock transfer cost between any two warehouses which will be overhead on the company.

Input

The first line of the input consists of two space-separated integers - numOutlets and numWarehouses, representing the number of outlets (N) and the number of warehouses(K).

The next line consists of K space separated integers warehouse D[O], warehouse D[1]..., warehouse/D[K-1], representing the ids where the warehouses were established initially. The next line consists of an integer - directConnection, representing the number of direct connections among outlets (X).

The next X lines consists of three space-separated integers - A, B, C representing the id of the directly connected outlets (A and B) and the cost of stock transport C between outlet A and B.

Output

Print an integer representing the minimum stock transfer cost between any two warehouses.

Constraints

• Os <= numWarehouses <= numOutlets <= 500
• 1 <= cost[i][2] <= 1300 (i.e., the cost of stock transport between two warehouses is between 1 and 1300)
• 0 <= i < numOutlets

Example

Input

6  3
1  3  4
7
0  1  10
0  4  7
1  3  12
3  5  3
1  5  10
4  2  2
2  5  3

Output

8

Explanation: The warehouses have ids 1, 3, 4. The cost of stock transport between warehouses id 1 and 3 is 12, between warehouses id 1 and 4 is 17, and between warehouses id 3 and 4 is 7. So, the minimum cost of stock transport is 8 between warehouse id 3 and 4. So, the output is 8.

Question 2

The Health Ministry of Torris county has decided to set up medical centers for the benefit of its citizens. The Ministry selects N different cities in the county in which to establish a medical center. Each city is identified by a city ID ranging from 0 to N 1. Multiple medical centers are needed in different cities according to requirement. Each day a medical center will be set up in one of the selected cities. On any two consecutive days the chosen city must be different.

Write an algorithm to determine the maximum number of medical centers that will be set up in the county covering the maximum number of locations.

Input

The first line of the input consists of an integer - numCity representing the number of cities selected for a medical center (N).

The next line consists of N space separated integers - loc1, loc2,.. locN representing the number of locations to set up a medical centers in a city.

Output

Print an integer representing the maximum number of medical centers that will be set up in the county covering the maximum number of locations.

Constraints

• 1 <= numCity <= 10^4
• 1 <=locl <= 10^5
• ∑ locl <= 10^5
• 1 <= l <= N

Example

Input

3
11  4  5

Output

19

Explanation: The first, second and third cities are selected with locations 11, 4 and 5, respectively.

The locations of different cities are selected on successive days in a sequence:

1st, 2nd, 1st, 3rd, 1st, 2nd, 1st, 3rd,1st, 2nd, 1st, 3rd, 1st, 2nd, 1st, 3rd, 1st, 3rd, 1st

So, the maximum number of medical centers that may be set up in the county is 19.

Question 3

The Cytes Lottery is the biggest lottery in the world. On each ticket, there is a string of a-z letters. The company produces a draw string S. A person wins if his/her ticket string is a special substring of the draw string. A special substring is a substring which can be formed by ignoring at most k characters from drawstring. For example, if draw string = 'xyzabc' and tickets are [ac zb yhja] with K=1 then the winning tickets will be 2 i.e ac (won by ignoring 'b' in drawstring) and zb (won by ignoring 'a' in drawstring).

Now, some people change their ticket strings in order to win the lottery. To avoid any kind of suspicion, they can make the following changes in their strings:

1. They can change character 'o' to character 'a' and vice versa.
2. They can change character 't' to character 'l' and vice versa.
3. They can erase a character from anywhere in the string.

Note that they can ignore at most 'K characters from the draw string to get a match with the ticket string. Write an algorithm to find the number of people who win the lottery (either honestly or by cheating).

Input

The first line of the input consists of an integer - numTickets, representing the number of tickets (N).

The second line consists of N space separated strings - tickets1, tickets2,........, ticketsN, representing the tickets.

The third line consists of a string - drawstring, representing the draw string (S).

The last line consists of an integer - tolerance, representing the maximum number of characters that can be deleted from the drawString(K).

Output

Print an integer representing the number of winning tickets (either fairly or by cheating).

Constraints

• 0 <= numTickets <= 1000
• 0 <= length of drawString <= 200
• O <= length of tickets <= 200
• 0 <= tolerance <= 1000

Note: The drawstring contains lowercase English alphabets.

Example

Input:

abcde aoc actld 
aabacd 
1

Output

2

Explanation:

For the first ticket 'abcde' - delete 'e' from the tickets string and delete 'a' from drawstring (aabcd). So, the new first ticket 'abcd' is a substring of the new drawString

For the second ticket 'aoc' - change 'o' to 'a' so that the new string will be 'aac' which is a substring of the drawString

For the third ticket 'actld' - by applying any operation on the tickets and on the drawstring we cannot get any substring of the drawString.

Therefore, there are only 2 winning tickets.

2.1 years ago

Gurankit Pal Singh 160

Solution for question 3

This problem can be solved using dp.

The states of dp will be i, j, isDeletedOnce

1. i represents the current index of the drawString
2. j represents the current index of the ticket
3. isDeletedOnce is boolean, and represents if the character is deleted once in the ticket.

dp[i][j][isDeletedOnce] will store the minimum characters needed to be removed from the drawString. We will check for every i from 0 to drawString.length()-1, that if dp[i][j][isDeletedOnce] < = tolerance, then it is possible to win lottery from that ticket.

Pseudo Code:

solve(i, j, isDeletedOnce, drawString, ticket)
    if j == ticket.length
        return 0

    if i==drawString.length
        if isDeletedOnce==0 and j==ticket.length-1
            return 0
        else
            return inf

    ans = inf

    if drawString[i] and ticket[j] are equivalent
        ans = min(ans, solve(i+1, j+1, isDeletedOnce, drawString, ticket))

    if isDeletedOnce==0
        ans = min(ans, solve(i, j+1, 1, drawString, ticket)

    ans = min(ans, 1+solve(i+1, j, isDeletedOnce, drawString, ticket))

    return ans


isSpecialSubstring(drawString, ticket, tolerance)
    for i from 0 to drawString.size
        if solve(i, 0, 0, drawString, ticket) <= tolerance
            return true

    return false

2.1 years ago

Ujjwal Rana 50

Problem 1

Approach :-

• We are given a bidirected graph and we have to find the find the minimum distance between any 2 of the warehouses.
• Floyd Warshall is an algorithm that helps us find shortest distance between every pair of vertex in O(V^3) complexity.
• Hence we will choose Floyd warshall here in order to find the shortest distance between any pair.
• Hence we can use Floyd Warshall algorithm to find all pair shortest path in O(V^3) to find out the answer.

PsuedoCode

cin>>n>>k;
vector<int>ware(k);
for(int i(0);i<k;++i){cin>>ware[i];}
cin>>x;
for(int i(0);i<x;++i){int a,b,c; cin>>a>>b>>c; adj[a][b]=c;}
 for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);  // d-> distance matrix (intially adjacent)
    }
}
}
return minimum_dist;

8 months ago

Akshay Sharma 990

Chandigarh

Question 2

Overview

We have to set up the medical centre by covering the maximum location and multiple centres can be needed in a single city and we are given the condition that on two consecutive days we can't visit the same city.

Approach/intuition

• If we analyse this test case with the given example then we are able to set medical centres on almost 19 locations by starting with the first city which has the maximum need for a centre and also ends with that but if we change the test case to 11 5 4 1 than we are able to visit all the cities as the sum of others elements is one less than maximum.
• So the solution always exits as sum_of_all_element if The difference between Maximum_Element-Other_Element<=1 || Sum_of_other_element >Maximum_Element.
• If none of the conditions satisfies then the sum of other elements excluding maximum is less than the maximum_element then answer will going to be Sum_Of_other_Element*2+1
• We can easily calculate the sum using for loop
• Time Complexity: O(N)

Pseudo Code

for (int i = 0; i < n; i++)
{
    cin >> a[i];
    mx = max(a[i], mx);
    sum += a[i];
}
sum -= mx;
if (sum >= mx || sum - mx == 1)
{
    cout << sum + mx << "\n";
}
else
{
    cout << (sum * 2) + 1 << "\n";
}