FastPrep
Problem · Dynamic Programming

Profitable Currency Exchange Cycle

Learn this problem
● HardOptiver logoOptiverFULLTIMEOA

Problem statement

The square matrix rates describes currency conversions. Exchanging one unit of currency i into currency j yields rates[i][j] units.

An exchange cycle begins and ends at the same currency and uses between 1 and rates.length exchanges, inclusive. Intermediate currencies may repeat. The exchange-rate product is applied to the starting amount, then one fee equal to 0.01% of the starting amount is charged.

Return true when some allowed cycle is strictly profitable after that one fee; otherwise return false.

Function

hasProfitableExchangeCycle(rates: double[][]) → boolean

Examples

Example 1

rates = [[1.0,1.1,0.9],[0.9,1.0,1.1],[1.0,0.9,1.0]]return = true

The cycle 0 -> 1 -> 2 -> 0 has product 1.21. After the one starting-amount fee, the result remains greater than 1.

Example 2

rates = [[1.0,0.9],[1.1,1.0]]return = false

The nontrivial two-exchange product is 0.99, and a diagonal exchange has product 1. Neither is profitable after the fee.

Constraints

  • 1 <= rates.length <= 40
  • rates[i].length = rates.length
  • 10^-4 <= rates[i][j] <= 10^4
  • rates[i][i] = 1
  • For every allowed closed exchange sequence, its log-rate sum differs from the profitability threshold by at least 10^-10.

More Optiver problems

drafts saved locally
public boolean hasProfitableExchangeCycle(double[][] rates) {
    // write your code here
}
rates[[1.0,1.1,0.9],[0.9,1.0,1.1],[1.0,0.9,1.0]]
expectedtrue
checking account