Junco_dh's blog

About exponentiation-distance on DAGs
By Junco_dh, history, 3 years ago, In English

Hello everyone!!!

For a long long time, I have been struggling to do this problem: link to Online Judge (13143-Dijkstractions). I could not find any information or code on the internet.

In short, the problem is: given a DAG (Directed Acyclic Graph) and two nodes u, v, find the longest path from u to v, but with exponentiation-distance, i.e. if you have two edges a and b, the distance is not a+b but a^b (^ of exponentiation).

If there are multiple answers, then you have to return the one with the lowest lexicographical order.

What I have thought:

1- Maybe the part of returning the lowest lexicographical order path is not important, and you get it easy once you have the longest path.

2- I know how to solve this problem if it had sum-distance: Using tree (DAG) DP.

3- I know how to solve this problem if it had multiplication-distance: Changing the value of edges to log(edges) and using sum-distance. This is because if the longest path has 3 edges a1, a2, a3, a1*a2*a3 = ans => log(a1) + log(a2) + log(a3) = log(ans), and the path will be the longest in the new problem.

4- I have thought about how could I simplify the exponentiation-distance problem to multiplication-distance problem, similar to the 2-3 parts.

Can anyone provide a hint or a solution?

Thank you!! :)

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

»
3 years ago, # |
  Vote: I like it -36 Vote: I do not like it
$$$(a^b)^c = a^{bc}$$$

More generally,

$$$(((a^{k_1})^{k_2})^{\ldots}) = a^{k_1k_2\ldots}$$$

so I think you could fix the first edge and find the shortest path by product that way.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Junco_dh (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I think you can approximate the $$$n$$$th log of a power tower pretty simply. Basically if your tower $$$a^T$$$ is large (much larger than $$$3$$$), then $$$\log(a^T p + q) \approx T \log a + \log p + \frac{q}{a^T p} \approx T \log a + \log p$$$, where the constant never grows significantly larger than $$$\log\log 10^6 < 3$$$. You can probably turn this into a comparator by picking a reasonable $$$n$$$ for two towers, taking the $$$n$$$th log which is basically the power tower after $$$n$$$ terms (so this should be large but computable) times the $$$\log$$$ of the $$$n-1$$$ th term plus the $$$\log\log$$$ of the $$$n-2$$$th term, and comparing these. This fails when the two sequences are equal past the $$$n-2$$$th term, but if this fails for all reasonable $$$n$$$ then the towers are equal at the top and the first place where they differ (from the top) should determine which is larger (just let $$$n = $$$ where they differ $$$ + 1$$$ in the expression).

Might not work, but intuitively power towers shouldn't land very close to each other in value. I'll code this up soon probably and update.

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

    adding little more expansion to understand the approximation.

    $$$ log(a^{T}p + q) = log(a^{T}p( 1 + \frac{q}{a^{T}p})) = log(a^Tp) + log(1 + \frac{q}{a^{T}p}) $$$

    now

    $$$ 1 + \frac{q}{a^{T}p} ≈ 1 => log(1 + \frac{q}{a^{T}p}) = 0 $$$

    or

    $$$ log(1 + h) = h ,{h \to 0} $$$
    → Reply