8. Obchod mení cenu kryptomeny! vzorové riešenie

5 3

5 5
6 6
7 7
8 8
9 9

1 7 1 5 22
2 8 1 5 22
3 9 1 5 22

22
20
17

V odhadoch časovej zložitosti budeme označovať ako \(P\) horný odhad množstva peňazí, ktoré má Jemko pri sebe. (V testovacích prípadoch \(P = 50\).)

Hrubá sila

Tak ako v pôvodnej úlohe, aj v tejto vieme použiť štandardný algoritmus na riešenie problému batoha (tzv. knapsack algoritmus). O kryptomenách si neudržujeme žiadnu ďalšiu informáciu, iba ich ceny a hodnoty. Zmenu ceny potom vieme vykonať v konštantnom čase.

// knapsack.cpp

#include <vector>
using namespace std;

#define NEVIEM -1

int knapsack(vector<pair<int, int> >& K, int n, int p, vector<vector<int> >& memo) {
  // K := ceny a hodnoty kryptomien
  // n := prvych kolko kryptomien uvazujeme?
  // p := mnozstvo penazi v penazenke
  // memo := struktura, v ktorej si ukladame uz vypocitane hodnoty (memoizacia)
  
  // zakladny pripad o-ifujeme
  if (n == 0) {
    return 0;
  }
  // ak este nepozname odpoved, tak pocitame
  if (memo[n][p] == NEVIEM) {
    int naj = knapsack(K, n-1, p, memo); // ak nekupim i-tu kryptomenu
    int p1 = p - K[n-1].first;
    if (p1 >= 0) {
      int kupim = K[n-1].second + knapsack(K, n-1, p1, memo); // ak ju kupim
      if (kupim > naj) {
        naj = kupim;
      }
    }
    memo[n][p] = naj;
  }
  return memo[n][p];
}

int knapsack(vector<pair<int, int> >& K, int p) {
  // pomocna metoda, vytvori nam memo aby sme to nemuseli vytvarat explicitne
  int n = K.size();
  vector<vector<int> > memo(n+1, vector<int>(p+1, NEVIEM));
  return knapsack(K, n, p, memo);
}

Zvyšok riešenia vyzerá nasledovne:

#include <iostream>
#include <vector>
#include "knapsack.cpp"
using namespace std;

int main() {
  int n, q;
  cin >> n >> q;
  
  // nacitame pociatocne data o kryptomenach
  vector<pair<int, int> > K(n); // kryptomeny: first := cena, second := hodnota
  for (int i = 0; i < n; i++) {
    int c, h;
    cin >> c >> h;
    K[i] = make_pair(c, h);
  }
  
  // spracujeme kazdy z q nasledujucich dni
  for (int qi = 0; qi < q; qi++) {
    
    // zmena ceny kryptomeny
    int k, b;
    cin >> k >> b;
    k--;
    K[k].first = b;
    
    // Jemkova navsteva
    int l, r, p;
    cin >> l >> r >> p;
    l--;
    vector<pair<int, int> > podzoznam(K.begin() + l, K.begin() + r);
    int vysl = knapsack(podzoznam, p);
    cout << vysl << "\n";
  }
  
  return 0;
}

Na druhej strane, nájdenie optimálneho nákupu bude pomalé: robíme knapsack na \(n\) kryptomenách, a máme vo vrecku najviac \(P\) peňazí. Toto potrvá \(O(n \cdot P)\), a keďže máme \(q\) otázok, celková časová zložitosť bude až \(O(n \cdot P \cdot q)\).

Za toto riešenie sa dalo získať \(2\) body. Veď hrubú silu ste si mohli naprogramovať už v pôvodnej úlohe…

Rozšírenie pôvodnej úlohy? Nie…

Kto ale skúšal riešenie v duchu “upravím vzorák pôvodnej úlohy”, zistil, že to nie je také ľahké¹. Problém robia zmeny hodnôt kryptomien, ktoré nevieme vykonať efektívne. V štruktúrach, ktoré využívame na riešenie pôvodnej úlohy, by sa toho menilo príliš veľa.

Nie všetko je ale stratené—netreba zabudnúť na to, že obmedzenia tejto úlohy sú iné. Možno teda existuje úplne iné riešenie, ktoré nebuduje na riešení pôvodnej úlohy.

Jemko má nejako málo peňazí… náhoda?

Všimnime si, že Jemko má pri sebe vždy najviac \(50\) peňazí, čo je výrazne menej ako limit v pôdovnej úlohe (kde bol \(2000\)). Nevedeli by sme to nejako využiť?

Predstavme si, že Jemko by mal na výber iba z kryptomien ceny \(1\). Určite sa mu oplatí kupovať od najhodnotnejších kryptomien. Navyše, kedže každá kryptomena stojí \(1\) peniaz a Jemko má pri sebe nanajvýš \(P\) peňazí, kúpi nanajvýš \(P\) z týchto kryptomien.

Toto pozorovanie vieme zovšeobecniť: spomedzi kryptomien ceny \(c\) stačí Jemkovi pri nákupe uvažovať iba najhodnotnejších \(\lfloor \frac{P}{c} \rfloor\) ² z nich. Viac ich určite nekúpi, lebo potom by minul viac peňazí, ako má pri sebe.

To nám ale výrazne zužuje výber. Aj keby Jemko dovidel na \(300\,000\) kryptomien, stačí mu pri nákupe uvažovať dokopy iba

\[\lfloor \frac{P}{1} \rfloor + \lfloor \frac{P}{2} \rfloor + \ldots + \lfloor \frac{P}{P} \rfloor\]

kryptomien, čo je asymptoticky \(O(P \log P)\). Dôkaz tohto odhadu presahuje rámec tohto vzoráku, záujemcom ale odporučím túto stránku.

Nemusíme byť ale matematický mágovia na to, aby sme zistili, že onen súčet je dosť malý. Pre \(P = 50\) ho vieme zrátať jednoduchým skriptom:³

def sucet(p):
  """Vypocita nasledovny sucet: p/1 + p/2 + ... + p/2, pricom zlomky
  zaokruhli nadol."""
  vysl = 0
  for i in range(1, p+1):
    vysl += p // i
  return vysl

print(sucet(50))

Z čoho dostaneme, že sa Jemkovi stačí v našich testovacích prípadoch pozerať vždy na najviac \(207\) kryptomien. To je výrazne menej, ako keby sa pozeral na všetkých potenciálne až \(300\,000\) kryptomien.

Lepšie riešenie

Ako pomocou vyššie uvedeného tvrdenia možno urýchliť riešenie hrubou silou? Namiesto toho, aby sme pri knapsacku uvažovali všetky kryptomeny, na ktoré Jemko dovidí, stačí uvažovať len niekoľko málo z nich. Konkrétne, každej cenovej kategórie \(c\) uvažujeme len \(\lfloor \frac{P}{c} \rfloor\) najhodnotnejších kryptomien. Pre každú cenu vieme tento zoznam zostrojiť jednoducho pomocou minimovej haldy: vložíme kryptomenu do haldy, a ak je v halde priveľa prvkov, vyhodíme z nej najmenej hodnotnú kryptomenu.

// vyber.cpp

#include <vector>
#include <queue>
using namespace std;

void vyber (int l, int r, int p, vector<pair<int, int> >& K, vector<pair<int, int> >& vysl) {
  /** Vyberie zo zoznamu kryptomien 'K' tie, ktore su relevantne pre otazku:
   * "Ako mam nakupit v intervale [l, r) za p penazi?" Tieto relevantne kryptomeny
   * ulozi do 'vysl'. */
  vector<priority_queue<int, vector<int>, greater<int> > > haldy(p);
  for (int i = l; i < r; i++) {
    int c = K[i].first;   // cena kryptomeny
    if (c > p) {
      continue;
    }
    int h = K[i].second;  // hodnota kryptomeny
    int ci = c - 1;       // index do zoznamu hald
    haldy[ci].push(h);
    if (haldy[ci].size() * c > p) {
      haldy[ci].pop();
    }
  }
  for (int ci = 0; ci < p; ci++) {
    while (!haldy[ci].empty()) {
      int h = haldy[ci].top();
      haldy[ci].pop();
      vysl.push_back(make_pair(ci + 1, h));
    }
  }
}

Zlúčením všetkých \(P\) háld dostaneme zoznam všetkých kryptomien, na ktoré má zmysel sa pozerať. Potom spustíme knapsack algoritmus, ale iba na kryptomenách v tomto zozname.

#include <iostream>
#include <vector>
#include "knapsack.cpp"
#include "vyber.cpp"
using namespace std;

int main() {
  int n, q;
  cin >> n >> q;
  
  // nacitame pociatocne data o kryptomenach
  vector<pair<int, int> > K(n); // kryptomeny: first := cena, second := hodnota
  for (int i = 0; i < n; i++) {
    int c, h;
    cin >> c >> h;
    K[i] = make_pair(c, h);
  }
  
  // spracujeme kazdy z q nasledujucich dni
  for (int qi = 0; qi < q; qi++) {
    
    // zmena ceny kryptomeny
    int k, b;
    cin >> k >> b;
    k--;
    K[k].first = b;
    
    // Jemkova navsteva
    int l, r, p;
    cin >> l >> r >> p;
    l--;
    vector<pair<int, int> > podzoznam;
    vyber(l, r, p, K, podzoznam);
    int vysl = knapsack(podzoznam, p);
    cout << vysl << "\n";
  }
  
  return 0;
}

Časová zložitosť na jeden nákup sa nám zmenšila na \(O(n \log P + P^2 \log P)\): na zostrojenie zoznamu relevantných kryptomien musíme prejsť \(O(n)\) kryptomien, a pri každej strávime \(O(\log P)\) času na haldu⁴. Následný knapsack trvá \(O(P \log P \cdot P)\), pretože máme \(O(P \log P)\) vecí a \(P\) peňazí.

Toto riešenie si vyslúžilo \(6\) bodov. Jeho najpomalšou časťou je konštrukcia zoznamu relevantných kryptomien. To robíme jednoducho (ale pomaly) tak, že prejdeme všetky kryptomeny, na ktoré Jemko dovidí.

Vzorové riešenie

V úlohe sa často pýtame na nejaké intervaly, a tak by nás hneď mohol napadnúť intervalový strom. Nevedeli by sme ho tu nejako využiť?

Avšak, priamočiare využitie, kde by sme si v každom intervale pamätali knapsack na tom intervale, nestačí. Problém je so spájaním viacerých podknapsackov do jedného—nejde to robiť efektívne.⁵

Avšak my máme niečo lepšie. Vieme, že nám stačí uvažovať iba niekoľko málo kryptomien z každej ceny. Možno by sme si vedeli pamätať túto informáciu vo vrcholoch stromu.

V každom vrchole si budeme pre každú cenu pamätať zoznam relevantných kryptomien. Navyše budeme mať tieto zoznamy utriedené podľa hodnôt.

Teraz nás zaujímajú dve veci. Po prvé, čo má byť v listoch? To je ľahké: list obsahuje iba jedinú kryptomenu. Nech jej cena je \(c\), potom zoznam pre cenu \(c\) obsahuje túto kryptomenu, a ostatný zoznamy sú prázdne.

Ďalej, dajú sa tieto zoznamy efektívne spočítať v nejakom vrchole, ak ich už máme pre jeho synov? Dajú. Postupujeme podobne ako pri mergesorte. Pri zostrojovaní zoznamu pre cenu \(c\) opakujeme nasledovnú úvahu:

• Ktorý prvok ceny \(c\) môže byť najväčší? Zrejme to bude buď najväčší prvok ceny \(c\) v ľavom synovi, alebo v pravom synovi. Pre oboch synov ale máme usporiadaný zoznam prvkov s touto cenou. Bude to teda prvý prvok niektorého z týchto zoznamov.

• Porovnáme tieto prvé prvky, zoberieme väčší z nich a umiestnime ho na prvé voľné miesto v našom zozname.

• Opakujeme so zvyškom, pričom vybratý prvok ďalej neberieme v úvahu. Za najväčší prvok v tom synovi teda budeme považovať druhý prvok, keď sa vyberie ten tak potom tretí, …

// zluc.cpp

#pragma once // aby sa to pri kompilacii include-lo len raz

#include <vector>
using namespace std;

#define MAX_P 50
#define ZLA_HODNOTA -1

struct Vyber {
  // Struktura odrzujuca najlepsich 50/50 kariet ceny 50,
  // najlepsich 50/49 kariet ceny 49,
  // ...,
  // najlepsich 50/2 kariet ceny 2,
  // najlepsich 50 kariet ceny 1.
  
  vector<vector<int> > V; // V[i] obsahuje zoznam pre cenu <i>, V[0] sa nepouziva
  
  Vyber() : V(MAX_P + 1) {}
  
  Vyber(int c, int h) : V(MAX_P + 1) {
    // zakladny Vyber, obsahuje len 1 kartu s cenou <c> a hodnotou <h>.
    V[c].push_back(h);
  }
  
  Vyber(Vyber& a, Vyber& b) : V(MAX_P + 1) {
    // zluci <a> a <b> do jedneho
    for (int ci = 1; ci <= MAX_P; ci++) {
      int ai = 0, bi = 0;
      
      // zoberieme najhodnotnejsich MAX_P/ci z <a> a z <b> (s cenou <ci>)
      for (int j = 0; j < MAX_P/ci; j++) {
        int ah = (ai < (int)a.V[ci].size() ? a.V[ci][ai] : ZLA_HODNOTA);
        int bh = (bi < (int)b.V[ci].size() ? b.V[ci][bi] : ZLA_HODNOTA);
        
        // ale ak uz nie su ani v <a> ani v <b>, tak skonci
        if (ah == ZLA_HODNOTA && bh == ZLA_HODNOTA) {
          break;
        }
        
        int h;
        if (ah > bh) {
          h = ah;
          ai++;
        }
        else {
          h = bh;
          bi++;
        }
        V[ci].push_back(h);
      }
    }
  }  
};

Vyber zluc(vector<Vyber>& A) {
  // Zluci vsetky Vybery vo <V> do jedneho, v ktorom su z kazdej ceny najhodnotnejsie meny.
  // Predpokladame, ze sme dostali aspon 1 Vyber vo <V>...
  if (A.size() == 1) {
    return A[0];
  }
  Vyber vysl(A[0], A[1]);
  for (int i = 2; i < (int)A.size(); i++) {
    vysl = Vyber(vysl, A[i]);
  }
  return vysl;
}

void do_pola(Vyber& a, vector<pair<int, int> >& vysl) {
  // Do vektora <vysl> ulozi obsah Vyberu <v> (vo forme dvojic <cena kryptomeny, jej hodnota>).
  // Na toto pole potom staci zavolat knapsack funkciu.
  vysl.clear();
  for (int ci = 1; ci <= MAX_P; ci++) {
    for (auto h : a.V[ci]) {
      vysl.push_back({ci, h});
    }
  }
}

Aká je časová zložitosť tohto predpočítania? Zlučovanie dvoch intervalov do jedného trvá \(O(P \log P)\), a vrcholov v strome je \(O(n)\). Bude teda trvať \(O(n \cdot P \log P)\).

// intervalac.cpp

#pragma once // aby sa to pri kompilacii include-lo len raz

#include <vector>
#include "zluc.cpp"
using namespace std;

struct Intervalac {
  vector<Vyber> A;
  int m;
  
  Intervalac(vector<pair<int, int> >& V) {
    // inicializujeme intervalac: kryptomeny s povodnymi cenami a hodnotami <V>
    int n = V.size();
    m = 1;
    while (m < n) m *= 2;
    
    A.resize(2*m);
    // A[0] sa nepouziva
    // A[1...m-1] su intervaly dlzok 2 a viac
    // A[m...2m-1] su intervaly dlzky 1
    for (int i = 0; i < n; i++) {
      A[m+i] = Vyber(V[i].first, V[i].second);
    }
    for (int i = m-1; i > 0; i--) {
      A[i] = Vyber(A[2*i], A[2*i+1]);
    }
  }
  
  void zmen(int k, int b, int h) {
    // zmen cenu <k>-tej kryptomeny na <b> a hodnotu na <h>, pricom <k> cislujeme od 0
    int kde = m+k;
    A[kde] = Vyber(b, h);
    kde /= 2;
    while (kde > 0) {
      A[kde] = Vyber(A[2*kde], A[2*kde+1]);
      kde /= 2;
    }
  }
  
  int L, R;
  void pomocny_rozloz(int l, int r, int i, vector<Vyber>& vysl) {
    // Rekurzivne rozlozi interval <l; r) na podintervaly a ich Vybery
    // prida do <vysl>. <l>, <r> a <i> su viazane: posledne menovane
    // udava, v ktorom vrchole intervalacu sme, a prve dve definuju
    // interval. Iba intervaly, ktore zodpovedaju nejakemu vrcholu,
    // su povolene.
    if (l >= L && r <= R) {
      vysl.push_back(A[i]);
      return;
    }
    if (l >= R || r <= L) {
      return;
    }
    int s = (l+r)/2;
    pomocny_rozloz(l, s, 2*i, vysl);
    pomocny_rozloz(s, r, 2*i+1, vysl);
  }
  
  void rozloz(int l, int r, vector<Vyber>& vysl) {
    // Rozlozi interval <l; r) na podintervaly, a ich Vybery da do <vysl>.
    // Z toho potom vieme vycitat, ktore kryptomeny v useku <l; r) su tie
    // podstatne (dostatocne hodnotne).
    L = l;
    R = r;
    pomocny_rozloz(0, m, 1, vysl);
  }
};

Ako zistiť zoznam relevantných kryptomien pri nákupe? Interval rozbijeme na \(O(\log n)\) intervalov zo stromu, a tie zlúčime. To potrvá \(O(\log n \cdot P \log P)\), a následné vyriešenie knapsacku bude trvať \(O(P \cdot P \log P)\). Časová zložitosť jedného nákupu je teda \(O(P \log P \cdot (P + \log n))\).

Ako prepočítať intervalový strom, keď sa zmení hodnota kryptomeny? Keď vieme zlučovať intervaly, nie je problém: zmeníme príslušný vrchol-list⁶ a všetkých jeho predkov ⁷ prepočítame. Tých je iba \(O(\log n)\), časová zložitosť jednej úpravy je teda \(O(\log n \cdot P \log P)\).

#include <iostream>
#include <vector>
#include "knapsack.cpp"
#include "zluc.cpp"
#include "intervalac.cpp"
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  int n, q;
  cin >> n >> q;
  
  // nacitame pociatocne data o kryptomenach
  vector<pair<int, int> > K(n); // kryptomeny: first := cena, second := hodnota
  for (int i = 0; i < n; i++) {
    int c, h;
    cin >> c >> h;
    K[i] = make_pair(c, h);
  }
  Intervalac I(K);
  
  // spracujeme kazdy z q nasledujucich dni
  for (int qi = 0; qi < q; qi++) {
    
    // zmena ceny kryptomeny
    int k, b;
    cin >> k >> b;
    k--;
    if (b != K[k].first) {
      K[k].first = b;
      I.zmen(k, b, K[k].second);
    }
    
    // Jemkova navsteva
    int l, r, p;
    cin >> l >> r >> p;
    l--;
    
    // najdeme iba tie podstatne kryptomeny
    vector<Vyber> vybery;
    I.rozloz(l, r, vybery);
    Vyber podvyber = zluc(vybery);
    vector<pair<int, int> > podzoznam;
    do_pola(podvyber, podzoznam);
    
    int vysl = knapsack(podzoznam, p);
    cout << vysl << "\n";
  }
  
  return 0;
}

Celková časová zložitosť je

\[O(P \log P \cdot (n + (P + \log n) \cdot q)),\]

čo síce nevyzerá pekne, ale aspoň je to dosť málo. Toto riešenie si vyslúžilo plných \(8\) bodov.

Pomocou lazy-loadingu by sme sa vedeli vyhnúť zdĺhavému predpočítaniu a dosiahnuť tak o chlp lepšiu časovú zložitosť. Na plný počet bodov sme to ale nevyžadovali.