CS 577: Introduction to Algorithms Program 6 – Arbitrage
Out: 16 March 2021 Due: 23 March 2021
Coding Question:
Reminders:
• Must be coded individually in your choice of either Python, Java, C, C++, or C# • There are hidden testcases
• Submitted through Gradescope
• There is a class-wide runtime leaderboard on Gradescope
• We encourage the use of Piazza for debugging help • Please do not cheat
Problem:
Arbitrage is the simultaneous buying and selling of an asset in different markets to make profit off of the difference in the asset’s price. For example, with currency arbitrage, say 1 USD buys 0.83 Euro, 1 Euro buys 12.934 Japanese Yen, 1 Japanese Yen buys 0.096 USD. By converting currencies through theses exchanges (USD → Euro → Yen → USD), a trader on every 1 USD would earn 1 · 0.83 · 12.934 · 0.096 ≈ 1.03 or about a 3% profit.
You’re given a list of values of an asset across different exchanges and must calculate the minimum transaction cost (as an integer percent) so as to eliminate any possible arbitrage if starting and ending in the same exchange. You may assume the asset is infinitely divisible. In the above example, a transaction cost of 1% would remove the arbitrage opportunity.
Input should be read in from stdin. The first line will contain the number of exchanges (n) and the number of possible trades (m) and all subsequent lines will contain 3 inputs, separated by spaces, where the first input is the buying location, the second input is the selling location, and the last input is the integer price (p), in the sell market, of $100 of the asset in the buy market.
Constraints:
• 1≤n≤100
• 1≤m≤10000 • 1≤p≤500
Sample Test Case 1:
Input: 22
NYSE JPX 110
JPX NYSE 110 Output:
10 Explanation:
Trading the asset from NYSE to JPX and back results in 110% ∗ 110% = 121% profit. The minimum cost solves 110 ∗ (1 − x) ∗ 110 ∗ (1 − x) ≤ 100. Thus, the minimum cost per trade is ⌈9.09%⌉ = 10%.
Sample Test Case 2:
Input: 56
NYSE JPX 110 JPX LSE 90 LSE SSE 110 SSE NYSE 111 SSE AMS 90 AMS NYSE 90
Output: 5
1
Explanation:
Optimal trade is NYSE → JPX → LSE → SSE → NYSE for profit of 120.879%. This is the highest possible profit if starting and ending in the same exchange. Thus, the minimum cost per trade solves 120.879(1−x)4 ≤ 100 for an integer x and is thus ⌈4.6%⌉ = 5%
2
Problem 2
Two players are arguing over which of their characters is the best at 1v1 combat in a tabletop RPG game, and they have asked you to help solve this dispute. In this game, combat works as follows: each character starts with a certain number of hitpoints, and players take turns selecting actions that could either harm their opponent or benefit themselves. The first character to reach 0 or fewer hitpoints loses.
Player 1’s character starts with H1 hitpoints and has two actions to choose from on each turn: attack and flex. Their character starts with an attack power of 1, and each time they choose the flex option their attack power increases by 1, up to a maximum of 5. If they choose to attack, then their character deals their attack power times A1 damage to their opponent, removing that same amount of hitpoints. Player two’s character starts with H2 hitpoints and also has two actions to choose from: attack and heal. If they choose to heal, then their character recovers 20 of their missing hitpoints (up to a maximum of H2). Because heal is a spell, it can only be used a total of two times in combat. If player 2 chooses to attack, then they deal A2 points of damage to their opponent.
Because player 1’s character initiative attribute is greater than player 2’s character, player 1 is always the first one to choose an action. Notice that there are no draws, and if both players play optimally then one of them is always guaranteed to win. The problem you are asked to solve is the following: given as input integer values H1 , A1 , H2 and A2, decide which player is guaranteed to win when both play optimally.
(a) Give a dynamic programming algorithm to solve this problem. That is, describe your algorithm by including a clear statement of your recurrence, any necessary base case(s), and your final output.
(b) Provide a clear explanation for your recurrence relation for part (a) and analyze its running time.
Page 2