Zadanie
Táto úloha je podobná úlohe s pred dvoch kôl, Ako Jemo Etku spoznal. Rozdiel je v tom, že sa ceny kryptomien menia v čase, a sú iné obmedzenia na vstup.
Jemko sa ešte stále pokúša očariť Etku pri pulte s kryptomenami. Každý deň chodí do Teska a nakupuje kryptomeny čo najvýhodnejšie. Etkinu pozornosť sa mu ale zachytiť nedarí.
Prednedávnom ale spravil objav a hneď mu svitlo, kde by mohol byť problém—všimol si, že každý deň sa v Tesku zmení cena práve jednej kryptomeny. Háčik bol v tom, že doteraz predpokladal, že tieto ceny sú konštantné. Ak pri nákupe zoberie do úvahy tieto zmeny, tak jeho nákupy budú skutočne optimálne, a takúto optimálnosť si Etka určite všimne.
Úloha
V Tesku predávajú \(n\) kryptomien, ktoré sú vyložené na pulte v jednom dlhom rade. Každá kryptomena má nejakú cenu v obchode a nejakú hodnotu na trhu. Jemko bude obchod navštevovať nasledujúcich \(q\) dní. Na začiatku dňa sa zmení cena práve jednej kryptomeny, hodnoty ale zostávajú rovnaké.
Pretože Jemko chodí vždy večer, na pulte je vždy z každej meny už len \(1\) minca. Pre každú návštevu vieme, koľko má Jemko peňazí v peňaženke a odkiaľ pokiaľ vidí, a zaujíma nás odpoveď na otázku: “Akú najväčšiu hodnotu vie Jemko nakúpiť, ak si vyberá len medzi menami, na ktoré dovidí?”
Formát vstupu
Na prvom riadku vstupu sú dve celé čísla \(n\) a \(q\) oddelené medzerou: počet rôznych kryptomien a počet dní, počas ktorých Jemko navštívi Tesko. Kryptomeny sú číslované od \(1\) po \(n\).
Ďalší riadok je prázdny.
Nasleduje \(n\) riadkov, v každom sú dve medzerou oddelené celé čísla \(c_i\), \(h_i\): počiatočná cena \(i\)-tej kryptomeny v Tesku, a hodnota tejto kryptomeny na trhu.
Ďalší riadok je prázdny.
Na konci bude \(q\) riadkov popisujúcich udalosti v jednotlivých dňoch: Jemkove návštevy a zmeny cien v obchode. V každom riadku je pätica čísel \(k_i\), \(b_i\), \(l_i\), \(r_i\), \(p_i\) oddelených medzerou. Prvé dve čísla hovoria, že cena kryptomeny \(k_i\) sa na začiatku dňa zmení na \(b_i\). Posledné tri čísla hovoria, že Jemko má v peňaženke \(p_i\) peňazí a môže nakupovať kryptomeny od \(l_i\) po \(r_i\), vrátane.
Formát výstupu
Pre každú Jemkovu návštevu Teska vypíšte jeden riadok a v ňom jedno celé číslo: najväčšiu hodnotu, ktorú vie Jemko nakúpiť.
Hodnotenie
Pre jednotlivé sady vstupov platia nasledovné obmedzenia.
číslo sady | \(1\) | \(2\) | \(3\) | \(4\) |
---|---|---|---|---|
\(1 \leq n \leq\) | \(3\,000\) | \(30\,000\) | \(30\,000\) | \(300\,000\) |
\(1 \leq q \leq\) | \(3\,000\) | \(10\,000\) | \(10\,000\) | \(10\,000\) |
Vo všetkých vstupoch platia nasledovné obmedzenia pre ceny kryptomien a peňaženku: \(1 \leq c_i, b_i, p_i \leq 50\).
Pre hodnoty kryptomien platí \(0 \leq h_i \leq 10^6\).
Kryptomeny indexujeme od jednotky; platí teda \(1 \leq k_i \leq n\) a \(1 \leq l_i \leq r_i \leq n\).
Príklad
Input:
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
Output:
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é1. 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\) 2 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:3
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 haldu4. 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.5
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-list6 a všetkých jeho predkov 7 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.
Nie je nám známe žiadne riešenie na takéto motívy.↩
Symbol \(\lfloor x \rfloor\) označuje dolnú celú časť reálneho čísla \(x\), teda \(x\) zaokrúhlené nadol.↩
alebo aj pomocou WolframAlpha↩
Šikovné oko si všimne, že v skutočnosti zoznam vieme zostrojiť rýchlejšie, ako pomocou haldy.↩
Možno argumentujete, že v pôvodnej úlohe sme predsa použili intervalový strom. Zamyslite sa ale, či nebol nejaký divný. Napríklad, keď sme dostali nejaký interval, na koľko najviac vrcholov v strome sme ho rozdelili? Bolo to \(O(\log n)\), tak ako v obyčajných intervaláčoch?↩
reprezentujúci interval dĺžky \(1\)↩
reprezentujúce všetky ďalšie intervaly, ktoré kryptomenu obsahujú↩
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.