13th JLTi Code Jam – Mar 2018
After adding new node to Floyd-Warshall algorithm incrementally and dealing with decreasing rate (of an existing currency pair), the next logical thing is how to deal with increasing rate (of an existing currency pair). By an existing currency pair we mean both the currencies were already present and there was already a rate between the two.
Just like before, given that we have an existing best path cost matrix, when a rate between two currencies increases what shall we do? Once again, we have two options: i) re-compute the cost matrix from the scratch, using Floyd-Warshall, at a cost O(V3) and ii) update the already computed cost matrix using some partial computations. This problem expects a solution using the second option.
Input:
1 USD = 1.380 SGD
1 SGD = 3.080 MYR
1 MYR = 15.120 INR
1 INR = 0.012 GBP
1 GBP = 1.29 USD
I CAD = 0.57 GBP
1 GBP = 1.30 USD
Explanation: We have 7 inputs here. Each time an input is given, we need to present an output and hence, we have 7 lines of output.
The first 6 inputs do not result in any arbitrage; we output “No luck here”.
At 7th input, we see the existing rate from GBP to USD, which was 1.29 last time, has changed (increased) to 1.30 now. With this new rate in effect, an arbitrage comes into picture now. We need to output the path that creates that arbitrage.
Since in this problem, we are dealing with only increasing rate, in input, between two currencies, rate will only increase. For example, an input like 1 GBP = 1.25 USD will never appear.
When multiple arbitrages exist, printing any one will do.
Output:
No luck here
No luck here
No luck here
No luck here
No luck here
No luck here
USD -> SGD -> MYR -> INR -> GBP -> USD
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. Use existing solution for this.
If input contains a rate that has increased since last time, accommodate that change in the best path cost matrix using some partial computations, instead of computing the whole matrix from the scratch.
Sharing Experiences 