Arbitrage Detection

Description
<span style="color: rgb(0, 0, 0); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 15px; line-height: 22.5px;">Consider a market for financial transactions that is based on trading commodities. The table below</span><span style="color: rgb(0, 0, 0); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 15px; line-height: 22.5px;">&nbsp;shows conversion rates among currencies.&nbsp;</span><div><span style="color: rgb(0, 0, 0); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 15px; line-height: 22.5px;"><br></span></div><pre><p>USD 1 0.741 0.657 1.061 1.005<br>EUR 1.349 1 0.888 1.433 1.366<br>GBP 1.521 1.126 1 1.614 1.538<br>CHF 0.942 0.698 0.619 1 0.953<br>CAD 0.995 0.732 0.650 1.049 1</p></pre><div><span style="color: rgb(0, 0, 0); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 15px; line-height: 22.5px;"><br></span></div><div><span style="color: rgb(0, 0, 0); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 15px; line-height: 22.5px;">The table has one line per currency, giving its name followed by the conversion rates to the other currencies. An&nbsp;</span><em style="color: rgb(0, 0, 0); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 15px; line-height: 22.5px;">arbitrage opportunity</em><span style="color: rgb(0, 0, 0); font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 15px; line-height: 22.5px;">&nbsp;is a directed cycle such that the product of the exchange rates is greater than one. For example, our table says that 1,000 U.S. dollars will buy 1,000.00 × .741 = 741 euros, then we can buy 741 × 1.366 = 1,012.206 Canadian dollars with our euros, and finally, 1,012.206 × .995 = 1,007.14497 U.S. dollars with our Canadian dollars, a 7.14497-dollar profit!</span><br><div><br></div><div><font color="#000000" face="Helvetica Neue, Helvetica, Arial, sans-serif"><span style="font-size: 15px; line-height: 22.5px;">Bounty for algorithm that takes X exchange rates and returns arbitrage&nbsp;opportunities&nbsp;if they exist.</span></font></div><div><br></div><pre><font color="#000000" face="Helvetica Neue, Helvetica, Arial, sans-serif"><span style="font-size: 15px; line-height: 22.5px;">Sample Input: &nbsp;</span></font><span style="color: rgb(38, 38, 38); font-family: arial, sans-serif; line-height: 16px; background-color: rgb(255, 255, 255);">[[1,&nbsp;0.741, &nbsp;0.657, &nbsp;1.061, &nbsp;1.005], </span><span style="color: rgb(38, 38, 38); font-family: arial, sans-serif; line-height: 16px; background-color: rgb(255, 255, 255);">[1.349,1,&nbsp;0.888, &nbsp;1.433, &nbsp;1.366], [1.521, &nbsp;1.126, &nbsp;1, 1.614, 1.538], </span><span style="color: rgb(38, 38, 38); font-family: arial, sans-serif; line-height: 16px; background-color: rgb(255, 255, 255);">[0.942, 0.698, 0.619, 1,0.953], </span><span style="color: rgb(38, 38, 38); font-family: arial, sans-serif; line-height: 16px; background-color: rgb(255, 255, 255);">[0.995, &nbsp;0.732,0.650,1.049,1]]&nbsp;</span></pre></div>
Fulfilled By
    • requests
Discussion
  • {{comment.username}}
Status
Fulfilled
Bounty expires in
Bounty expired
Bounty
0
Tags
(no tags)