About exponentiation-distance on DAGs
Разница между en1 и en2, 29 символ(ов) изменены
Hello everyone!!!↵

For a long long time, I have been struggling to do this problem: [link to Online Judge](https://onlinejudge.org/external/131/13143.pdf)
 (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!! :)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Junco_dh 2022-03-06 17:20:15 29
en1 Английский Junco_dh 2022-03-05 22:35:35 1366 Initial revision (published)