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!! :)
More generally,
so I think you could fix the first edge and find the shortest path by product that way.
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
Auto comment: topic has been updated by Junco_dh (previous revision, new revision, compare).
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.
adding little more expansion to understand the approximation.
now
or