Find Arbitrage with graph theory

Question

I am trying to solve this problem: https://open.kattis.com/problems/arbitrage

If you are going to travel to the World Finals, you cannot rely on Czech Crowns. You would have to exchange your money for various foreign currencies. This problem deals with multiple currencies and their exchange rates. Your task is to verify that some set of exchange rates is safe, namely detect a possibility of so-called arbitrage.

An arbitrage is a risk-free combination of buy and sell operations that gains profit from imbalance in market prices. The prices may apply to various things, typically stock exchange but also currencies.

Input The input consists of several test cases. Each case begins with a line containing one positive integer number 𝐶, 1≤𝐶≤200, the number of currencies.

The second line of each test case contains 𝐶 currency codes separated by a space. Each code is composed of 3 uppercase letters and all codes in one test case are different.

The third line contains one integer number 𝑅,0≤𝑅≤𝐶⋅(𝐶−1), the number of exchange rates available. Each of the following 𝑅 lines contains one exchange rate in the following format: first currency code, space, second currency code, space, integer number 𝐴𝑖, colon (’:’), and integer number 𝐵𝑖. The meaning is as follows: If you pay 𝐴𝑖 units of the first currency, you will get 𝐵𝑖 units of the second currency. You may assume that 1≤𝐴𝑖,𝐵𝑖≤100 and that the two currencies are different.

The last test case is followed by a line with 𝐶=0.

My approach is to do a dfs rooted at every node, checking if there's a cycle whose product is bigger than 1.

This runs in O(n^2).

Is there a faster solution?

Answer 1

To clarify, this problem has two measures of input size; C is the number of currencies and R is the number of exchange rates available. The "brute-force" solution of using DFS from every currency is O(C² + CR), where in general R can be up to O(C²) itself.

The problem can be modelled as finding a negative-weight cycle in a graph. The nodes are the currencies, the edges are the exchange-rate pairs, and the edge weight is -log(r) for an exchange rate r. Using negative logarithms means the sum of weights for a cycle is negative if and only if the product of the exchange rates is greater than 1.

Finding a negative-weight cycle is usually achieved by adapting a standard shortest-path algorithm, such as Bellman-Ford in O(CR) time, or Floyd-Warshall in O(C³) time. Neither of these is asymptotically better than your solution in the case that R is O(C) or greater, but it may be worth benchmarking to see if an alternative is faster in practice.