progress

~/problems / More shortest paths

Currency arbitrage with fees

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium ~30 min Optiver

You're given n currencies and an n x n matrix rates, where rates[i][j] > 0 is how many units of currency j one unit of currency i buys. The diagonal is 1.0.

Every exchange also costs a fee: converting x units through rates[i][j] actually gives x * rates[i][j] * (1 - fee).

Write has_arbitrage(rates: list[list[float]], fee: float = 0.0001) -> bool. Return True if some sequence of two or more exchanges starts and ends at the same currency and leaves you with strictly more than you started with, after all fees. Otherwise return False. 0 <= fee < 1.

Constraints: 1 <= n <= 80.

⭐ Bonus: trying every cycle is exponential but passes small markets; a speed test with 80 currencies earns a star at O(n^3).

Floating point: use a small tolerance (around 1e-12) in your comparisons. The tests stay well away from the break-even boundary.

has_arbitrage([[1, 0.5], [2.0, 1]])                      # False: 0.5 * 2 = 1, minus fees
has_arbitrage([[1, 0.5], [2.01, 1]])                     # True:  1.005 * 0.9999^2 > 1
has_arbitrage([[1, 0.5], [2.0005, 1]], fee=0.001)        # False: the fee eats the edge
has_arbitrage([[1, 2, 1], [0.5, 1, 1.1], [0.95, 1, 1]])  # True:  0 -> 1 -> 2 -> 0 gives 2*1.1*0.95 = 2.09
Show hint

A cycle is profitable when the product of rates[i][j] * (1 - fee) along it exceeds 1. Taking logarithms turns products into sums, and negating them turns "product greater than 1" into "total weight below 0": a kind of cycle that standard shortest-path algorithms can detect.

Topic: Bellman-Ford, Floyd-Warshall, 0-1 BFS. Negative edges, all-pairs, and deque BFS for 0/1 weights.

0:00
Ctrl ' run · Ctrl ↵ submit
esc