I found a really interesting problem and I wanted to hear people's opinion.
It has to do with currency exchange rate.
If we are give some coins $c_1,c_2,\dots,c_n$ and an array $R$ that keeps the selling price, where $R[i,j]$ is the selling price of one unit of currency $c_i$ to currency $c_j$.
a) We are trying to design an algorithm that will find a sequence of coins $(c_{i_1}, c_{i_2}, \dots, c_{i_k})$ ,$R[i_1, i_2] \cdot R[i_2, i_3] \cdots R[i_{k-1}, i_k] \cdot R[i_k, i_1] >1$.
b) Show how the algorithm you designed can find and print fast such a sequence $(c_{i_1}, c_{i_2}, \dots, c_{i_k})$ (if there is one).
If someone dives into that problem it would be also interesting to know the execution time of the algorithm.
Sorry if I did mistakes with the terminology of this scientific field.
Best Answer
Conceptually, it is easier to think of the “log-exchange rates” defined by $L[i, j] = - \log R [i, j]$. (The negative sign is just for the sake of convention.) Now imagine a directed graph with the currencies as the vertices where the weight of the edge $(i, j)$ is $L[i, j]$. In terms of the new quantity we just introduced, we are seeking a cycle $(i_1, i_2, \ldots, i_k)$ such that $$ \sum_{t = 1}^{k-1} L[i_t, i_{t+1}] + L[i_k, i_1] \lt 0. $$ This equation is obtained by just taking the log of the given equation, and reversing the sign. That is, we are seeking a “negative weight cycle” in the graph, where the weight of a cycle is just the sum of the edges in the cycle.
Negative cycle detection is a standard problem in algorithmic graph theory, conventionally studied along with the shortest path problem. [The shortest path problem is the following: given a directed graph with a source and a sink terminal, find the path of least cost from the source to the sink.] A number of algorithms have been designed to solve these problems. The simplest one (in general graphs) is the Bellman-Ford algorithm which runs in $O(|V||E|)$.