5. Letné nakupovanie vzorové riešenie

4 4 10 32
7 3 5 4
9 2 3 4
0 4
1 4
2 4
3 2

2

4 5 5 20
10 3 1 2
7 4 4 6
4 3
4 2
1 0
4 1
3 0

-1

Najprirodzenejším spôsobom ako sa dá celá úloha reprezentovať je zrejme grafom. Vrcholmi sú v tomto grafe obchody a chata, pričom hranami sú cesty medzi nimi. Grafová reprezentácia je výhodná najmä v tom, že na grafoch poznáme mnoho algoritmov.

Riešenie hrubou silou

Ak sa pýtame na najmenší čas, za ktorý sa dá nakúpiť \(p\) fixiek za cenu najviac \(c\), môžeme postupovať jednoduchým spôsobom a pýtať sa : “ide to za čas \(1\)?”, “ide to za čas \(2\)?”…

Akonáhle je odpoveď na nejakú takúto otázku áno, vieme, že sme našli najmenší čas, za ktorý vieme \(p\) fixiek nakúpiť. Ide ale jednoducho nájsť odpoveď na takéto otázky? Ukážeme si, že áno. Vezmime si otázku : “ide to za čas \(x\)?” a poďme na ňu skúsiť nejak odpovedať.

Čo najskôr potrebujeme urobiť, je nájsť obchody z ktorých máme na výber, teda zistiť, ktoré ležia do vzdialenosti \(x\). To vieme ľahko jedným prehľadávaním do šírky v lineárnom čase. Keď máme tieto obchody, chceme vedieť či ide len pomocou nich kúpiť \(p\) fixiek za cenu najviac \(c\). Ak si zoradíme obchody, ktoré máme k dispozícií podľa ceny za jednu fixku, vieme postupne nakupovať fixky od najlacnejších obchodov až po najdrahšie. Čo sa môže stať sú 3 veci:

1. fixky úspešne nakúpime za cenu dokopy menej ako c
2. počas nakupovania fixiek nám dojdú peniaze
3. počas nakupovania nám dojdú obchody, z ktorých by sme mohli nakúpiť

Asi je jasné, že iba prvá možnosť znamená, že to “ide za čas \(x\)”, ostatné znamenajú, že zatiaľ sme s touto vzdialenosťou nepochodili a musíme sa pozrieť na obchody o kus ďalej.

Akú má toto riešenie časovú zložitosť? Koľko môže byť otázok typu : “ide to za čas \(x\)?”. Je to zjavne \(n\). S časom \(x=n\) už vieme určite použiť všetky obchody, žiadny obchod nemôže byť ďalej a pridaním času sa nám teda už ponuka nezvýši, inými slovami, ak to nejde za čas \(n\), nepôjde to ani za čas \(n+1\), \(n+2\), \(n+3\)… Koľko najviac môže trvať odpoveď na takúto otázku? Zoradiť všetky obchody a raz ich prejsť bude trvať pokaždé \(O(n \cdot log(n))\). Teraz vieme v čase \(O(n \cdot n \cdot log(n) + m)\) riešiť túto úlohu. Akú ma toto pamäťovú zložitosť? Ukazuje sa, že tak ako všetky naše riešenia to bude \(O(n+m)\). V každom našom riešení nám bude stačit zapamätať si konštantne veľa vecí pre každý obchod a potom ešte zoznam susedov, reprezentujúci graf.

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

using namespace std;

// prehladavanie do sirky na grafe "G" z vrcholu "zac"
void bfs(const int zac, const vector<vector<int> >& G, vector<int>& vzd)
{
    queue<int> Q;
    
    vzd[zac] = 0;
    Q.push(zac);
    
    while(!Q.empty())
    {
        int v = Q.front();
        Q.pop();
        
        for(const int kandidat : G[v]) if(vzd[kandidat] == -1)
        {
            vzd[kandidat] = vzd[v] + 1;
            Q.push(kandidat);
        }
    }
    
    return;
}

// vrati true ak ide nakupit "max_pocet" fixiek za cenu najviac "max_cena" len s obchodmi
// v poli "moznosti"
bool ide(vector< pair<int, int> >& moznosti, const int max_cena, const int max_pocet)
{
    // chceme prechadzat od najlacnejsich obchodov
    sort(moznosti.begin(), moznosti.end());

    int spolu = 0, cena = 0;
    for(int j=0;j<moznosti.size();++j)
    {
        if(cena > max_cena) break;
        
        if(spolu + moznosti[j].second <= max_pocet)
        // pridame vsetky fixky z obchodu
        {
            spolu += moznosti[j].second;
            cena += moznosti[j].first * moznosti[j].second;
        }
        else
        // pridame cast fixiek z obchodu a skoncime
        {
            cena += moznosti[j].first * (max_pocet-spolu);
            spolu = max_pocet;
            break;
        }
    }
        
    if(spolu == max_pocet && cena <= max_cena) return true;

    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    
    int n, m, max_pocet, max_cena;
    
    cin >> n >> m >> max_pocet >> max_cena;
    
    vector<vector<int> > G(n+1, vector<int>());
    vector<int> pocty(n, 0), ceny(n, 0);
    
    for(int i=0;i<n;++i) cin >> pocty[i];
    
    for(int i=0;i<n;++i) cin >> ceny[i];
    
    for(int i=0;i<m;++i)
    {
        int a, b;
        cin >> a >> b;
        
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    vector<int> vzd(n+1, -1);
    
    bfs(n, G, vzd);
    
    for(int i=0;i<=n+1;++i)
    // "i" nam hovori aku vzdialenost teraz testujeme
    {
        vector<pair<int, int> > moznosti;
        
        // do vectoru moznosti nahadzeme vsetko, co je do vzdialenosti "i"
        for(int j=0;j<n;++j) if(vzd[j] <= i) 
        {
            moznosti.push_back( {ceny[j], pocty[j]} );
        }
        
        // spytame sa, ci existuje riesenie, ak ano, vypiseme ho a skoncime
        if( ide(moznosti, max_cena, max_pocet) )
        {
            cout << i << endl;
            return 0;
        }
    }

    // ak sme riesenie nenasli, neexistuje
    cout << "-1" << endl; 
    
    return 0;
}

Ako naše riešenie teraz časovo zlepšiť?

Zlepšenie riešenia hrubou silou

K jednoduchému zlepšeniu vedie nasledovné pozorovanie: Ak vieme \(p\) fixiek nakúpiť za cenu \(c\) a to všetko za čas \(x\) (teda pomocou obchodov do vzdialenosti \(x\)), vieme to určite aj za čas \(x+1\), \(x+2\), \(x+3\) atď. Pokiaľ je \(x\) najmenší čas, za ktorý to vieme, tak zároveň platí, že to nevieme za čas \(x-1\), \(x-2\), \(x-3\)… \(0\). To ale znamená, že vieme odpoveď jednoducho binárne vyhľadať. Povedali sme si, že najskôr ide \(p\)-fixiek nakúpiť za čas \(1\), najneskôr za čas \(n\). Ak si vezmeme nejaký čas \(x\), môžu sa stať dve veci:

1. za čas x ide nakúpiť p fixiek za cenu najviac c a teda musíme najmenšiu odpoveď
hľadať vo vzdialenosti menšej alebo rovnej ako x.
2. za čas x nejde nakúpiť p fixiek za cenu najviac c a teda musíme najmenšiu odpoveď
hľadať vo vzdialenosti väčšej ako x.

Tento malý trik si zapamätajte. V úlohách, kde treba hľadať najmenší čas za ktorý sa niečo dá spraviť, sa tentro trik používa pomerne často. Akú má tento postup časovú zložitosť? Počet otázok, na ktoré vieme stále odpovedať v čase \(O(n \cdot log(n))\), sa zmenšil z \(n\) na \(log(n)\). Výsledná časová zložitosť je teda \(O(log(n) \cdot n \cdot log(n))\) alebo inak \(O(n \cdot log(n)^2 + m)\). Toto už stačí na prejdenie všetkými vstupmi.

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

using namespace std;

void bfs(const int zac, const vector<vector<int> >& G, vector<int>& vzd)
{
    queue<int> Q;
    
    vzd[zac] = 0;
    Q.push(zac);
    
    while(!Q.empty())
    {
        int v = Q.front();
        Q.pop();
        
        for(const int kandidat : G[v]) if(vzd[kandidat] == -1)
        {
            vzd[kandidat] = vzd[v] + 1;
            Q.push(kandidat);
        }
    }
    
    return;
}

bool ide(vector< pair<int, int> >& moznosti, const int max_cena, const int max_pocet)
{
    sort(moznosti.begin(), moznosti.end());

    int spolu = 0, cena = 0;
    for(int j=0;j<moznosti.size();++j)
    {
        if(cena > max_cena) break;
        
        if(spolu + moznosti[j].second <= max_pocet)
        {
            spolu += moznosti[j].second;
            cena += moznosti[j].first * moznosti[j].second;
        }
        else
        {
            cena += moznosti[j].first * (max_pocet-spolu);
            spolu = max_pocet;
            break;
        }
    }
        
    if(spolu == max_pocet && cena <= max_cena) return true;

    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    
    int n, m, max_pocet, max_cena;
    cin >> n >> m >> max_pocet >> max_cena;
    
    vector<vector<int> > G(n+1, vector<int>());
    vector<int> pocty(n, 0), ceny(n, 0);
    
    for(int i=0;i<n;++i) cin >> pocty[i];
    for(int i=0;i<n;++i) cin >> ceny[i];
    
    int a, b;
    for(int i=0;i<m;++i)
    {
        cin >> a >> b;
    // Tu doslo k zmene
    //////////////////////////////////////////////////////////////////
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    vector<int> vzd(n+1, -1);
    bfs(n, G, vzd);
    
    int zac = 1, stred, kon = n+1;
    
    while(kon - zac > 2)
    {
        stred = (zac+kon)/2;
        
        vector<pair<int, int> > moznosti = nahadz()
        
        for(int j=0;j<n;++j) if(vzd[j] <= stred) 
        {
            moznosti.push_back( {ceny[j], pocty[j]} );
        }
        
        if( ide(moznosti, max_cena, max_pocet) ) kon = stred+1;
        else zac = stred;
    }
    
    for(int i=zac;i<kon;++i)
    {
        vector<pair<int, int> > moznosti;
        
        for(int j=0;j<n;++j) if(vzd[j] <= i) 
        {
            moznosti.push_back( {ceny[j], pocty[j]} );
        }
        
        if( ide(moznosti, max_cena, max_pocet) )
        {
            cout << i << endl;
            return 0;
        }
    }
    
    cout << "-1" << endl; 
    
    //////////////////////////////////////////////////////////////////
    
    return 0;
}

Vzorové riešenie

Vzorové riešenie bude akosi trochu kopírovať naše prvé riešenie hrubou silou. Zas sa bude náš algoritmus pozerať na problém po úrovniach. Chceme totiž využiť vlastnosť, že akonáhle fixky, ktoré máme k dispozícií spĺňajú podmienky počtu a ceny, vieme, že naše riešenie je najlepšie možné. Riešenie hrubou silou malo nevýhodu, že po každej úrovni zahodilo všetky informácie, ktoré o grafe získalo. Ako budeme teda postupovať?

Budeme prechádzať obchody postupne po úrovniach (podľa vzdialenosti od chaty) a udržiavať si v akomsi virtuálnom nákupnom košíku dostatočný počet, doteraz najlacnejších fixiek. Do košíku najskôr naložíme všetky fixky z obchodov v nejakej úrovni. Ak je počet fixiek stále moc nízky, pokračujeme ďalšou úrovňou. Ak je počet fixiek v košíku moc veľký, začneme fixky vyhadzovať pokým ich nie je v košíku toľko, koľko chceme. Vyhadzovať ich samozrejme budeme od najdrahších. Po dovyhodzovaní fixiek je ich určite v košíku toľko, koľko potrebujeme. Ak je ale cena privysoká, pokračujeme ďalšou úrovňou. Akonáhle nájdeme riešenie, je jasné, že žiadne lepšie neexistuje, kedže by sme ho boli objavili skôr.

Ako bude vyzerať implementácia? Od košíka chceme, aby sme doňho vedeli rýchlo vkladať dvojice
(cena_za_fixku_v_obchode, obchod) a vedeli z neho rýchlo vyberať a pozerať sa na akutálne najdrahší obchod, z ktorého máme nejaké fixky. Pokaždé keď fixky vyhadzujeme, stačí sa nám pozrieť na vrchný najdrahší obchod, z ktorého fixky v košíku máme. Asi tušíte, že na toto je vhodná dátová štruktúra maximová halda.

Aká bude časová zložitosť tohto riešenia? Obchody musíme určite zoradiť, každý obchod pridáme do košíka iba raz a z košíka vyhadzujeme iba na jednotlivých úrovniach. Časová zložitosť je teda \(O(n*log(n) + m)\). Pamäťová zložitosť ostáva \(O(n+m)\).

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

using namespace std;

void bfs(int zac, const vector<vector<int> >& G, vector<int>& vzd)
{
    queue<int> Q;
    
    vzd[zac] = 0;
    Q.push(zac);
    
    while(!Q.empty())
    {
        int v = Q.front();
        Q.pop();
        
        for(const int kandidat: G[v]) if(vzd[kandidat] == -1)
        {
            vzd[kandidat] = vzd[v] + 1;
            Q.push(kandidat);
        }
    }
    
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    
    int n, m, max_pocet, max_cena;
    cin >> n >> m >> max_pocet >> max_cena;
    
    vector<vector<int> > G(n+1, vector<int>());
    vector<int> pocty(n, 0), ceny(n, 0);
    
    for(int i=0;i<n;++i) cin >> pocty[i];
    for(int i=0;i<n;++i) cin >> ceny[i];
    
    for(int i=0;i<m;++i)
    {
        int a, b;
        cin >> a >> b;
        
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    vector<int> vzd(n+1, -1);
    bfs(n, G, vzd);
    
    // v poli dvojic "por" su obchody zoradene podla vzdialenosti
    vector<pair<int, int> > por(n);
    
    for(int i=0;i<n;++i) por[i] = {vzd[i], i};
    
    // klasicke zoradovanie dvojic podla prveho cisla, teda vzdialenosti
    sort(por.begin(), por.end());
    
    // maximalna vzdialenost, do ktorej hladame obchody, i index prveho obchodu,
    // ktory zatial nepouzivame
    int i = 0, max_vzd = 1;
    // cena veci v kosiku a pocet veci v kosiku
    long long cena = 0, pocet = 0;
    
    // PQ symbolizuje nas nakupny kosik
    priority_queue< pair<int, int> > PQ;
    // v poli nakupene si pamatame pre kazdy obchod, kolko fixiek mame z neho v kosiku
    vector<int> nakupene(n, 0);
    
    // i je index prveho obchodu, ktory zatial neuvazujeme
    while(i<n)
    {
        // najskor pridavame obchody pokym su do vzdialenosti max_vzd
        while(i<n && por[i].first <= max_vzd)
        {
            int obchod = por[i].second;
            
            nakupene[obchod] += pocty[obchod];
            pocet += pocty[obchod];
            cena += pocty[obchod] * ceny[obchod];
            
            PQ.push( {ceny[obchod], obchod} );
            
            ++i;
        }
        
        ++max_vzd;
        
        // ak pocet nie je dostatocny, skaceme na dalsiu uroven
        if(pocet < max_pocet) continue;
        
        // vyhadzujeme pokym nie je pocet fixiek v kosiku presne max_pocet
        while(1)
        {
            int obchod = PQ.top().second;
            
            // prva moznost je ze chceme kompletne z kosika odstranit fixky z najdrahsieho
            // obchodu "obchod" lebo ich aj tak budeme mat dost
            if( pocet - nakupene[obchod] >= max_pocet)
            {
                PQ.pop();
                pocet -= nakupene[obchod];
                cena -= nakupene[obchod] * ceny[obchod];
                nakupene[obchod] = 0;
            }
            else
            {
                // druha moznost je, ze nechceme odstranit vsetky z najdrahsieho obchodu
                // lebo by sme nemali dost fixiek
                long long cast = pocet - max_pocet;
                pocet -= cast;
                cena -= cast * ceny[obchod];
                nakupene[obchod] -= cast;
                break;
            }
        }
        
        // ked sme skoncili a fixiek je urcite v kosiku max_pocet,
        // skontrolujeme ci sedi cena
        if(cena <= max_cena)
        {
            cout << max_vzd-1 << endl;
            return 0;
        }
    }

    cout << "-1" << endl;
    
    return 0;
}