Arbitraža dobiti

Arbitraža je simultana kupovina i prodaja iste imovine, koja se na različitim tržištima trži po različitim cenama, a sve to sa namerom profita. Osoba koja vrši arbitražu je arbitar. Prost primer arbitraže je kupovina i prodaja valuta. Na primer, pretpostavimo da se za \(1 \mbox{RSD}\) (srpski dinar) može kupiti \(0.77 \mbox{INR}\) (indijska rupija), za \(1 \mbox{INR}\) se može kupiti \(1.82 \mbox{JRY}\) (japanski jen), i za \(1 \mbox{JRY}\) se može kupiti \(0.73 \mbox{RSD}\). Tada arbitar može za \(1 \mbox{RSD}\) kupiti \(0.77 \times 1.82 \times 0.73 = 1.023 \mbox{RSD}\), i ostvariti profit od \(2.3 \%\).

Opis ulaza

Sa standardnog ulaza se unosi broj valuta \(n\), a odmah zatim i \(n\) oznaka valuta sa \(c_1, c_2, \ldots c_n\). Nakon toga se unose elementi matrice \(\mathbf{R}_{n \times n} = (r_{i,j})\), tako da jedna jedinica valute \(c_i\) može kuputi \(r_{i, j}\) jedinica valute \(c_j\).

Opis izlaza

Na standardni izlaz, u leksikografskom poretku, ispisati sve moguće cikluse valuta \(\langle c_{i_1}, c_{i_2}, \ldots c_{i_k}, c_{i_1} \rangle\) za koje važi

\[r_{i_1, i_2} \cdot r_{i_2, i_3} \cdots r_{i_{k-1}, i_k} \cdot r_{i_k, i_1} > 1.\]

Primer

Ulaz

Izlaz

Objašnjenje

Na primer, za ciklus \(\langle \mbox{MXN}, \mbox{USD}, \mbox{RUB}, \mbox{INR}, \mbox{PLN}, \mbox{MXN} \rangle\) važi \(0.052 \times 64.52 \times 1.11 \times 0.055 \times 4.94 = 1.012 > 1\).

Rešenje

Detekcija postojanja ciklusa

Rešimo prvo relaksiraniji problem. Naime, hoćemo da proverimo da li postoji ciklus valute \(\langle c_{i_1}, c_{i_2}, \ldots c_{i_k}, c_{i_1} \rangle\) za koji važi

\[\begin{equation} r_{i_1, i_2} \cdot r_{i_2, i_3} \cdots r_{i_{k-1}, i_k} \cdot r_{i_k, i_1} > 1. \label{eq:ineq} \end{equation}\]

Ideja se zasniva na modelovanju grafa tako da je moguće Belman-Fordovim algoritom detektovati da li postoji ciklus negativne težine u grafu. Neka čvor \(i\) odgovara valuti \(c_i\). Postavlja se pitanje šta izabrati kao težine grana tako da Belman-Fordov algoritam detektuje ciklus negativne težine. Kako, u nejednačini gore, imamo da figuriše operacija množenja, i pri tome Belman-Fordov algoritam sabira težine grana, zgodno je logaritmovati celu nejednačinu, te dobijamo:

\[\begin{equation} \log (r_{i_1, i_2}) + \log (r_{i_2, i_3}) + \ldots + \log (r_{i_{k-1}, i_k}) + \log (r_{i_k, i_1}) > 0. \end{equation}\]

Kako Belman-Fordov algoritam može da detektuje cikluse negativne težine nejednačinu dalje transformišemo u

\[\begin{equation} -\log (r_{i_1, i_2}) - \log (r_{i_2, i_3}) - \ldots - \log (r_{i_{k-1}, i_k}) - \log (r_{i_k, i_1}) < 0. \end{equation}\]

Zbog toga će težina grane \((i, j)\) biti \(-\log(r_{i, j})\).

Ispisivanje ciklusa

Kada detektujemo ciklus negativne težine, pri obradi grane \((u, v)\), treba ga ispisati. Kako Belman-Fordovim algoritmom čuvamo za svaki čvor i njegovog roditelja možemo rekonstruisati putanju do čvora \(v\). Ta putanja će sigurno sadržati ciklus koji dalje detektujemo gramzivo prolazeći prvo unazad, a onda i unapred kroz putanju. Kako za razne grane \((u, v)\) možemo detektovati iste cikluse negativne težine, pronađene cikluse čuvamo u skupu.

Analiza složenosti

Složenost Belman-Fordovog algoritma je, u opštem slučaju, \(O(|V||E|)\). Kako za svaku valutu postoji grana, tada će složenost Belman-Fordovog algoritma biti \(O(n^3)\). Rekonstrukcija i ispisivanje ciklusa u leksikografskom poretku je složenosti \(O(n^2)\). Zbog toga je ukupna složenost algoritma \(O(n^3)\).

#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
#include <algorithm>
#include <stack>
#include <set>

using namespace std;

void negative_log(vector<vector<double>> &R)
{
    const int n = R.size();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            R[i][j] = - log(R[i][j]);
        }
    }
}

void relax(int u, int v, 
           const vector<vector<double>> &R, 
           vector<double> &dist, 
           vector<int> &parent)
{
    if (dist[v] > dist[u] + R[u][v]) {
        dist[v] = dist[u] + R[u][v];
        parent[v] = u;
    }
}

string build_cycle(int u, int v, 
                 const vector<int> &parent, 
                 const vector<string>& currencies)
{
    vector<int> path;

    path.push_back(v);
    path.push_back(u);

    while (find(path.begin(), path.end(), parent[u]) == path.end()) {
        path.push_back(parent[u]);
        u = parent[u];
    }
    path.push_back(parent[u]);

    int first_in_cycle = path.back(); path.pop_back();

    string cycle = currencies[first_in_cycle] + " ";
    while (!path.empty() && path.back() != first_in_cycle) {
        cycle += currencies[path.back()] + " ";
        path.pop_back();
    }
    cycle += currencies[first_in_cycle];

    return cycle;
}

void arbitrage(vector<vector<double>> &R, const vector<string> &currencies)
{
    const int n = R.size();
    
    negative_log(R);

    vector<int> parent(n, -1);
    vector<double> dist(n, numeric_limits<double>::max());
    dist[0] = 0.0;

    for (int i = 0; i < n - 1; i++) {
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                relax(u, v, R, dist, parent);
            }
        }
    }

    set<string> sequences;
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            if (dist[v] > dist[u] + R[u][v]) {
                sequences.insert(build_cycle(u, v, parent, currencies));
            }
        }
    }

    for (auto sequence : sequences) {
        cout << sequence << endl;
    }
}

int main() {
    int n; cin >> n;

    vector<string> currencies(n);
    for (int i = 0; i < n; i++) {
        cin >> currencies[i];
    }

    vector<vector<double>> R(n, vector<double>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> R[i][j];
        }
    }

    arbitrage(R, currencies);

    return 0;
}