Обнаружение арбитража на валютном рынкеDetecting currency-market arbitrage

Дано n валют (пронумерованы 0..n-1) и список троек `rates[i] = [a, b, rate]`, означающий "1 единица валюты a обменивается на `rate` единиц валюты b" (курс в обратную сторону не даётся напрямую и не обязан быть равен 1/rate). Нужно определить, существует ли последовательность обменов, начинающаяся и заканчивающаяся в одной и той же валюте, после которой денег становится строго больше, чем было — то есть возможен ли арбитраж.Given n currencies (numbered 0..n-1) and a list of triples `rates[i] = [a, b, rate]`, meaning "1 unit of currency a exchanges for `rate` units of currency b" (the reverse rate isn't given directly and need not equal 1/rate). Determine whether there's a sequence of exchanges starting and ending at the same currency after which the amount held is strictly larger than at the start — i.e., whether arbitrage is possible.

// Example — есть арбитраж— arbitrage exists
n = 3  // 0=USD, 1=EUR, 2=GBP// 0=USD, 1=EUR, 2=GBP
rates = [[0,1,0.9], [1,2,0.8], [2,0,1.5]]
// 1 USD → 0.9 EUR → 0.72 GBP → 1.08 USD — цепочка вернула больше, чем вложили— the chain returned more than was put in
// output: true

Первый шаг — тот же, что описан в 3.2.1: превратить курс обмена в вес ребра через логарифм. Обмен 1 единицы a на `rate` единиц b — это ребро a→b с весом `-log(rate)`. Логарифм превращает произведение курсов вдоль цепочки обменов в сумму весов пути — а знак минус превращает "поиск цепочки с итоговым курсом больше 1" (арбитраж) в привычную задачу "поиск отрицательного цикла" из 3.2.1: если произведение курсов по циклу > 1, то сумма логарифмов > 0, то сумма отрицательных логарифмов (весов) < 0 — отрицательный цикл.The first step is the same as described in 3.2.1: turn an exchange rate into an edge weight via a logarithm. Exchanging 1 unit of a for `rate` units of b is an edge a→b with weight `-log(rate)`. The logarithm turns the product of rates along an exchange chain into a sum of path weights — and the minus sign turns "find a chain with a final rate above 1" (arbitrage) into the familiar "find a negative cycle" problem from 3.2.1: if the product of rates around a cycle is > 1, the sum of logarithms is > 0, so the sum of negative logarithms (weights) is < 0 — a negative cycle.

Второй шаг — применить сам алгоритм Беллмана-Форда из 3.2.1 без изменений: инициализировать dist фиктивным нулевым источником, соединённым со всеми валютами весом 0 (чтобы не гадать, с какой валюты начинать поиск — цикл может быть недостижим из произвольно выбранной вершины), затем выполнить V-1 итераций релаксации всех рёбер, и на V-й итерации — ту самую проверку из 3.2.1: если хотя бы одно ребро всё ещё можно расслабить, в графе есть отрицательный цикл, а значит арбитраж существует.The second step is applying Bellman-Ford from 3.2.1 unchanged: initialize dist with a dummy zero-weight source connected to every currency (so there's no need to guess which currency to start the search from — a cycle might be unreachable from an arbitrarily chosen vertex), then run V-1 relaxation passes over all edges, and on the V-th pass, the exact check from 3.2.1: if at least one edge can still be relaxed, the graph has a negative cycle, meaning arbitrage exists.

class Solution {
public:
    bool hasArbitrage(int n, std::vector<std::array<double,3>>& rates) {
        // рёбра: {u, v, weight}, weight = -log(rate)// edges: {u, v, weight}, weight = -log(rate)
        std::vector<std::array<double,3>> edges;
        for (auto& r : rates)
            edges.push_back({r[0], r[1], -std::log(r[2])});

        std::vector<double> dist(n, 0.0);   // фиктивный источник соединён со всеми весом 0// dummy source connected to all with weight 0

        for (int i = 0; i < n - 1; ++i)
            for (auto& e : edges) {
                int u = (int)e[0], v = (int)e[1];
                double w = e[2];
                if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
            }

        for (auto& e : edges) {          // V-й проход — детект отрицательного цикла// V-th pass — negative-cycle check
            int u = (int)e[0], v = (int)e[1];
            double w = e[2];
            if (dist[u] + w < dist[v] - 1e-9) return true;  // арбитраж найден// arbitrage found
        }
        return false;
    }
};

Сложность O(V·E) — идентична базовому Беллману-Форду из 3.2.1. Фиктивный источник с нулевыми весами и dist, изначально равным 0 везде, — стандартный приём, эквивалентный запуску от каждой вершины по очереди, но за один проход, а не за V.Complexity is O(V·E) — identical to base Bellman-Ford from 3.2.1. The dummy zero-weight source, with dist initialized to 0 everywhere, is a standard trick equivalent to running from every vertex in turn, but in one pass instead of V.