8. Ako priečinky robia radosť vzorové riešenie

5 1
1 2 10 9
1 4 7 11
2 4 15 16
4 5 20 1
5 7 2 5

11

5 4
1 2 10 9
1 4 7 11
2 4 15 16
4 5 20 1
5 7 2 5

40

3 1
1 1000000 1 1
1000000 50000000 1000000000 1
50000000 1000000000 1000000000 474747

999999991

10 1
1 2 1 4
1 3 5 3
3 5 7 2
2 4 6 9
2 3 7 5
3 5 8 2
1 8 9 1
4 5 10 3
5 8 6 47
8 9 10 5

10

10 5
1 2 1 4
1 3 5 3
3 5 7 2
2 4 6 9
2 3 7 5
3 5 8 2
1 8 9 1
4 5 10 3
5 8 6 47
8 9 10 5

45

10 25
1 2 1 4
1 3 5 3
3 5 7 2
2 4 6 9
2 3 7 5
3 5 8 2
1 8 9 1
4 5 10 3
5 8 6 47
8 9 10 5

113

Prevedieme si najprv úlohu do informatickej terminológie. Vedúci sú vrcholy, a odovzdanie priečinka je orientovaná hrana – ak vedúci \(x\) vie odovzdať vedúcemu \(y\) priečinok s radosťou odovzdávania \(a_y - b_x\), tak z vrcholu \(x\) vedie hrana do vrcholu \(y\) s váhou \(a_y - b_x\). Životná púť priečinka je teda cesta v tomto grafe, a hodnota je súčet váh hrán na nej.

Môžeme si o tomto grafe navyše všimnúť, že je acyklický, keďže každý vedúci vie odovzdať priečinok v ostro neskoršom roku, ako ho dostal. Je to teda DAG (directed acyclic graph).

N < 20 znamená…

…že použijeme starú dobrú hrubú silu, a prejdeme si všetky možné púte priečinka. Skúsime začať v každom vrchole, pozrieme sa na všetky ostatné, a rekurzívne pokračujeme do každého, do ktorého vedie hrana.

Hodnotu každej púte, ktorú spracujeme si odložíme, a po prehľadávaní ich usporiadame a sčítame \(k\) najhodnotejších z nich.

#include <bits/stdc++.h>

using namespace std;

struct veduci {
    long long pride, odide, v_pride, v_odide;
};

vector<veduci> v;
vector<long long> sols;

// existuje put s hodnotou p prechadzajuca veducim i
void bf(int i,long long p)
{
    sols.push_back(p);
    for(int k=0;k<v.size();++k)
    {
        if(v[k].pride == v[i].odide && v[k].v_pride > v[i].v_odide)
            bf(k,p+v[k].v_pride-v[i].v_odide);
    }
}

int main()
{
    int n,k;
    cin >> n >> k;

    v.resize(n);
    for(int i=0;i<n;++i)
    {
        cin >> v[i].pride >> v[i].odide >> v[i].v_pride >> v[i].v_odide;
    }

    for(int i=0;i<n;++i)
        bf(i,0);

    sort(sols.begin(),sols.end(),greater<long long>());

    long long ans = 0;
    for(int i=0;i<min(k,(int)sols.size());++i)
        ans += sols[i];

    cout << ans%1000000007 << "\n";

}

Aby sme určili zložitosti, musíme zistiť, koľko ciest vie existovať v orientovanom acyklickom grafe. Môžeme využiť fakt, že v takomto grafe je cesta jednoznačne určená množinou vrcholov v nej, keďže cez vrcholy na ceste vieme ísť len v jednom poradí, a bez cyklov sa nemôžu ani opakovať. Samozrejme, nie každá podmnožina vrcholov tvorí platnú cestu, ale každá platná cesta je určená podmnožinou, dáva nám teda horný odhad. Počet podmnožín \(n\) vrcholov je \(O(2^n)\), toľko ciest teda v najhoršiom prípade nájdeme. Každá cesta má najviac \(n\) vrcholov, a v každom vrchole prejdeme zvyšné vrcholy aby sme skúsili cestu predĺžiť, náš odhad časovej zložitosti je teda \(O(n^2 2^n)\), a pamäťovej \(O(2^n)\).

Najdrahšia cesta v DAGu

Poďme teda vymyslieť niečo prefíkanejšie ako skúšanie všetkých možností. Počet ciest v našom grafe je exponenciálny, ale nás z nich zaujíma len málo z nich – v ďalších dvoch sadách dokonca len jedna, tá najdrahšia.

Skúsme teda nájsť najdrahšiu cestu tak, že si pre každý vrchol zistíme najdrahšiu cestu, ktorá končí v ňom – naša celková najdrahšia cesta musí končiť v niektorom vrchole, bude teda jednou z nich.

Môžeme si napríklad všimnúť, že ak máme cestu prechádzajúcu vrcholmi \(v_1, v_2, \cdots, v_{d-1}, v_d\) kde \(d\) je jej dĺžka, tak ak je to najdrahšia cesta končiaca vo \(v_d\), tak cesta \(v_1, v_2, \cdots, v_{d-1}\) je najdrahšia cesta končiaca vo \(v_{d-1}\). Ak by totiž bola iná cesta ktorá je drahšia a končí vo \(v_{d-1}\), tak by sme ju mohli napojiť na \(v_d\) a získať drahšiu cestu ako tú s ktorou sme začali, čo je v rozpore s tým že sme začali s najdrahšou cestou končiacou vo \(v_d\).

Z tohto pozorovania vyplýva, že na nájdenie najdrahšej cesty končiacej vo vrchole \(v\) stačí nájsť najdrahšie cesty končiace vo vrcholoch, z ktorých sa vieme priamo dostať do \(v\), a najdrahšia cesta bude jedna z nich plus cena hrany, ktorou sa na ňu napojíme.

Stačí nám teda prejsť vrcholy vo vhodnom poradí, aby sme vždy zrátali cenu najdrahšej cesty pre nejaký vrchol \(v\) skôr, ako ju budeme rátať pre vrcholy do ktorých sa vieme dostať z \(v\). Keďže vieme, že vedúci môže odovzdať priečinok len takému vedúcemu, ktorý príde do KSP až po ňom, môžeme si vedúcich zoradiť podľa roku príchodu, a prejdeme ich v tomto poradí.

Nakoniec vypíšeme cenu najdrahšej cesty, ktorú sme takto našli.

#include <bits/stdc++.h>

using namespace std;

struct veduci {
    long long pride, odide, v_pride, v_odide;
    long long radost = 0;
};

bool podla_prichodu(veduci a,veduci b)
{
    return a.pride < b.pride;
}

int main()
{
    int n,k;
    cin >> n >> k;

    // nejdeme riesit k>1
    if(k>1) return 0;

    vector<veduci> v(n);
    for(int i=0;i<n;++i)
        cin >> v[i].pride >> v[i].odide >> v[i].v_pride >> v[i].v_odide;

    sort(v.begin(),v.end(),podla_prichodu);

    for(int o=0;o<v.size();++o) {
        for(int p=o+1;p<v.size();++p) {
            if(v[o].odide == v[p].pride && v[p].v_pride > v[o].v_odide)
                v[p].radost = max(v[p].radost, v[o].radost + (v[p].v_pride - v[o].v_odide) );
        }
    }

    long long best = 0;
    for(int i=0;i<n;++i)
        best = max(best,v[i].radost);

    cout << best%1000000007 << "\n";

}

Keďže pre každého vedúceho prejdeme každého, ktorý prišiel po ňom, budeme mať časovú zložitosť \(O(n^2)\). Pre každého si okrem vstupných hodnôt pamätáme len jednu premennú navyše – najdrahšiu cestu končiacu v ňom – pamäť bude \(O(n)\).

Najdrahšia cesta v priečinkovom DAGu

V predošlom riešení skúšame veľa nezmyselných dvojíc vedúcich, aj takých, ktorí si nevedia odovzdať priečinok (lebo prvý neodchádza v roku, v ktorom druhý prichádza).

Rozdeľme si teda vedúcich na kôpky – nech \(P_r\) je zoznam vedúcich ktorí prichádzajú v nejaký rok \(r\), a \(O_r\) je zoznam vedúcich ktorí odchádzajú v rok \(r\). Každý vedúci sa vyskytne raz na zozname prichádzajúcich, a raz na zozname odchádzajúcich.

Ak chceme prechádzať vedúcich podľa roku príchodu, prejdeme kôpky vedúcich v \(P\) pre postupne stúpajúce roky \(r\) (len tie, ktoré boli na vstupe). Potom ich skúšame napojiť na najdrahšie cesty končiace vo vedúcich v \(O_r\), keďže priečinky vedia dostať len od nich.

Stále však môžeme mať až kvadraticky veľa dvojíc – napríklad ak polovica vedúcich odchádza v jednom roku, a druhá polovica vedúcich v tomto roku prichádza.

Skúsme teda namiesto toho, aby sme pre každého prichádzajúceho vedúceho \(v\) skúšali všetkých vedúcich, ktorí odchádzajú v rovnaký rok (a majú menšiu hodnotu priečinka) a napojiť sa na ich cestu, priamo určiť, ktorá z nich bude najdrahšia po napojení na \(v\).

Zoberme si teda príkladového vedúceho \(v\), ktorý príde a bude mať hodnotu priečinka \(p\), a majme dve cesty na ktoré sa vieme napojiť – jednu s hodnotou \(h\), končiacu vo vedúcom ktorý ešte využíva svoj priečinok na \(o\), a druhú s hodnotami \(H\), \(O\).

Akú hodnotu budú mať tieto cesty po napojení na \(v\)? Prvá cesta bude mať \(h+(p-o)\), a druhá \(H+(p-O)\). Aby bola prvá cesta drahšia ako druhá, \(h+(p-o) > H+(p-O)\), tak \(h-o > H-O\). Stačí teda zobrať cestu, ktorá má túto hodnotu (určenú jej hodnotou a vedúcim, v ktorom končí) najväčšiu, a tú napojiť na vedúceho \(v\). Všimnime si, že na ktorú cestu je najlepšie sa napojiť nezávisí od využitia \(p\), ktorý pre priečinok má prichádzajúci vedúci – jediné čo musíme dodržať je, aby cesty ktoré uvažujeme končili vo vedúcich, ktorí sú mu ochotní priečinok odovzdať.

Usporiadajme si teda vedúcich ktorí prichádzajú a odchádzajú v daný rok, poďla ich využitia priečinka, a prejdime ich v tomto poradí. Udržiavame si pritom vyššie popísanú hodnotu najlepšej doposiaľ nájdenej cesty. Keď prídeme na odchádzajúceho vedúceho, pozrieme sa či cesta, ktorá v ňom končí nie je lepšia ako tá čo sme mali doteraz, a ak áno, prepíšeme si ju. Keď prídeme na prichádzajúceho vedúceho, priradíme mu hodnotu najlepšej cesty, plus jeho využitie priečinka v prváku, tiež ako popísané vyššie.

Takto vieme nájsť najdrahšiu cestu končiacu v každom vedúcom, pričom však nepozeráme na všetky možné odovzdávanie medzi nimi, pozrieme sa len na každého vedúceho práve raz.

#include <bits/stdc++.h>

using namespace std;

struct veduci {
    long long pride, odide, v_pride, v_odide;
    long long radost = 0;
};

bool podla_prichodu(veduci a,veduci b)
{
    return a.pride < b.pride;
}

int main()
{
    int n,k;
    cin >> n >> k;

    if(k>1) return 0;

    vector<veduci> v(n);
    for(int i=0;i<n;++i)
        cin >> v[i].pride >> v[i].odide >> v[i].v_pride >> v[i].v_odide;

    map<int,vector<int> > pridu,odidu;
    for(int i=0;i<n;++i)
    {
        pridu[ v[i].pride ].push_back(i);
        odidu[ v[i].odide ].push_back(i);
    }

    for(auto it=odidu.begin();it!=odidu.end();it++)
    {
        int kedy = it -> first;
        vector<int> kto_odide = it -> second;

        if(!pridu.count(kedy)) continue;
        vector<int> kto_pride = pridu[kedy];


        int P = 0, O = 0, ps=kto_pride.size(), os=kto_odide.size();
        
        // usporiadame si odchadzajucich podla hodnoty priecinka pri ich odchode
        vector<pair<int,int> > odchadzajuci;
        for(int i=0;i<os;++i)
            odchadzajuci.push_back({v[ kto_odide[i] ].v_odide,kto_odide[i]});
        sort(odchadzajuci.begin(),odchadzajuci.end());

        // aj prichadzajucich
        vector<pair<int,int> > prichadzajuci;
        for(int i=0;i<ps;++i)
            prichadzajuci.push_back({v[ kto_pride[i]].v_pride,kto_pride[i]});
        sort(prichadzajuci.begin(),prichadzajuci.end());

        // nase 'H-O'
        long long najlepsi_priecinok = -(1e10);
        // spracujeme vsetkych prichadzajucich veducich
        // dvoma bezcami, aby sme spracovali veducich podla hodnoty priecinka
        // pri prichode/odchode
        while(P<ps)
        {

            if(O == os || odchadzajuci[O].first >= prichadzajuci[P].first)
            {
                // veduci prichadza, zratame prenho najlepsiu put
                int kto = prichadzajuci[P].second;
                v[kto].radost = max(0LL, najlepsi_priecinok + v[kto].v_pride);
                
                ++P;
                
            }
            else {
                // veduci odchadza, preratame si najlepsi priecinok
                int kto = odchadzajuci[O].second;
                najlepsi_priecinok = max(najlepsi_priecinok, v[kto].radost - v[kto].v_odide);
                
                ++O;
            }
        }

    }

    long long best = 0;
    for(int i=0;i<n;++i)
        best = max(best,v[i].radost);

    cout << best%1000000007 << "\n";

}

V prípade, že sa všetci vedúci vyskytnú v jeden deň, nám ich usporiadanie zaberie \(O(n \log n)\). Pamäť ostane na \(O(n)\).

A teraz už len trochu všeobecnejšie…

Čo potrebujeme, aby sme toto riešenie rozšírili ak nás nezaujíma len najdrahšia cesta, ale \(k\) najdrahších ciest? Pôjdeme na to rovnako – pre každý vrchol si zapamätáme \(k\) najdrahších ciest, ktoré v ňom končia. Tu využijeme podmienku zo zadania, že \(n \cdot k \leq 10^6\), čiže síce vedia byť \(n\) aj \(k\) veľké, nemôžu byť veľké naraz, a vieme si tieto cesty zapamätať – bude ich najviac \(n \cdot k\).

Analogicky, aby sme našli \(k\) najdrahších ciest končiacich v danom vrchole, musíme skúsiť \(k\) najlepších ciest ktoré sa na neho môžu napojiť (ktorých hodnota mínus využitie priečinka vedúceho, v ktorom končia, je najvyššia).

Namiesto jednej hodnoty najlepšej cesty, si teda budeme pamatäť usporiadanú množinu najlepších ciest. Budeme prechádzať vedúcich rovnako ako v predošlom riešení. Keď spracujeme prichádzajúceho vedúceho, vypočítame jeho najlepších (najviac) \(k\) ciest ktoré v ňom končia. Keď spracujeme odchádzajúceho vedúceho, hodnoty jeho ciest pridáme do našej množiny, a ak ich v nej je viac ako \(k\), zahodíme tie najhoršie.

Počas spracovania prichádzajúcich vedúcich, ktorých je dokopy \(n\), vypočítame najviac \(k\) najdrahších ciest ktoré v nich končia, spravíme teda \(O(nk)\) operácií. Počas spracovania odchádzajúcich vedúcich, ktorých je tiež dokopy \(n\), vypočítame hodnoty ciest ktoré v nich končia, a pridáme ich do našej usporiadanej množiny. Ak použijeme rozumnú dátovú štruktúru (napr. v C++ multiset), pridávanie hodnoty do, a odstraňovanie najmenšej hodnoty z nej nás bude stáť \(O(\log k)\) operácií, ak jej veľkosť je \(O(k)\). Za každého odchádzajúceho vedúceho teda spravíme v najhoršom prípade \(O(k \log k)\) práce, dokopy teda \(O(nk \log k)\). Spolu s usporiadaním vedúcich aby sme ich prešli v správnom poradí teda spravíme \(O(n(\log n + k \log k))\) operácií.

Pamäťová zložitosť bude \(O(nk)\), keďže si pre každého vedúceho pamätáme najviac \(k\) hodnôt ciest.

#include <bits/stdc++.h>
using namespace std;

struct veduci
{
    long long pride, odide, v_pride, v_odide;
    int id;
    vector<long long> pute = {0};
};

struct udalost{

    bool prichadza;
    int id;
    long long v;
};

bool cmp_udalost(udalost a,udalost b)
{
    if(a.v!=b.v)
        return a.v < b.v;
    if(a.prichadza != b.prichadza)
        return a.prichadza > b.prichadza;

    return a.id < b.id;
}

long long solve()
{

    int n,k;
    cin >> n >> k;
    vector<veduci> v(n);

    for(int i=0;i<n;++i)
    {
         v[i].id = i;
        cin >> v[i].pride >> v[i].odide >> v[i].v_pride >> v[i].v_odide;
    }   

    unordered_map<int, vector<int> > pridu, odidu;

    set<int> roky;

    for(int i=0;i<n;++i)
    {
        roky.insert(v[i].pride);
        pridu[ v[i].pride ].push_back(i);
        odidu[ v[i].odide ].push_back(i);
    }

    // prejdeme veducich, ktori pridu/odidu v dany rok
    for(int day : roky)
    {
        if(odidu.count(day)==0) continue;

        vector<int> prichadzajuci = pridu[day];
        vector<int> odchadzajuci = odidu[day];

        // usporiadame si udalosti (relevantny veduci prichadza/odchadza)
        // do poradia podla hodnoty priecinka daneho veduceho pri
        // prichode/odchode
        vector<udalost> U;

        for(int x : prichadzajuci)
        {
            udalost e;
            e.id = x;
            e.v = v[e.id].v_pride;
            e.prichadza = true;

            U.push_back(e);
        }

        for(int x : odchadzajuci)
        {
            udalost e;
            e.id = x;
            e.v = v[e.id].v_odide;
            e.prichadza = false;

            U.push_back(e);
        }

        sort(U.begin(),U.end(),cmp_udalost);
        multiset<long long> najlepsie;

        // prejdeme udalosti
        for(udalost u : U)
        {
            // ak veduci prichadza, zratame mu (najviac) k najlepsich puti
            if(u.prichadza)
            {
                for(auto it: najlepsie)
                {
                    v[u.id].pute.push_back(it+u.v);
                }
            }
            else
            {
                // preratame moznosti na najlepsie priecinky
                for(long long p: v[u.id].pute)
                {
                    najlepsie.insert(p-u.v);
                }

                // ak ich mame viac ako k, zahodime najhorsie
                while(najlepsie.size() > k)
                {
                    najlepsie.erase(najlepsie.begin());
                }
            }
        }
    }

    long long ans = 0;

    vector<long long> pute;

    for(int i=0;i<n;++i)
    {
        for(auto x: v[i].pute)
            pute.push_back(x);
    }

    sort(pute.begin(),pute.end(),greater<long long>());

    for(int i=0;i<k && i<pute.size();++i)
        ans += pute[i];

    return ans%1000000007;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cout << solve() << "\n";
    return 0;
}