Zadanie

KSPáci radi čítajú a keďže veľa času trávia na Matfyze, čítajú hlavne tam. A ako KSPáci postupne starli a odchádzali do veľkého sveta, ich knihy zostali. No kníh stále pribúdalo a čoskoro zaplnili väčšinu políc, poličiek, skríň a zásuviek.

Po tom, čo Askara pri hľadaní zošívačky zasypala knižná séria Moderný design pre Windows 95, sa KSPáci rozhodli, že sa kníh zbavia. Vyhadzovať knihy je škoda, preto dumali, dumali, až vydumali skvelý nápad – predajú ich! Tak sa aj stalo, že sa o týždeň konal veľký výpredaj. Uložili knihy do veľkej veže a nechali Matúša, nech predáva.

Matúš je šikovný chlapec a vie, ako sa zákazníci správajú. Zákazníci sú pomerne leniví, nechce sa im prehrabovať v kope a nedajbože robiť rozhodnutia. Len čo prídu za Matúšom, pozrú sa aká kniha je na vrchu kopy, spýtajú sa Matúša, koľko kniha stojí a ak sú s cenou spokojní, kúpia si ju.

Matúš im samozrejme ponúkne najvyššiu cenu, akú sú ochotní zaplatiť. Jednak aby čo najviac zarobil a dvak aby sa zbavil všetkých kníh. Ponúknutá najvyššia cena je jednoducho súčin bohatosti zákazníka a skutočnej hodnoty knihy.

Avšak, bola by veľká škoda, keby si bohatí zákazníci kúpili lacnú knihu a chudobní zákazníci kúpili veľmi hodnotnú knihu, lebo by KSP (a Matúš) nič nezarobilo. Tak mu v hlave vznikol ďalší skvelý nápad. Môže trocha ovplyvňovať, aké knihy si zákazníci kúpia. Veď má predsa dve ruky! Keď napríklad chce, aby si zákazník kúpil tretiu knihu zhora, vie chytiť vrchnú do ľavej ruky a ďalšiu do pravej ruky. No nie je to génius?

Deň sa skončil, všetky knihy sa predali a Matúš teraz rozmýšľa, či predával optimálne. Od vás chce preto vedieť, koľko najviac peňazí mohol zarobiť.

Úloha

Máme \(n\) kníh, ktoré si príde kúpiť \(n\) kupcov. Na vstupe sú zadané hodnoty kníh \(h_1 \dots h_n\) (od vrchu kopy nadol) a bohatosti kupcov \(b_1 \dots b_n\) (v poradí, v ktorom prichádzajú do obchodu).

Každý kupec si kúpi práve jednu z vrchných troch kníh, pričom \(i\)-ty kupec zaplatí za \(j\)-tu knihu \(b_i \cdot h_j\) peňazí.

Koľko najviac peňazí vieme zarobiť, ak ponúkame zákazníkom knihy optimálne?

Formát vstupu

V prvom riadku je číslo \(n\) – počet kníh.

V druhom riadku je \(n\) čísel \(h_i\) – hodnoty kníh, \(1\leq h_i\leq 1\,000\).

V treťom riadku je \(n\) čísel \(b_i\) – bohatosti kupcov, \(1\leq b_i\leq 1\,000\).

Pre jednotlivé sady vstupov platia nasledovné obmedzenia na počet kníh.

Číslo sady 1 2 3 4 5 6 7 8
Maximálne \(n\) 5 10 20 40 100 200 400 500

Formát výstupu

Vypíšte jeden riadok a v ňom jedno celé číslo – najväčšiu sumu, za ktorú vieme knihy predať.

Príklad

Input:

4
16 6 2 10
3 8 12 9

Output:

336

Prvému človeku s bohatosťou \(3\) Matúš zodvihne dve knihy, vezme knihu s hodnotou \(2\) a zaplatí na ňu \(6\). Druhému zodvihne jednu, čiže si vezme knihu \(6\) za \(48\), tretiemu nezodvihne žiadnu a posledný už nemá na výber.

Najskôr sa pozrieme na jednoduchšie algoritmy, ktoré vás mohli pri riešení tejto úlohy napadnúť, následne si predstavíme dynamické programovanie a nakoniec v ňom nájdeme malý trik ku vzorovému riešeniu.

Jednoduché algoritmy

Prvá vec, ktorá nás napadne pri ľubovoľnej úlohe, je brute force. Ten však bude príliš pomalý. Navyše pri tejto úlohe je aj jeho implementácia netriviálna, takže je jednoduchšie sa zamyslieť nad rýchlejším riešením.

Ďalší jednoduchý prístup sú greedy algoritmy. No či už vyberáme pre zákazníka najlacnejšiu alebo najdrahšiu knihu, dá sa nájsť protipríklad, na ktorom nezvolíme optimálnu stratégiu. Poďme sa teda pozrieť na myšlienkovo náročnejšie riešenie, ktoré ale už bude korektné.

Dynamické programovanie

Táto úloha sa dá celkom príjemne riešiť pomocou dynamického programovania – dynamiky. Dynamika je algoritmus, v ktorom zo stavov, ktoré už poznáme, postupne počítame ďalšie, až kým sa nedostaneme ku výsledku.

V tejto úlohe bude naším stavom počet už predaných kníh a vrchné tri knihy na kope. Informácia, ktorú pre tento stav chceme vedieť, je maximum peňazí ktoré vieme mať vtedy zarobených. Medzi týmito stavmi sa presúvame predajom kníh. Pri každom predaji predáme jednu knihu (konkrétneho zákazníka vieme určiť z počtu predaných kníh) a namiesto nej do trojice známych kníh dáme ďalšiu knihu z kopy. Týmto nám vznikol nový stav. Ak už sme taký stav niekedy dosiahli, tak si porovnáme zarobené peniaze a zapamätáme si maximum.

Implementovať to budeme pomocou štvorrozmerného poľa, kde jedna súradnica bude počet predaných kníh, ďalšími tromi budú vrchné tri knihy na kope, a hodnota jedného políčka budú peniaze zarobené v danom stave.

Samotný algoritmus bude postupne prechádzať všetky políčka (stavy). Pre dané políčko si vypočíta stav, ktorý mu vznikne predajom prvej knihy, a na políčko tohto nového stavu skúsi uložiť peniaze, ktoré by takto zarobil. No čo ak sa na toto políčko už dostal predtým? Preto sa najskôr pozrie, či už na danom políčku nie je uložená väčšia hodnota, ako by zapisoval. Ak áno, tak nespraví nič, pretože by prepisoval optimálnejšie riešenie. V opačnom prípade zapíše novú hodnotu. To isté zopakuje pre druhú a tretiu knihu.

Keďže si pamätáme štvorrozmerné pole, kde každá zo súradníc môže mať veľkosť až \(n\), pamäťová zložitosť bude \(O(n^4)\). A keďže všetky tieto políčka počas výpočtu prechádzame, tak aj časová zložitosť bude \(O(n^4)\).

Už máme skoro vzorové riešenie, ale \(n^4\) je predsa len príliš pomalé a na najväčších vstupoch nestíha. Skúsme teda naše riešenie trochu zoptimalizovať.

Zlepšenie zložitosti

Pozrime sa bližšie na predaj jednej knihy. Zákazník príde, kúpi si jednu z vrchných troch kníh a odíde. Keďže sa jedna z vrchných troch kníh zobrala, štvrtá kniha z kopy sa “presunula” na tretie miesto. Toto sa deje pri každej kúpe knihy1. Treťou knihou na kope bude teda po ľubovoľných \(k\) nákupoch vždy \(k+3\)-tia v pôvodnej kope.

Nám si teda stačí pamätať len túto tretiu knihu a celkový počet kníh si z nej budeme vedieť ľahko. Celkovo teda máme tri vnorené cykly, čo nám dáva časovú a aj pamäťovú zložitosť \(O(n^3)\).

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

#define MIN_INFTY -56789

int n, B[542], H[542];
int data[542][542][542];

int main(){

    cin >> n;   //načítame vstup
    for(int i = 0; i<n; ++i) cin >> H[i];
    for(int i = 0; i<n; ++i) cin >> B[i];
    
    H[n] = H[n+1] = H[n+2] = 0;
    B[n] = B[n+1] = H[n+2] = 0;
    //vytvoríme si sentinely, t.j. hranice na okraji našich hodnôt, aby sme
    //nemuseli ošetrovať hraničné prípady. V tomto prípade doplníme hodnoty o
    //tri bezcenné knihy na spodku kopy a troch švorc kupcov na konci. Je
    //ľahké vidieť, že v každom optimálnom riešení si títo traja kupci vezmú
    //tieto tri knihy, a nám to ušetrí kopu if-ov

    for(int i = 0; i<2; ++i) {  //inicializujeme si pole
        for(int j = 0; j<n+2; ++j) {
            for(int k = 0; k<(n+2); ++k) {
                data[i][j][k] = MIN_INFTY;
            }
        }
    }
    
    data[0][1][2] = 0; //počiatočný stav
    
    for(int i=0; i<n+1; i++){   //prejdeme cez jednotlivé stavy
        for(int j=i+1; j<n+2; j++){
            for(int k=j+1; k<n+3; k++){
                int current = data[i][j][k];
                data[j][k][k+1] = max(data[j][k][k+1], current + H[i]*B[k-2]);
                data[i][k][k+1] = max(data[i][k][k+1], current + H[j]*B[k-2]);
                data[i][j][k+1] = max(data[i][j][k+1], current + H[k]*B[k-2]);
            }
        }
    }

    cout<<data[n][n+1][n+2]<<endl;  //vypíšeme stav, kde nám ostávajú nami
                                    //doplnené bezcenné knihy
}

Vzorové riešenie

Pamäťová zložitosť \(O(n^3)\) však stále nestačí na plný počet bodov, skúsme ju teda trochu orezať.

Pri predchádzajúcej optimalizácií sme využili fakt, že tretia kniha na kope sa nám pri každom predaji zmení na tú pod ňou. Tento fakt nám ale dáva viac, než sme využili. Vďaka tomu totiž vieme, že zo stavov, kde tretia kniha je \(k\)-ta sa vieme dostať jedným predajom len do stavov, kde tretia kniha je \(k+1\)-vá. A naopak, do stavov kde tretia kniha je \(k\)-ta sa vieme dostať len zo stavov, kde tretia kniha je \(k-1\)-vá. Keďže potrebujeme len stavy \(k-1\), nemusíme si pamätať všetky predchádzajúce. Stačí nám, keď si v jednom riadku poľa budeme pamätať už vypočítané stavy a do druhého budeme zapisovať novovypočítané stavy. No a keď ich dorátame, tak nám stačí len vymeniť riadky a počítať ďalej.

Tým, že si v jednom momente pamätáme stavy len pre dva prípady tretej knihy na kope, sme práve odobrali ďalšie \(n\) z pamäťovej zložitosti. Pamäťová zložitosť teda bude \(O(n^2)\).

#include<iostream>
#include<algorithm>
#include<vector>


using namespace std;

#define MIN_INFTY -1023456789

int n, B[542], H[542];
int data[2][542][542];  
//Prvá súradnica nám bude reprezantovať tretiu knihu v kope.


int main(){
    cin >> n;
    for(int i = 0; i<n; ++i) cin >> H[i];
    for(int i = 0; i<n; ++i) cin >> B[i];
    
    for(int i = 0; i<2; ++i) {
        for(int j = 0; j<n+2; ++j) {
            for(int k = 0; k<n+2; ++k) {
                data[i][j][k] = MIN_INFTY;
            }
        }
    }
    
    data[0][0][1] = 0; //Inicializujeme si počiatočný stav

    for(int i = 0; i<n; ++i) {
        for(int j = 0; j<n+2; ++j) {
            for(int k = 0; k<n+2; ++k) {
                int current = data[i%2][j][k];
                data[(i+1)%2][j][k]   = max(data[(i+1)%2][j][k], current+B[i]*H[i+2]);
                data[(i+1)%2][i+2][k] = max(data[(i+1)%2][i+2][k], current+B[i]*H[j]);
                data[(i+1)%2][j][i+2] = max(data[(i+1)%2][j][i+2], current+B[i]*H[k]);
                //simulujeme predaj postupne tretej, prvej a druhej knihy v kope
            }
        }
    }
    cout << max(data[n%2][n][n+1], data[n%2][n+1][n]) << endl;
}


  1. Až na okrajový prípad, keď sú na kope menej ako štyri knihy.

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ť.