11th JLTi Code Jam – Jan 2018
Here we revisit Manipulating Money Exchange problem where we tried to find currency arbitrage using Bellman-Ford at a time complexity of O(|V||E|).
In general, this kind of graph can be dense. Suppose, there are 4 currencies: USD, SGD, GBP and INR. Usually, a rate is given from each currency to all other currencies, resulting in |V|2 edges. Hence, Bellman-Ford ends up with O(|V||E|) = O(|V||V|2) = O(|V|3), that is quite expensive. Specially, when you consider the fact that apart from the few hundred fiat currencies, there are 1000+ cryptocurrencies out there.
Also we should not forget that currency exchange rate is not a factor of solely the currency itself, rather it is tied with an exchange. For example, suppose, Moneycorp exchange has a USD to SGD rate 1.4 while for HiFX it is 1.396 for the same. So we see, USD appearing twice in the graph – once as part of Moneycorp and again as part of HiFX.
However, computing shortest paths, a prerequisite for finding arbitrage, is something quite expensive. In this problem, we need to incrementally compute shortest paths when a new vertex, nth one arrives, assuming we have pre-computed results for (n-1) vertices that we can re-use.
To be more specific, suppose, at this moment, we have 12344 vertices and we already know whether there is an arbitrage, after computing the necessary shortest paths. And then, a new currency, JioCoin arrives with some new rates (from JioCoin to some existing currencies, say, JioCoin to INR and from some existing currencies to JioCoin, say, SGD to JioCoin). Now we have 12345 vertices. Computing shortest paths for a dense graph with 12345 vertices would take a very long time (try running 3 nested for loops, each looping 12345 times), doing billions of computations.
At this moment, would it be not wise to use the existing results for 12344 vertices? And then incrementally adjust the new shortest paths and compute some new ones? That is precisely, this problem is all about. We need to incrementally, adjust/add shortest paths once a new vertex arrives. And this is to be done at a time complexity of O(|V|2), something that is comfortably manageable. After this, we have to now say, whether an arbitrage exists.
Input:
1 USD = 1.380 SGD
1 SGD = 3.080 MYR
1 MYR = 15.120 INR
1 INR = 0.012 GBP
1 GBP = 1.30 USD
I CAD = 0.57 GBP
Explanation: Whenever a rate arrives, starting from the first, for each new vertex, we need to incrementally adjust/add shortest paths, find whether an arbitrage exists or not and output the same. We have 6 inputs here. Each time an input comes, we need to output and hence, we have 6 lines of output. The first 4 did not result in any arbitrage, we output “No luck here”. From 5th we have an arbitrage and we output the same.
Once an arbitrage is found, it is going to last. Note that, there might exist more than one arbitrage. Printing any one will do.
An important thing: rate between a certain currency pair will not appear twice in the input. Meaning once, GBP to USD rate arrives at line 5, a new rate between the two won’t arrive again.
Output:
No luck here
No luck here
No luck here
No luck here
USD -> SGD -> MYR -> INR -> GBP -> USD
USD -> SGD -> MYR -> INR -> GBP -> USD
Input:
1 USD = 1.38295 SGD
1 SGD = 3.08614 MYR
1 MYR = 15.0996 INR
1 INR = 0.0119755 GBP
1 GBP = 1.295 USD
Output:
No luck here
No luck here
No luck here
No luck here
No luck here
Task: For each line of input, for each new vertex, incrementally adjust/add shortest paths at a cost (time) of O(|V|2), detect the presence of an arbitrage and output as specified.
Sharing Experiences 