DhurBaal's blog

By DhurBaal, history, 4 months ago, In English

This is not a programming competition problem. This is a paraphrase of a problem I am trying to solve at my job.

A graph G consists of N nodes where every node has some positive value. Graph G is a connected, dense graph where edges are bi-directional and the number of edges can go up to O(N^2).

To traverse an edge we have to pay a tax equal to the edge's weight. The weight of an edge depends on its two node's values. If the value of two connected nodes is vA and vB, calc_weight(vA, vB) returns the weight of the edge. Please refer to the clarification section to understand why we can not pre-calculate all the weights.

We start with some initial value (let's call it amount). From a predefined source node, our goal is to reach the predefined destination node, with minimum tax paying. Both the source and destination are present in the graph.


At some arbitrary moment, let's assume we are at nodeA and the value of nodeA is valA. And at that moment our amount is amtA. Let's consider nodeB has a bi-directional edge from nodeA. If we want to go nodeA -> nodeB, we first have to calculate the edge's weight.

The catch is when we are at a node, we have to call weightAB = calc_weight(amtA+valA, valB). See how our presence affects the parameters of the function.

we then pay weightAB from amtA and when we reach nodeB our amount becomes amtB = (amtA-weightAB). If we want to go to nodeB -> nodeC, the weight will be calc_weight(amtB+valB, valC).

I can solve this problem using a bitmaskDP. But N can reach up to 2000.

Thanks in advance for any ideas/suggestions. Also if you have seen any problem that closely resembles this, please point me in that direction.

Full text and comments »

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