Koľko bitkoinov vie vyhrať gladiátor $\boldsymbol{a}$?

Aby sme zistili koľko bitkoinov môže zarobiť nejaký gladiátor $a$, skúsme najskôr zistiť ktoré bitkoiny môže $a$ získať.

Aby gladiátor $a$ získal bitkoin, ktorý na začiatku turnaja patril gladiátorovi $b$, musí k nemu tento bitkoin nejako doputovať. Táto púť bude vyzerať tak, že najskôr $b$ prehrá súboj s nejakým iným gladiátorom, ten (ak to ešte nie je gladiátor $a$) potom prehrá s ďalším gladiátorom, ten prehrá s ďalším, atď., až nakoniec posledný gladiátor z tejto reťaze prehrá s gladiátorom $a$.

Povedané formálne, $a$ dokáže získať bitkoin od $b$, vtedy a len vtedy, keď existuje postupnosť gladiátorov $b = g_1, g_2, \ldots, g_k = a$ taká, že pre všetky prípustné $i$ vie $g_{i+1}$ poraziť $g_i$ v aspoň jednom type súboja.

Máme teda dobre popísaný vzťah “$a$ vie získať bitkoin $b$”. Viac bitkoinov než počet takýchto gladiátorov $b$ gladiátor $a$ nevie získať. Ale to, že $a$ vie získať bitkoiny od $b_1, \ldots, b_m$ ešte neznamená, že ich vie získať všetky v priebehu jedného turnaja. Ukazuje sa ale, že sa to dá.

Dobre sa to vysvetľuje z grafového hľadiska. Uvažujme orientovaný graf, v ktorom vrcholy reprezentujú gladiátorov, a je v ňom hrana $x \rightarrow y$ vtedy, keď $x$ vie poraziť $y$ aspoň v jednom type súboja. Potom $a$ vie získať bitkoiny práve tých gladiátorov, ktorí sú dosiahnuteľní z $a$ (rozmyslite si).

Postupnosť zápasov, v ktorej $a$ získa bitkoiny od všetkých takýchto gladiátorov, vieme nájsť nasledovne:

1. Začneme s prázdnou postupnosťou zápasov.

2. Spustime prehľadávanie (napríklad do hĺbky) z $a$ a vždy, keď prejdeme po hrane do nejakého ešte nenavštíveného vrcholu, zafarbime túto hranu na červeno. Po skončení prehľadávania budú červené hrany tvoriť strom obsahujúci práve vrcholy dosiahnuteľné z $a$.

3. Z tohto stromu odstránime hranu $x \rightarrow y$ vedúcu do listu a do postupnosti pridáme zápas medzi $x, y$, pričom typ zápasu zvolíme tak, aby $x$ vyhral.

4. Opakujeme predchádzajúci krok, kým sú v grafe hrany.

(Prvá tabuľka zobrazuje sily jednotlivých gladiátorov. Druhá tabuľka obsahuje gladiátorov usporiadaných podľa ich síl. Tretia tabuľka zobrazuje zápasy v takom turnaji, v ktorom by gladiátor $g_7$ získal všetky bitkoiny, ktoré vie získať.)

Prvý správny algoritmus

Predchádzajúca úvaha nám dáva jednoduchý algoritmus na riešenie úlohy: zostrojíme graf a postupne z každého vrcholu $a$ spustíme prehľadávanie, ktorým zistíme, koľko vrcholov z neho vieme dosiahnuť. To je zároveň aj počet bitkoinov, ktorý si vie gladiátor $a$ z turnaja odniesť.

Graf obsahuje $n$ vrcholov a $O(n^2)$ hrán, časová zložitosť je preto $O(n^3)$. Pamäťová zložitosť je $O(n^2)$ (ak v pamäti vytvoríme všetky hrany), prípadne $O(n)$ (ak si pamätáme iba sily gladiátorov).

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> graf;
vector<int> navstivene;
int pocet;

void dfs(int v) {
  if (navstivene[v]) return;
  navstivene[v] = true;
  pocet++;

  for (int i = 0; i < graf[v].size(); ++i) {
    dfs(graf[v][i]);
  }
}

int main() {
  int n; scanf("%d", &n);
  vector<int> mec(n), kopija(n);
  navstivene.resize(n);

  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &mec[i], &kopija[i]);
  }

  graf.resize(n);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (mec[i] > mec[j]) graf[i].push_back(j);
      if (kopija[i] > kopija[j]) graf[i].push_back(j);
    }
  }

  for (int i = 0; i < n; ++i) {
    pocet = 0;
    for(int j = 0;j < n;j++) navstivene[j] = 0;
    dfs(i);
    printf("%d\n", pocet);
  }

  return 0;
}

Predchádzajúce riešenie možno o rád zrýchliť nasledujúcim trikom: usporiadajme si gladiátorov do postupnosti $g’1, g’_2, \ldots, g’_n$ podľa rastúcej sily v boji s mečom. Potom nemusíme mať v grafe všetky hrany $g’_i \rightarrow g’_j$ pre $i > j$, stačí, ak v ňom budú hrany $g’_i \rightarrow g’$ pre všetky prípustné $i$.

(Graf, v ktorom neuvažujeme zbytočné hrany. Pre každú silu $k > 1$ a každý typ boja máme hranu vedúcu od gladiátora so silou $k$ ku gladiátorovi so silou $k - 1$. Zelené hrany zodpovedajú boju s mečom, modré hrany boju s kopijou.)

Prečo? Ak v pôvodnom grafe existovala cesta z $a$ do nejakého $b$, tak v novom grafe dostaneme cestu z $a$ do $b$ tak, že každú hranu na pôvodnej ceste, ktorá má tvar $g_i \rightarrow g_j$ pre $i > j$, nahradíme postupnosťou hrán $g_i \rightarrow g_{i - 1}, g_{i - 1} \rightarrow g_{i - 2}, \ldots, g_{j + 1} \rightarrow g_j$. Takže pre ľubovoľný vrchol $a$ je množina vrcholov dosiahnuteľných z $a$ rovnaká, ako v pôvodnom grafe.

Rovnako vieme zredukovať počet hrán, ktoré zodpovedajú súbojom s kopijou. V novom grafe budeme mať $2 \cdot (n - 1) = O(n)$ hrán, a vylepšíme tým časovú zložitosť algoritmu na $O(n^2)$.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

vector<vector<int>> graf;
vector<int> vysledok, navstivene;
int pocet;

void dfs(int v) {
  if (navstivene[v]) return;
  navstivene[v] = true;
  pocet++;

  for (int i = 0; i < graf[v].size(); ++i) {
    dfs(graf[v][i]);
  }
}

int main() {
  int n; scanf("%d", &n);
  vector<pii> mec(n), kopija(n);
  vysledok.resize(n);
  navstivene.resize(n);

  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &mec[i].first, &kopija[i].first);
    mec[i].second = kopija[i].second = i;
  }
  sort(mec.begin(), mec.end());
  sort(kopija.begin(), kopija.end());
  graf.resize(n);

  for (int i = 1; i < n; ++i) {
    graf[mec[i].second].push_back(mec[i-1].second);
    graf[kopija[i].second].push_back(kopija[i-1].second);
  }

  for (int i = 0; i < n; ++i) {
    pocet = 0;
    for(int j = 0;j < n;j++) navstivene[j] = 0;
    dfs(mec[i].second);
    vysledok[mec[i].second] = pocet;
  }

  for (int i = 0; i < n; ++i) {
    printf("%d\n", vysledok[i]);
  }

  return 0;
}

Vzorové riešenie

Majme gladiátorov $g_1, g_2, \ldots, g_n$ usporiadaných vzostupne podľa sily v boji s mečom. Všimnime si, že všetky bitkoiny, ktoré vie získať $g_i$, vie získať aj $g_{i + 1}$. To ale znamená, že keď hľadáme vrcholy dosiahnuteľné z $g_{i + 1}$, tak nám stačí hľadať iba také vrcholy, ktoré nie sú dosiahnuteľné z $g_i$. Vrcholy dosiahnuteľné z $g_i$ totiž môžeme zarátať automaticky.

Budeme teda púštať prehľadávanie postupne od najslabších gladiátorov k najsilnejším, teda v poradí $g_1, g_2, \ldots, g_n$. Pre každého gladiátora si pamätáme, či sme ho už v niektorom prehľadávaní navštívili, a pamätáme si tiež počet už navštívených gladiátorov. Keď prehľadávame z $g_i$, tak nenavštevujeme vrcholy, ktoré sme už navštívili v niektorom z predchádzajúcich prehľadávaní.

Rozmyslite si, že takýmto spôsobom sú po $i$-tom prehľadávaní navštívení práve tí gladiátori, ktorí sú dosiahnuteľní z $g_i$. Práve od nich vie $g_i$ získať bitkoin. Ich počet je teda počet bitkoinov, ktoré vie $g_i$ získať.

Zložitosť

Na začiatku si potrebujeme utriediť gladiátorov podľa sily. To nám bude trvať $O(n \log n)$. Počas prehľadávaní navštívime každý vrchol grafu najviac raz, čo je $O(n)$ roboty (lebo graf má len $n$ vrcholov a $O(n)$ hrán). Preto je časová zložitosť celého algoritmu $O(n \log n)$. Pamäťová zložitosť ostáva $O(n)$.

Pritom časová zložitosť $O(n \log n)$ je iba kvôli triedeniu, my však máme čísla z rozsahu od $1$ po $n$. Vieme ich teda utriediť count sortom, a dostaneme tak lepší čas $O(n)$.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

vector<vector<int>> graf;
vector<int> vysledok, navstivene;
int pocet;

void dfs(int v) {
  if (navstivene[v]) return;
  navstivene[v] = true;
  pocet++;

  for (int i = 0; i < graf[v].size(); ++i) {
    dfs(graf[v][i]);
  }
}

void countSort(vector<pii> &v) {
  vector<pii> utriedene(v.size());
  for (int i = 0; i < v.size(); ++i) {
    utriedene[v[i].first - 1] = v[i];
  }
  v = utriedene;
}

int main() {
  int n; scanf("%d", &n);
  vector<pii> mec(n), kopija(n);
  vysledok.resize(n);
  navstivene.resize(n);

  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &mec[i].first, &kopija[i].first);
    mec[i].second = kopija[i].second = i;
  }
  countSort(mec);
  countSort(kopija);
  graf.resize(n);

  for (int i = 1; i < n; ++i) {
    graf[mec[i].second].push_back(mec[i-1].second);
    graf[kopija[i].second].push_back(kopija[i-1].second);
  }

  for (int i = 0; i < n; ++i) {
    dfs(mec[i].second);
    vysledok[mec[i].second] = pocet;
  }

  for (int i = 0; i < n; ++i) {
    printf("%d\n", vysledok[i]);
  }

  return 0;
}