Skip to main content
Bounty Ended with 50 reputation awarded by CommunityBot
Fixed typos
Source Link
John L.
  • 39.1k
  • 4
  • 34
  • 91

You've the right idea. Yuval's comment provides the missing trick. Here is the algorithm that connects the dots.

  1. For each pipe $i$ with $A_i$ and $B_i$ from vertex $u$ to vertex $v$, we add an edge of weight $\log(B_i/A_i)$ from $u$ to $v$. TheLet $G$ be the graph with the given $n$ vertices with theand $m$ new edges just added. It is the new graph you were thinking of. Name it $G$.
  2. Apply Bellman–Ford algorithm with $s$ as the source to detect whether there is a negative-weight cycle in $G$ reachable from $s$.
  3. If there is, it is possible for $A$ to lead $B$ through a sequence of pipes starting from $s$ so that $A$ gets infinitely larger than $B$. Otherwise, no.

The idea is that the sum of weights along a walk in $G$ corresponds to the logarithm of the change of ratios of $B$'s height to $A$'s height when $A$ and $B$ have walked that walk. A negative-weight cycle means the ratio of $B$'height's height to $A$'s height becomes smaller when both $A$ and $B$ have walked that cycle once.

The algorithm runs in $O(mn)$ time.

You've the right idea. Yuval's comment provides the missing trick. Here is the algorithm that connects the dots.

  1. For each pipe $i$ with $A_i$ and $B_i$ from vertex $u$ to vertex $v$, we add an edge of weight $\log(B_i/A_i)$ from $u$ to $v$. The given $n$ vertices with the $m$ new edges is the new graph you were thinking of. Name it $G$.
  2. Apply Bellman–Ford algorithm with $s$ as the source to detect whether there is a negative-weight cycle in $G$ reachable from $s$.
  3. If there is, it is possible for $A$ to lead $B$ through a sequence of pipes starting from $s$ so that $A$ gets infinitely larger than $B$. Otherwise, no.

The idea is that the sum of weights along a walk in $G$ corresponds to the logarithm of the change of ratios of $B$'s height to $A$'s height when $A$ and $B$ have walked that walk. A negative-weight cycle means the ratio of $B$'height to $A$'s height becomes smaller when both $A$ and $B$ have walked that cycle once.

The algorithm runs in $O(mn)$ time.

You've the right idea. Yuval's comment provides the missing trick. Here is the algorithm that connects the dots.

  1. For each pipe $i$ with $A_i$ and $B_i$ from vertex $u$ to vertex $v$, we add an edge of weight $\log(B_i/A_i)$ from $u$ to $v$. Let $G$ be the graph with the given $n$ vertices and $m$ edges just added. It is the graph you were thinking of.
  2. Apply Bellman–Ford algorithm with $s$ as the source to detect whether there is a negative-weight cycle in $G$ reachable from $s$.
  3. If there is, it is possible for $A$ to lead $B$ through a sequence of pipes starting from $s$ so that $A$ gets infinitely larger than $B$. Otherwise, no.

The idea is that the sum of weights along a walk in $G$ corresponds to the logarithm of the change of ratios of $B$'s height to $A$'s height when $A$ and $B$ have walked that walk. A negative-weight cycle means the ratio of $B$'s height to $A$'s height becomes smaller when $A$ and $B$ have walked that cycle once.

The algorithm runs in $O(mn)$ time.

Fixed typos.
Source Link
John L.
  • 39.1k
  • 4
  • 34
  • 91

You've the right idea. Yuval's comment provides the missing trick. Here is the algorithm that connects the dots.

  1. For each pipe $i$ with $A_i$ and $B_i$ from vertex $u$ to vertex $v$, we add an edge of weight $\log(B_i/A_i)$ from $u$ to $v$. The given $n$ vertices with the $m$ new edges is the new graph you were thinking of. Name it $G$.
  2. Apply Bellman–Ford algorithm with $s$ as the source to detect whether there is a negative-weight cycle in $G$ reachable from $s$.
  3. If yesthere is, it is possible for $A$ to lead $B$ through a sequence of pipes starting from $s$ so that $A$ gets infinitely larger than $B$. Otherwise, no.

The idea is that the sum of weights along a pathwalk in $G$ corresponds to the logarithm of the change of ratios ofof $B$'s height to $A$'s height afterwhen $A$ and $B$ followshave walked that walk. A negative-weight cycle means the same pathratio of $B$'height to $A$'s height becomes smaller when both $A$ and $B$ have walked that cycle once.

The algorithm runs in $O(mn)$ time.

You've the right idea. Yuval's comment provides the missing trick. Here is the algorithm that connects the dots.

  1. For each pipe $i$ with $A_i$ and $B_i$ from vertex $u$ to vertex $v$, we add an edge of weight $\log(B_i/A_i)$ from $u$ to $v$. The given $n$ vertices with the $m$ new edges is the new graph you were thinking of. Name it $G$.
  2. Apply Bellman–Ford algorithm with $s$ as the source to detect whether there is a negative cycle in $G$ reachable from $s$.
  3. If yes, it is possible for $A$ to lead $B$ through a sequence of pipes so that $A$ gets infinitely larger than $B$. Otherwise, no.

The idea is that the sum of weights along a path in $G$ corresponds to the logarithm of the change of ratios of $B$'s height to $A$'s height after $A$ and $B$ follows the same path.

You've the right idea. Yuval's comment provides the missing trick. Here is the algorithm that connects the dots.

  1. For each pipe $i$ with $A_i$ and $B_i$ from vertex $u$ to vertex $v$, we add an edge of weight $\log(B_i/A_i)$ from $u$ to $v$. The given $n$ vertices with the $m$ new edges is the new graph you were thinking of. Name it $G$.
  2. Apply Bellman–Ford algorithm with $s$ as the source to detect whether there is a negative-weight cycle in $G$ reachable from $s$.
  3. If there is, it is possible for $A$ to lead $B$ through a sequence of pipes starting from $s$ so that $A$ gets infinitely larger than $B$. Otherwise, no.

The idea is that the sum of weights along a walk in $G$ corresponds to the logarithm of the change of ratios of $B$'s height to $A$'s height when $A$ and $B$ have walked that walk. A negative-weight cycle means the ratio of $B$'height to $A$'s height becomes smaller when both $A$ and $B$ have walked that cycle once.

The algorithm runs in $O(mn)$ time.

Source Link
John L.
  • 39.1k
  • 4
  • 34
  • 91

You've the right idea. Yuval's comment provides the missing trick. Here is the algorithm that connects the dots.

  1. For each pipe $i$ with $A_i$ and $B_i$ from vertex $u$ to vertex $v$, we add an edge of weight $\log(B_i/A_i)$ from $u$ to $v$. The given $n$ vertices with the $m$ new edges is the new graph you were thinking of. Name it $G$.
  2. Apply Bellman–Ford algorithm with $s$ as the source to detect whether there is a negative cycle in $G$ reachable from $s$.
  3. If yes, it is possible for $A$ to lead $B$ through a sequence of pipes so that $A$ gets infinitely larger than $B$. Otherwise, no.

The idea is that the sum of weights along a path in $G$ corresponds to the logarithm of the change of ratios of $B$'s height to $A$'s height after $A$ and $B$ follows the same path.