Zadanie

Prišlo leto a s ním aj LTT. Úžasná akcia, ktorej sa chce každý nadšený matematik, fyzik či informatik zúčastniť. Vedúci si na sústredenie prichystali množstvo zaujímavých prednášok. Keď však dorazili na chatu, zistili, že väčšina ich fixiek nepíše. Na vedúcovskej izbe zavládol nepokoj. Čo budú robiť? Aké vedomosti si účastníci z tábora odnesú, ak nikto nebude môcť vysvetľovať na tabuľu? Nuž, podujali sa fixky vo veľkom množstve nakúpiť. Zásoby v jednotlivých dedinách naokolo sú však obmedzené a z miest, ako tak blízko k chate, to bude isto nejaký čas trvať. Oni však majú málo penazí a tiež by chceli, aby fixky prišli čím skôr. Vymyslite, ako im s týmto problémom pomôcť a čo najskôr k ním fixky dopraviť.

Úloha

V úlohe dostanete pre každý obchod počet fixiek, ktoré má na sklade – \(p_i\) a cenu za jeden kus – \(c_i\). Naviac od nás dostanete informáce o tom, ktoré obchody sú s ktorými priamo prepojené cestou. Môžete predpokladať, že prevoz fixiek medzi nejakými priamo spojenými obchodmi trvá nejaký konštantný čas, napr. \(1\) hodinu. Vašou úlohou je nájsť najmenší čas \(t\), za ktorý je možné dopraviť \(p\) fixiek na chatu za cenu najviac \(c\). Znamená to teda, že vašou hlavnou úlohou je minimalizovať čas, za ktorý fixky dorazia na chatu, nie celkovú cenu, tá samozrejme ale musí byť dostatočne malá aby bola zaplatiteľná vedúcimi.

Formát vstupu

Na začiatku vstupu sa nachádzajú \(4\) čísla \(n\), \(m\), \(p\), \(c\). Číslo \(n\) (\(1 \leq n \leq 100\,000\)) – počet obchodov, ktoré sa nachádzajú v okolitých dedinách, \(m\) (\(1 \leq m \leq 1\,000\,000\)) – počet spojení medzi obchodmi ale aj chatou a potom \(p\) (\(1 \leq p \leq 10^7\)) a \(c\) (\(1 \leq c \leq 10^9\)), počet fixiek, ktoré chceme nakúpiť a maximálna cena, ktorú si môžme dovoliť zaplatiť. Chata má v našom číslovaní vždy číslo \(n\) a nepočíta sa medzi obchody. Na ďaľšom riadku je \(n\) medzerou oddelených čísel, ktoré reprezentujú \(p_i\)(\(0 \leq p_i \leq 10^7\)). \(i\)-te číslo na tomto riadku určuje počet fixiek, ktoré má na sklade \(i\)-ty obchod. Na ďaľšom riadku je \(n\) medzerou oddelených čísel, ktoré reprezentujú \(c_i\)(\(0 \leq c_i \leq 10^9\)). \(i\)-te číslo na tomto riadku určuje cenu jednej fixky v \(i\)-tom obchode. Na nasledujúcich \(m\) riadkoch sú postupne dvojice čísel \(a\), \(b\) (\(0 \leq a, b \leq n\)), reprezentujúce, že existuje priama a obojsmerná cesta medzi lokáciami(chata/obchod) s číslom \(a\) a \(b\). Všimnite si, že napriek tomu, že obchody číslujeme od \(0\), \(a\), či \(b\) môžu byť aj rovné \(n\), čo symbolizuje cestu, ktorá spája nejaký obchod a chatu. Možete predpokladať, že z každej lokácie sa dá dostať do každej inej lokácie postupnosťou nejakých priamych spojení.

Formát výstupu

Na výstup vypíšte jedno číslo – najmenší čas, za ktorý sa dá nakúpiť \(p\) fixiek, pričom ich cena dokopy nepresiahne cenu \(c\) alebo \(-1\) ak sa to nedá.

Hodnotenie

Pre jednotlivé sady platia aj tieto špeciálne obmedzenia:

V prvej sade platí, že počet obchodov je malý a takisto aj počet priamych ciest, teda \(n \leq 100\) a \(m \leq 150\). V druhej sade platí, že \(n \leq 10\,000\) a \(m \leq 50\,000\). Pre tretiu a štvrtú sadu neplatia žiadne špeciálne obmedzenia.

Príklad

Input:

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

Output:

2

V tomto pripade existujú obchody do vzdialenosti \(2\), ktoré nám spolu vedia dopraviť dosť fixiek za prijateľnú cenu. Konkrétne sú to obchody \(1\), \(2\) a \(3\). Môžme napr. vziať \(3\) fixky z obchodu \(1\), \(5\) fixiek z obchodu \(2\) a \(2\) fixky z obchodu \(3\). Za cenu \(3 \cdot 2 + 5 \cdot 3 + 2 \cdot 4 = 29\). Ak by sme hľadali riešenie do vzdialenosti \(1\), museli by sme nakúpiť fixky v obchode \(0\), ktorý je ale na naše dostupné prostriedky pridrahý.

Input:

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

Output:

-1

V tomto prípade neexistujú obchody, z ktorých by sme vedeli nakúpiť potrebné množstvo za nami požadovanú cenu.

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;
}

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