8. Ako Jemo Etku spoznal vzorové riešenie

3 2
2 2
3 3
2 2
1 3 4
1 2 4

4
3

3 2
2 2
3 5
2 2
1 3 4
1 2 4

5
5

Potom, ako ste si spolu s Jemom prešli strastiplnou cestou na druhú stranu kopca, našli slušné bývanie a napriek obrovskému hladu stretli jeho vyvolenú, ste dostali neľahkú úlohu. Mnohým z vás však táto úloha musela prísť povedomá. A tak stačilo spomenúť si na jej riešenie a následne ho trošku vytúniť, aby riešilo aj túto úlohu.

Knapsack

Áno, táto úloha bola len jemné zovšeobecnenie úlohy, ktorá je vo svete známa pod názvom knapsack problem. Zadanie znie nasledovne: “Máme \(n\) kryptomien, pre každú z nich poznáme jej cenu v Tesku a jej hodnotu na trhu. Akú najväčšiu hodnotu vieme nakúpiť za \(p\) peňazí?”

Túto úlohu vyriešime dynamickým programovaním. Vypočítame si dvojrozmerné pole, kde v \(D[i][j]\) je uložená najväčšia hodnota, akú vieme nakúpiť, ak máme k dispozícii \(j\) peňazí a môžeme nakupovať len prvých \(i\) typov kryptomien. Potom odpoveď na našu otázku je uložená v \(D[n][p]\).

Ako vypočítame hodnoty v jednotlivých políčkach poľa? Predstavme si, že máme \(j\) peňazí a nakupujeme z prvých \(i\) typov kryptomien. Aké sú možnosti pre \(i\)-tu kryptomenu? Buď ju nekúpime a výsledok je rovnaký, ako keď nakupujeme iba z prvých \(i-1\) kryptomien. Alebo ju kúpime (samozrejme, iba ak máme na to dosť peňazí). Vtedy chceme kúpiť najväčšiu hodnotu z prvých \(i-1\) kryptomien, pričom už máme k dispozícii len \(j-cena[i]\) peňazí.

Teda pokiaľ máme dosť peňazí na kúpenie \(i\)-tej kryptomeny (\(j \geq cena[i]\)), tak platí \[D[i][j] = \max (D[i-1][j], D[i-1][j-cena[i]] + hodnota[i])\text{.}\] Inak \(D[i][j] = D[i-1][j]\). Základný prípad je jednoduchý, keďže za \(0\) peňazí a ani z \(0\) kryptomien si nič nekúpiš. Vieme teda, že \(D[0][j] = D[i][0] = 0\).

Priamočiare využitie

Toto vieme využiť v našej úlohe tak, že vždy, keď príde otázka, zrátame si výsledok knapsacku pre kryptomeny od \(l\) po \(r\) a vypíšeme odpoveď. Akú to má celé časovú zložitosť? Pre každú otázku potrebujeme zrátať celé dvojrozmerné pole knapsacku odznova. Toto pole môže mať v najhoršom prípade veľkosť až \(n \times p\). Teda celková časová zložitosť je \(O(q \cdot n \cdot P)\), kde \(P\) je najväčšie \(p_i\).

#include <bits/stdc++.h>

using namespace std;

int n,q,l,r,b;
vector<int> c,h;

int main() {
  ios_base::sync_with_stdio(false);
  cin>>n>>q;
  c.resize(n);h.resize(n);
  for(int i=0;i<n;i++)cin>>c[i]>>h[i];
  while(q--){
    cin>>l>>r>>b;l--;
    vector<vector<int> > D(r-l+1, vector<int>(b+1, 0));
    for(int i=1;i<=b;i++){
      for(int j=1;j<D.size();j++){
        //skus kupit j+l-ty typ
        D[j][i]=D[j-1][i];
        if(i>=c[j+l-1])D[j][i]=max(D[j][i], D[j-1][i-c[j+l-1]]+h[j+l-1]);
      }
    }
    cout <<D.back().back()<<endl;
  }
  return 0;
}

Vzorové riešenie

Všimnime si, že keď zrátame knapsack pre nejaký interval kryptomien (od \(l\) po \(r\)), tak musíme zrátať celú tabuľku \(D\). Zaujímavé je ale to, že v \(i\)-tom riadku tabuľky \(D\) vlastne uvažujeme len prvých \(i\) kryptomien (kryptomeny od \(l\) po \(l+i-1\)). A teda keď už máme vyrátané \(D\), tak máme odpovede zrátané aj pre každý prefix tohto intervalu. Teda pre každý interval tvaru \(\langle l; l+i \rangle\), kde \(0 \leq i \leq r-l\). Pokiaľ zrátame všetky tieto knapsacky odzadu, tak máme dokonca zrátaný knapsack aj pre každý jeho sufix (intervaly tvaru \(\langle l+i; r \rangle\)).

Postavme si teraz nad našimi kryptomenami strom s rovnakou štruktúrou, ako má intervalový strom – teda binárny strom, kde je každému vrcholu priradený nejaký interval, pričom koreňu je priradené celé pole, každému z jeho synov jedna polovica poľa, ich synom štvrtiny poľa atď. V každom vrchole nášho stromu zrátajme knapsack na intervale kryptomien, ktorý tento vrchol pokrýva, v oboch smeroch.

Akú výhodu nám to dá? Ľubovoľný interval sa teraz dá rozdeliť na dve časti (o chvíľu si ukážeme ako), pričom pre obe z nich už máme knapsack predrátaný niekde v našom strome. Ak by sme vedeli, koľko peňazí máme minúť v prvej a koľko v druhej časti, odpoveď na otázku by sme zrátali v konštantom čase sčítaním vhodných dvoch čísel, ktoré už máme predpočítané. To síce nevieme, ale môžeme vyskúšať všetky možnosti, ktorých je \(p+1\). Poďme si teda zhrnúť naše riešenie.

Predstavme si, že nám príde otázka, že chceme výsledok knapsacku na intervale od \(l\) po \(r\). Skúsme nájsť nejaké intervaly v intervaláči, ktoré nám v tomto pomôžu. Začnime v koreni. Pokiaľ celý náš hľadaný interval leží len v pravom alebo len v ľavom synovi, tak nás vlastne tá druhá časť intervaláču nezaujíma a môžeme sa presunúť do syna, v ktorom sa náš interval nachádza. Toto opakujeme až dôjdeme do vrchola, kde toto opakovať nemôžeme. To môže znamenať, že sme v liste, vtedy je hľadaný interval dĺžky \(1\) a odpoveď je jednoduchá. Buď si vieme dovoliť kúpiť kryptomenu a odpoveď je jej hodnota, alebo je odpoveď \(0\). Iná možnosť je, že časti nami hľadaného intervalu ležia v oboch synoch. Dokonca vieme, že náš hľadaný interval je vlastne zlepením nejakého sufixu ľavého syna a nejakého prefixu pravého syna. Toto už ale máme predpočítané, teda jediné, čo ostáva, je nakombinovať odpoveď z týchto dvoch intervalov. Jediný problém je, že nevieme, koľko peňazí chceme minúť v ľavom synovi a koľko v pravom. Tak to urobíme jednoducho—keďže dokopy chceme minúť \(p\) peňazí, tak vyskúšame všetky možnosti, ako rozdeliť tieto peniaze do synov. Potom už len zoberieme maximum a vypíšeme.

Ako sme teda zlepšili časovú zložitosť? Najprv si predpočítame celý intervalový strom. Všimnime si, že na každej úrovni tohto stromu zrátame niekoľko knapsackov, dokopy pre \(n\) prvkov s tým, že minieme maximálne \(p\) peňazí. Strom má \(\log n\) úrovní, a teda zrátať celý strom vieme v čase \(O(n \cdot p \cdot \log n)\). Pri spracovávaní konkrétnej otázky najprv potrebujeme nájsť vhodný vrchol, pričom pri každom kroku tohto hľadania klesneme v hĺbke stromu o \(1\). Teda vrchol vieme nájsť v \(O(\log n)\), a na záver vyskúšame všetky možnosti rozdelenia peňazí do ľavého a pravého intervalu, čo bude trvať \(O(p)\). Celková časová zložitosť je teda \(O(n \cdot p \cdot \log n + q \cdot (\log n + p))\). Čo sa týka pamäťovej zložitosti, tak si musíme pamätať celý náš intervalový strom, čo je \(O(n \cdot p \cdot \log n)\).

#include <bits/stdc++.h>

using namespace std;

int n,q,l,r,b, maxP=2000;
vector<int> c,h;
vector<vector<vector<int> > > D,E;
void calculateKnapsnack(int vrchol, int odkial, int pokial) {
  D[vrchol].resize(pokial-odkial+1, vector<int>(maxP+1,0));
  E[vrchol].resize(pokial-odkial+1, vector<int>(maxP+1,0));
  for(int i=1;i<=maxP;i++){
    for(int j=1;j<D[vrchol].size();j++){
      D[vrchol][j][i]=D[vrchol][j-1][i];
      if(i>=c[j+odkial-1])D[vrchol][j][i]=max(D[vrchol][j][i], D[vrchol][j-1][i-c[j+odkial-1]]+h[j+odkial-1]);
    }
  }
  for(int i=1;i<=maxP;i++){
    for(int j=1;j<E[vrchol].size();j++){
      E[vrchol][j][i]=E[vrchol][j-1][i];
      if(i>=c[pokial-j])E[vrchol][j][i]=max(E[vrchol][j][i], E[vrchol][j-1][i-c[pokial-j]]+h[pokial-j]);
    }
  }
  if(pokial-odkial<2)return;
  int stred=(odkial+pokial)/2;
  calculateKnapsnack(2*vrchol, odkial, stred);
  calculateKnapsnack(2*vrchol+1, stred, pokial);
}

pair<int,int> najdivrchol(int vrchol, int odkial, int pokial){
  int stred=(odkial+pokial)/2;
  if(l>stred)return najdivrchol(2*vrchol+1, stred, pokial);
  if(r<stred)return najdivrchol(2*vrchol, odkial, stred);
  return {vrchol,stred};
}

int main() {
  ios_base::sync_with_stdio(false);
  cin>>n>>q;
  int listy=1;
  while(listy<n)listy*=2;
  D.resize(2*listy);
  E.resize(2*listy);
  c.resize(listy,0);h.resize(listy,0);
  for(int i=0;i<n;i++)cin>>c[i]>>h[i];
  //ulozene v poli [cislo vrchola v intervalaci][pocet spracovanych][pocet penazi]
  calculateKnapsnack(1,0,listy);
  while(q--){
    cin>>l>>r>>b;l--;
    pair<int,int> interval=najdivrchol(1,0,listy);
    int vsledok=0;
    for(int i=0;i<=b;i++){
      vsledok=max(vsledok, D[2*interval.first+1][r-interval.second][i]+E[2*interval.first][interval.second-l][b-i]);
    }
    cout <<vsledok<<endl;
  }
  return 0;
}