I_dont_have_girlfriend's blog

Problem TAX (Algorithmic Engagements 2012)
By I_dont_have_girlfriend, 11 years ago, In English

Hello everybody,

I'm trying to solve this problem. But I don't have any ideas. Can someone help me, pls ?

Thanks!

UPD: I solved it :-)

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, congratulations for solve this problem, I've already blogged here about this problem, but my doubts wasn't full cleared, could you explain your ideas to me ?

My Post

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    Hi, This problem can be solved using Dijkstra. Let's take a look at group of 3 continous vertices (u_1 -> u -> u_2), the tax equals max(Cost[u_1][u], Cost[u][u_2]).

    So with any vertices, I have COST is the minimal amount of tax we have to pay, LAST is the tax of the last edge that we enter the town. Suppose I'm at the two [u] I update the result to the town [v] which is connected with [u] by a road (There are 2 cases: Cost[u][v] > LASTs and Cost[u][v] < LAST).

    Beause the tax depends on vertices, it's not hard to understand that if d[u] is the minimal amount of tax to go to the town [u] and we haven't determined d[v], certainly, d[v] = d[u] + tax[v]. So after update [u][v], we can remove the road that connects [u] and [v].

    My English isn't good, so I hope you can understand it :-)

    My implementation http://ideone.com/eKdUIT

    → Reply