Hi, I just came along this problem. But couldn't think of any solution hence reaching out to the community.

Problem Description

You live in orange town. There are a lot of markets around that are connected with roads. These markets sell oranges at some prices. The town is not very well developed and they still use carts to transport goods from one place to the other. The roads connect two markets together and have two attributes associated with them. One is the price to go from one market to the other in an empty cart and the other is the tax factor. The tax factor is the number by which the price associated with a road needs to be multiplied, so it can go from one market to the other if you are carrying oranges in your cart. So if a road's original price was 5 coins and tax factor was 6, then in an empty cart it would take 5 coins to travel the road, but if the cart contained oranges, it would cost 5*6=30 coins.

You wonder what would be the cheapest way to buy oranges if you were initially at each market. You can either buy at the market you are at or travel to some other market, buy oranges there, and travel back to the original market

You are given an integer A denoting the number of total markets in orange town, an integer array B denoting the price of purchasing oranges at each market and a 2-D array C containing the information about the roads. First two values denote the market numbers that are bi-directionally connected via a road, 3rd value is the price, while the 4th one is the tax factor.

Find and return the required array. The minimum cost to buy oranges at each market such that the starting and ending point is that market.

Problem Constraints

2 <= A <= 1e5
B.size() == A
1 <= B[i] <= 1e7
1 <= C.size() <= 2e5
1 <= C[0] <= A
1 <= C[1] <= A
1 <= C[2] <= 1e3
1 <= C[3] <= 5

Input Format

The first argument is the integer A. The second argument is the integer array B, and the third argument is the 2-D integer array C.

Output Format

Return an integer array as per the given problem.

Example Input

Input 1:

A = 2 B = [11 1] C = [ [2 1 1 2] ]

Input 2:

A = 2 B = [1 1] C = [ [2 1 2 4] ]

Example Output

Output 1: [4 1] Output 2: [1 1]

Explanation

Explanation 1:

For the first market, you can travel to the second market (1 cost), buy oranges there (1 cost) and return back to the first market (1*2 cost) for a total of 4 cost. For the second market, 1 is already the lowest you can get.

Explanation 2:

For both markets, 1 is the lowest so it is the best answer.

My thoughts

This is very similar to the question asked in Codeagon 2020. If we had no taxes associated then this would have been normal multisource dijkstra with path weights doubled as forward and return journey have same paths. But in this problem we can choose different paths for forward and return journey.

If anyone can help it will be much appreciated.

Question -

We are given 3 strings let say s1,s2,s3. s1 and s2 are of same length. We need to find the number of strings t of length = length of s1 or s2 (both are same) such that s1<=t<=s2 and t does not contain s3 as its substring.

My approach -

Initially, I am trying to precalculate $$$dp[i][j]$$$ as the number of strings of length n-i such that the prefix it has a prefix of length exactly j of string s3. here $$$0<=j<=len(s3)-1$$$, [Beacuse we cannot afford the original entire string as it is not allowed]. Here transitions are $$$dp[i][j]=dp[i+1][j-1]$$$, only for $$$dp[i][0]$$$ we need to place all characters and ensure it is not a suffix of $$$s3$$$.

Then I am doing normal digit dp type of thing, let's say we are at $$$i^th$$$ position in string s1, I am placing character c from s1[i]+1 to upto 'z' at $$$ith$$$ position to make it greater than s and checking for all prefix length x of s3 which can be placed at the $$$(i+1)^th$$$ position so that it do not form the original string $$$s3$$$, the only condition here is string $$$suffix(s1_{i-1},len(s3)-x-1)+char(k)+prefix(s3,x)$$$ must not be equal to $$$s3$$$. Then we can place it and add $$$dp[i+1][x]$$$ to our answer. Also at last if the original string ($$$s1$$$) satisfies this condition then add 1 to answer. Let this function be num.

Similarly do the same thing for $$$s2$$$.

Final answer is $$$num(s1)-num(s2)$$$+(s2 satisfies the condition) But it turns out that I am overcounting sometimes. Can anyone tell me if this method is incorrect or someone can suggest some better method?

It will be highly appreciated

Thanks

Given 2 arrays, array A (containing only 0s and 1s) and the other cost array B of the same size. We needed to convert all the elements of array A to 1 in minimum cost. For every ith element in the array A, converting from 0 to 1 requires B[i] cost but if A[i-1] and A[i+1] are 1 then A[i] can be converted to 1 with 0 cost. Return the minimum possible cost to convert all 0s to 1s. My approach- Isn't this simply $$$dp[i]=min(dp[i-1],dp[i-2])+cost[i]$$$;

Can someone please confirm?