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. Trying every cycle is exponential and won't pass the large tests; aim for 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.