Блог пользователя just_for_one

Interesting Problem involving dijkstra
Автор just_for_one, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I don't know if my aproach is correct but:

Step 0: Initialy set the minimum for each market to its price for oranges(example 1: min={11, 1})

Step 1: Take the market with the best price so far(can be stored with a priority_queue or a heap) and try to update its neighbours(min={min[1]+(factor+1)*road[0][0].tax(see code), 1}={4, 1}).

Step 2: Repeat Step 1.

Code in C++

Note: The code was not tested so there could be bugs, but you should be able to work with it. Also, it is very unoptimised.

Edit: Removed a mistake in the code

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    This will not work I guess. That's where the problem begins, you are assuming same forward and backward path, but that might not be the case. Your method would have worked if tax=1.

    → Ответить
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      One interesting thing is that this approach gives a reasonably good solution. For every node it actually finds a solution which is not worse than $$$\frac{3}{2} opt$$$, where $$$opt$$$ is the optimal solution for this node. To show this, let's consider an optimal solution for node $$$u$$$. It will walk in a path towards some market, buy an orange, and walk back. Let's call the cost for going towards the market $$$opt_1$$$ and the taxed trip back $$$opt_2$$$, and the cost of buying the orange $$$opt_3$$$. We know our solution will consider all solutions where the path goes forward and backward along the same path. Let's call the cost of our solution $$$naive$$$.

      Then $$$naive \leq (1+5) \cdot opt_1 + opt_3$$$ and $$$naive \leq (1+1) opt_2 + opt_3$$$.

      You can show these inequalities by considering the constraint on the tax factor and seeing that the naive solution can always go back and forth over either the $$$opt_1$$$ or $$$opt_2$$$ path.

      Now we can add up this inequalities, after multiplying the second inequality by 3.

      We get: $$$4 \cdot naive \leq 6 \cdot opt_1 + 6 \cdot opt_2 + 4 \cdot opt_3 < 6 \cdot opt \implies naive < \frac{3}{2} opt$$$

      I still have no idea how to solve the problem exactly though. Of course a quadratic (with log from dijkstra) solution is possible, but that's really slow.

      → Ответить
»
3 года назад, # |
← Rev. 3   Проголосовать: нравится -13 Проголосовать: не нравится

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

If you haven't got a solution, you haven't got a problem. One can invent a dozen of problems without solutions.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Excuse me, First of all thanks for the valuable comment. Secondly you are acting like I have invented the complete problem myself after carefully selecting the constraints, test cases, even a beautiful story XD. If I would have invented the problem it is better to contribute to some codeforces or codechef round rather than posting here. And does the wordings of the problem really suggest I have created the story and everything just to post here.

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

just_for_one, did you find any solution or approach?

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

@just_for_one did you find the solution?

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится 
## taking input from txt file, you can replace the code with input()

with open('input.txt') as f:
    lines = f.readlines()

from heapq import *

class solve():
    def __init__(self,a,b,c):
        self.a = a
        self.b = b
        self.c = c
        self.ans = [float("inf")]*a

        self.m = {i:[] for i in range(a)}
        self.cost = {}

        for a,b,c,t in c:
            self.m[a].append([b,c,t])
            self.m[b].append([a,c,t])
    #dijkstra algo
    def dk(self,s):
        pq = [[0,s]]
        visited = set()
        self.ans[s] = min(self.ans[s],self.b[s])

        while pq:
            w,cur = heappop(pq)
            if cur in visited:
                continue
            visited.add(cur)
            for node,c,t in self.m[cur]:
                cost = (w+c)*(1+t) + self.b[node]
                print(cost)
                self.ans[cur] = min(cost,self.ans[cur])
                heappush(pq,[w+c,node])


    def solution(self):
        for i in range(self.a):
            # applying for each node, not very optimized
            self.dk(i)
        return self.ans

for _ in range(1):
    a = int(lines[0])
    b = list(map(int,lines[1].split()))
    c = []
    for i in range(a-1):
        row = list(map(int,lines[2].split()))
        c.append(row)
    obj = solve(a,b,c)
    print(obj.solution())
→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    you are doing dijkstra for each node considering you are using new visited array for each each node to it looks like $$$n^2logn$$$ solution might not work for the constraint given.

    → Ответить