[Math] From currency conversions to graph modeling

algorithmsgraph theory

The problem

I am trying to solve the following programming problem (in C++).

I have tried to solve it thoughtlessly just typing code and observing what happens, but, as expected, I have reached nowhere.

So, I want to guarantee that I can understand the math basis before trying to type the algorithm.

This is the problem (adapted):

Currency converter

You are using an on-line currency converter. You notice that they give you $0.8$ pounds for
one euro, $1.4$ dollars for one pound, and $0.9$ euros for one dollar.
Wait a moment… So they really give you $0.8 \times 1.4 \times 0.9 = 1.008$ euros for
one euro??? Hurry up, you can get rich!

Input

Every case consist of $m$ direct changes. You are given $m$ triples with two different names of
currencies $x$ and $y$, and the number of $y$’s given for one $x$ (a real
number between $0.6$ and $1.5$). Assume $2 ≤ m ≤ 1000$. There is at most one
direct change from $x$ to $y$ for every pair of currencies $x$ and $y$.

Output

For every case, say “YES” if you can get rich, and print “NO”
otherwise.

Test cases: input/output

— Test case 1 (should return YES)

euro pound 0.8
pound dollar 1.4
dollar euro 0.9

— Test case 2 (should return NO)

euro pound 0.7
pound dollar 1.4
dollar euro 0.9

— Test case 3 (should return YES)

euro dollar 1.123
yen yuan 1.1
yuan yen 1

Font: https://jutge.org/problems/P84185_en/statement

My attempt

I suppose that it is not a bad idea to represent that data into a directed graph with weights, let's say $G$.

For the first case, e.g, I would set $G = (V,E)$ where
$$V = \{ euro, pound, dolar\}$$
$$E = \{ euro\ pound, pound\ dollar, dollar\ euro\}$$
with $\text{weight}(euro\ pound) = 0.8$, etc.

Then:

  • Definition: Given a cycle $C\colon x_0\;x_1\cdots x_k\;x_0$, we define the Weight Product (W.P.) of $C$ as:
    $$WP(C) = \text{weight}(x_0x_1) \times \text{weight}(x_1x_2) \times \cdots \times \text{weight}(x_k x_0)$$
  • Our objective is to find a cycle $C$ so $WP(C) > 1$.

So, I do:

Function has_got_WP_cycle:
list visited = { }
for each v in V
   if (not v in visited)
     if (DFS(v))
       return true
return false

with a modified version of the DFS.

But I am not really sure if it is a correct way to solve the problem. Any idea?

Best Answer

This problem can be solved using algorithms which can detecting negative cycles after replacing every weight by the log of this weight.

Replacing every weight by its log reduces the multiplication of the weights to a sum since $\log(a) + \log(b) = \log(a \cdot b)$. If the weights are replaced in this way, the cost for cycle $C$ becomes $\log(WP(C))$ where $WP(C)$ is the weight product you defined.

A cycle $C$ with $WP(C) > 1$ now has a cost of greater than 0, and all other cycles cost at most 0. Thus, you need to find a cycle with positive cost.

A positive cost cycle can be found by replacing each weight by its negative and applying an algorithm detecting negative cycles, e.g., the algorithm of Bellman and Ford

Related Question