### Junco_dh's blog

By Junco_dh, history, 2 years ago,

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!! :)

• +5

 » 2 years ago, # |   -36 $(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.
•  » » 2 years ago, # ^ |   +42 In the power towers, the brackets are the other way around, so $a^{(b^c)}$. So your trick doesn't work. This problems boils down to comparing power towers. I think this is a really difficult problem. Petr even questions if this problem is solvable at all
 » 2 years ago, # |   0 Auto comment: topic has been updated by Junco_dh (previous revision, new revision, compare).
 » 2 years ago, # | ← Rev. 3 →   0 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.
•  » » 2 years ago, # ^ | ← Rev. 5 →   +1 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}$