Task: Crypto Trading – Analysis and Explanation
In this task a hero named Alex starts with exactly 1 BTC (one bitcoin) and wants to increase his capital through N days of trading cryptocurrencies. Every day the platform shows a matrix of exchange rates between different currencies.
At first sight the task seems abstract, but at its core it simulates the real behaviour of crypto exchanges and the ways in which algorithms try to find the most profitable sequence of conversions.
1️⃣ Introduction to cryptocurrencies and Bitcoin
Bitcoin (BTC) is the first and best-known cryptocurrency. It appeared in 2009 as the idea of digital money without intermediaries and without a central bank. All transactions are recorded in a public ledger called the blockchain.
- Every user has their own digital wallet and a private key.
- Trading takes place on crypto exchanges (e.g. Binance, Coinbase...).
- The exchange rate between currencies (e.g. BTC ⇄ ETH) changes from second to second.
When, for example, 1 BTC is worth 20 ETH, it means you can exchange one Bitcoin for 20 Ether (another cryptocurrency). If the rate goes up tomorrow, by converting back you can get more BTC than you had at the beginning — that is the basis of trading.
2️⃣ The task
Alex has K different cryptocurrencies, numbered 1 to K. Number 1 is
reserved for BTC. Every day he gets a matrix of size K × K,
where A[i][j] is the rate at which he can convert
an amount x of currency i into A[i][j] × x of currency j.
An important rule: every conversion takes one whole day, so funds converted today cannot be used again on the same day. Alex may also decide not to make any transaction on that day.
After N days, Alex wants to finish with the maximum amount of BTC. Your task is to find that maximum amount.
□ Input
N K
a K × K matrix A for every day
□ Output
One real number — the maximum amount of BTC Alex can have after N days.
The result must have a relative error of at most 10⁻⁶.
3️⃣ Example
Input:
1 3
2.0 1.0 2.5
1.4 1.0 3.14159265359
3.0 3.0 3.0
Output:
2.0000000000
Explanation: Alex starts with 1 BTC. On this day he can exchange it for 2 BTC (the rate A[1][1] = 2.0), for 1 ETH or for 2.5 DOGE, but since he can make only one conversion per day, and the result is measured in BTC, the most profitable choice is to stay in BTC (at the rate 2.0).
4️⃣ The idea of the solution
This is a typical task for dynamic programming (DP) over days and currencies. The idea is to remember the maximum amount of every currency we can have after every day, and to update it using the rates.
dp[day][curr] = the maximum amount of currency curr after day days
dp[0][1] = 1 // we have 1 BTC at the beginning
dp[0][i] = 0 // the other currencies = 0
dp[d][j] = max( dp[d-1][j], max_i( dp[d-1][i] * A_d[i][j] ) ) // no trade, or the best conversion
answer = dp[N][1] // the amount of BTC after N days
Here A_d[i][j] is the rate between currencies i and j on day d.
Every day we choose the best conversion (or keep what we have) and pass the result on to the next day.
5️⃣ Solution in C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K;
cin >> N >> K;
// 3D vector: A[d][i][j] is the conversion rate from currency i to currency j on day d
vector<vector<vector<double>>> A(N, vector<vector<double>>(K, vector<double>(K)));
// Read all matrices
for (int d = 0; d < N; d++)
for (int i = 0; i < K; i++)
for (int j = 0; j < K; j++)
cin >> A[d][i][j];
// dp[i] = the maximum amount of currency i at the end of the current day
vector<double> dp(K, 0.0);
dp[0] = 1.0; // Initial state: we have 1 BTC (the currency with index 0)
// Simulate the trading day by day
for (int d = 0; d < N; d++) {
vector<double> next = dp; // the dp for the next day; starting from dp = no transaction today
for (int i = 0; i < K; i++) {
for (int j = 0; j < K; j++) {
// If I have dp[i] units of currency i at the end of yesterday,
// today I can convert them into currency j at the rate A[d][i][j]
next[j] = max(next[j], dp[i] * A[d][i][j]);
}
}
dp = next; // move on to the state of the next day
}
// In the end we want the maximum amount of BTC (the currency with index 0)
cout << fixed << setprecision(10) << dp[0] << "\n";
return 0;
}
6️⃣ How this resembles real crypto trading
In the real world crypto traders use similar algorithms to automatically choose the best moments and pairs for exchanging currencies. The goal is always the same: maximize the profit in the base currency (here BTC).
There are also special algorithms for arbitrage – situations in which, thanks to differences in the rates between several currencies, a profit can be made even without the market growing.
In a similar way, our DP model finds the smartest sequence of conversions over several days so that Alex ends up with as much BTC as possible.
Go back to the list of tasks: interactive algorithms (SR)
Illustration: conversions between currencies through the days (DP visualization)
The picture shows three currencies (1 = BTC, 2 = ETH, 3 = DOGE) at four points in time:
from Day 0 (the initial state) to Day 3 (after 3 days).
Every arrow from currency i on day d to currency j on day d+1
is a possible conversion with the factor A[d][i][j]. DP chooses the maximum path.
How to read the diagram:
- The columns are the days: Day 0 is the initial state (before trading starts), Day 3 is after 3 days.
- The circles are the currencies: 1 = BTC, 2 = ETH, 3 = DOGE.
- Every arrow from i on day d to j on day d+1 carries the factor
A[d][i][j]. If you had the amountvin currencyiat the end of dayd, after the conversion you getv * A[d][i][j]in currencyjat the beginning of dayd+1(which will be used for the next decision). - For every node in the next column the DP algorithm looks for the maximum over all incoming arrows — that is exactly the operation
next[j] = max(next[j], dp[i] * A[d][i][j]).
Task: Alex and Cryptocurrencies
Alex starts with exactly 1 BTC and wants to increase his capital through a series of N days of trading. The platform has K cryptocurrencies, numbered from 1 to K, where currency number 1 is always BTC.
Description of the problem
Every day Alex gets a matrix of rates of size K × K, where the element
A[i][j] is the rate at which he can convert an amount x in currency i
into A[i][j] * x units of currency j.
Transactions take a whole day, which means that funds converted today cannot be used again on the same day. Alex may also decide not to make any transaction on that day.
After N days, the goal is to finish with as much BTC as possible.
Input and output
Input:
N K
(N matrices of K × K real numbers)
Output:
The maximum amount of BTC after N days (a real number, error ≤ 1e-6)
Example
Input:
1 3
2.0 1.0 2.5
1.4 1.0 3.14159265359
3.0 3.0 3.0
Output:
2.0000000000
How cryptocurrency trading works
Bitcoin (BTC) is the first and best-known cryptocurrency. It is digital money that works independently of banks, and transactions are recorded in a public ledger called the blockchain.
The rate between different cryptocurrencies (e.g. BTC, ETH, LTC) changes all the time, just like the rate between
the euro and the dollar. In this task, those rates are represented by a matrix of numbers
A[i][j] – how many units of currency j you get for 1 unit of currency i.
An example in practice
Suppose that today you can exchange 1 BTC for 2 ETH (Ether), and tomorrow 1 ETH for 1.5 BTC. If you exchange BTC for ETH today, and ETH back to BTC tomorrow, you end up with 3 BTC after 2 days — which means a profit!
So the task asks you to find, from the daily rates, the optimal sequence of conversions with which Alex gets the most BTC at the end of the trading period.
The idea of the solution
This is a classic dynamic optimization problem. Instead of Alex changing currencies at random, we can use dynamic programming to compute, for every currency and every day, the maximum amount that can be obtained.
Let dp[d][k] be the maximum amount of currency k that Alex can have at the end of day d.
- At the beginning:
dp[0][1] = 1(he has 1 BTC), and the other currencies are 0. - For every next day and every currency we compute the best value using that day's matrix of rates (or keep the amount from the day before).
- In the end, the result is
dp[N][1]– the maximum number of BTC after all the days.
Time complexity
For every day we go through all pairs of currencies (i, j), so the complexity is O(N × K²),
which is feasible for the given limits (N ≤ 80, K ≤ 50).
Visual representation
The picture below shows the flow of trading through the days: every arrow shows a possible conversion between currencies. The goal is to find the path that leads to the largest number of BTC units at the end.
Go back to the page with interactive algorithms: Alex and cryptocurrencies (SR).
