6. Strieborné bubáky vzorové riešenie

5 10
1 1
11 100
11 10
1 5
20 15

30

Dynamika

Prvá vec, ktorá pravdepodobne skúsenému riešiteľovi napadne, keď sa pozrie na túto úlohu je: “dynamické programovanie”. Otázkou len je, ako si dobre zadefinovať stavy, aby sme si z menších stavov vedeli jednoducho vypočítať väčšie. Jednoduchý plán by bol definovať \(dp[t]\) = najväčší počet bubákov, ktorý viem mať v deň \(t\) (t.j. po \(t\) použitiach nejakého krompáča, hneď po tom ako sme sa rozhodovali, či kupujeme krompáč v deň \(t\)). Avšak, \(dp[t]\) nevieme priamočiaro vypočítať iba z predošlých stavov. Pri úvahách záleží na tom, ktorý krompáč použijeme zo dňa \(t-1\) na deň \(t\). Preto sa núka zadefinovať stavy nasledovne:
\(dp[t][j] =\) náš najväčší možný počet bubákov v deň \(t\), ak aktuálne máme krompáč \(j\) (ten, ktorý bolo možné kúpiť v deň \(j\))

Môžeme to vnímať tak, že na začiatku máme krompáč \(0\), ktorý ťaží \(0\) bubákov za deň. Teraz vieme medzi stavmi jednoducho prechádzať:

• pre \(j < t\): \(dp[t][j] = dp[t-1][j]+b_j\),
• pre \(j = t\): \(dp[t][j] = -c_t+\max \lbrace dp[t][0], \dots, dp[t][t-1] \rbrace\),
• pre \(j > t\): \(dp[t][j] = -\infty\).

Takže môžeme počítať odpoveď pre jednotlivé stavy podľa \(t\) vzostupne a pre fixné \(t\) vzostupne podľa \(j\). Nakoniec finálnu odpoveď nájdeme ako \(\max \lbrace dp[N+1][0], \dots dp[N+1][N] \rbrace\). Časová zložitosť tohoto riešenia je \(O(N^2)\).

Už to len zrýchliť

Pokúsime sa vylepšiť naše doterajšie riešenie. Chceli by sme dátovú štruktúru. Tá by si udržovala aktuálny deň \(t\), pre tento aktuálny deň naše možnosti zodpovedajúce dvojiciam \((j, dp[t][j])\), kde \(j \leq t\) reprezentuje náš aktuálny krompáč (posledný, ktorý sme sa rozhodli kúpiť). Navyše chceme, aby sa táto štruktúra dala ľahko upraviť pri prechode do dňa \(t+1\).

Ak by sme si pre každý krompáč \(j\) skutočne stále pamätali \(dp[t][j]\), tak by bol update z \(t\) na \(t+1\) časovo náročný (priamočiaro to nejde lepšie ako v \(O(N)\)). Skúsme sa toho teda vzdať. Napriek tomu však budeme chcieť byť schopný (pri troche úsilia) v aktuálnom dni vypočítať hodnotu \(dp[t][j]\) pre ľubovoľné \(j\).

Pre konkrétne \(j\) sa \(dp\) v čase vyvíja priamočiaro. \(dp[j][j]\) treba vypočítať náročne, ale potom je to už jednoduché: \(dp[t][j] = (t-j)b_j+dp[j][j]\). To nás navádza na myšlienku, že v našej štruktúre bude stačiť mať pre fixné \(j\) iba hodnotu \(dp[j][j]\).

Update z času \(t\) na \(t+1\) sa tak zvrháva na to, ako pridať \(t+1\). Ako spočítať \(dp[t+1][t+1]\)? Toto je ťažká vec. Na to, aby sme to vedeli rátať by bolo dobré mať krompáče v našej štruktúre utriedené podľa ich aktuálnej hodnoty \(dp\). Potom by výpočet bol triviálny. Chceš \(dp[t+1][t+1]\)? Zober zo štruktúry (v čase \(t+1\), pred pridaním krompáča \(t+1\)) krompáč \(j_0\) s najväčším \(dp[t+1][j_0]\). Potom \(dp[t+1][t+1] = dp[t+1][j_0]-c_{t+1}\). Ako však udržiavať štruktúru utriedenú?

Vezmime fixný deň \(t\). Krompáč \(j \leq t\) nazvime nadbytočný, ak

• existuje krompáč \(k \leq t\) taký, že (\(dp[t][k] > dp[t][j]\) a \(b_k \geq b_j\)) alebo (\(dp[t][k] = dp[t][j]\) a \(b_k > b_j\)), ALEBO
• existuje krompáč \(k \leq t\) taký, že \(dp[t][k] = dp[t][j]\) a \(b_k = b_j\) a \(k > j\).

Ak sa nám v nejakom čase stane, že je nejaký krompáč nadbytočný, tak na neho môžeme navždy zabudnúť. A presne to aj budeme robiť.

Navyše si všimnime, že ak v čase \(t\) máme v štruktúre iba nenadbytočné krompáče a utriedime ich podľa \(b_j\), tak ich hodnoty \(dp[t][j]\) musia v tomto poradí (nie nutne ostro) klesať. Skutočne, ak \(b_j \leq b_k\) a zároveň \(dp[t][j] \leq dp[t][k]\), tak aspoň jeden z nich je nadbytočný. Takže nám stačí udržovať nenadbytočné krompáče utriedené podľa ich \(b_j\), v prípade zhody podľa \(j\) vzostupne. Konkrétna implementácia môže byť napríklad ako set v C++ (binárny vyvažovaný strom) s prvkami tvaru \((b_j, j)\).

Ako si však udržovať v štruktúre iba nenadbytočné krompáče? Deň sa práve zmenil z \(t\) na \(t+1\), ešte sme však nepridali krompáč \(t+1\). Potrebujeme spraviť dve úpravy:

• Odstránenie nadbytočných krompáčov: V štruktúre máme krompáče \(j_0, \dots, j_m\) zoradené podľa \(b_j\). Ak sa nejaký krompáč \(j_i\) stal nadbytočným, tak si všimnime, že je nadbytočný s krompáčom \(k = j_{i+1}\) (v definícii vyššie). Budeme preto udrživať set udalostí \(U\), v ktorom pre každý krompáč \(j_i\) v našej štruktúre budeme mať udalosť \((t_*, j_i)\) hovoriacu, že v čase \(t_*\) sa \(j_i\) stane nadbytočným (s \(k = j_{i+1}\)). Potom vieme ľahko spraviť úpravu poradia: Pokiaľ je v \(U\) udalosť s časom \(\leq\) ako \(t+1\), vezmi príslušný krompáč, odstráň ho z poradia a updatni udalosti \(U\).
• Pridanie krompáču \(t+1\) a odstránenie tým vzniknutých nadbytočných krompáčov: Toto je jednoduché. Pozrieme sa kam do poradia by patril \(t+1\). Ten je buď hneď nadbytočný (v takom prípade ho nepridáme vôbec), alebo nie je (v takom prípade ho pridáme a prípadne povyhadzujeme krompáče, ktoré sa tým stali nadbytočné (tie sú nutne v poradí susedné pod ním)).

Poznamenajme, že nám nevadí, keď v konkrétnej implementácii budú pre nejaké \(j_*\) v \(U\) zostávať aj zastaralé udalosti.

Zhrnutie

Udržujeme si aktuálny deň \(t\), nenadbytočné krompáče v poradí podľa \((b_j, j)\) a set udalostí \(U\).

Update z \(t\) na \(t+1\) vyzerá nasledovne:

• Pokiaľ je v \(U\) udalosť s \(t_* \leq t+1\), vyhoď príslušný krompáč zo štruktúry (stal sa nadbytočný) a pridaj nové udalosti do \(U\). Opakuj.
• Nájdi \(j_0\) s najmenším \(b_{j_0}\) (a preto najväčším \(dp[t+1][j_0]\)), z toho spočítaj \(dp[t+1][t+1]\).
• Ak \(t+1\) nie je nadbytočný, pridaj ho a povyhadzuj krompáče, ktoré sa stali nadbytočné (v poradí susedné pod ním).

Na konci (v dni \((N+1)\)), jednoducho nájdeme \(j_0\) s najmenším \(b_{j_0}\) a odpoveď bude \(dp[N+1][j_0]\).

Celkovo spravíme \(O(N)\) operácii s oboma setmi a tieto operácie sú v \(O(\log N)\). Celková zložitosť bude \(O(N \log N)\). Pamäťová zložitosť bude \(O(N)\).

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define ff first
#define ss second

struct State {
    int time;
    // optimal miners: {miner_income, miner_id}
    // redundant miners: {time, miner_id}
    set<pair<ll, int>> optimal_miners, redundant_miners;
    vector<ll> price, income, base_income;

    ll miner_value(int id) {
        return (time-id)*income[id]+base_income[id];
    }

    ll get_swap_time(int down_id, int up_id) {
        if(income[up_id] == income[down_id]) return 0;
        double temp_time = (base_income[down_id]-down_id*income[down_id])-(base_income[up_id]-up_id*income[up_id]);
        temp_time /= income[up_id]-income[down_id];
        ll T = max((ll) 0, (ll) ceil(temp_time));
        return T;
    }

    void add_miner(int id) {
        ll val = miner_value(optimal_miners.begin()->ss);
        if(val < price[id]) return;
        base_income[id] = val-price[id];
        auto up_it = optimal_miners.upper_bound({income[id], INT_MIN});
        if(up_it != optimal_miners.end()) {
            if(miner_value(up_it->ss) >= miner_value(id)) return;
            ll T = get_swap_time(id, up_it->ss);
            redundant_miners.insert({T, id});
        }
        if(up_it == optimal_miners.begin()) {
            optimal_miners.insert({income[id], id});
            return;
        }
        auto down_it = prev(up_it);
        ll T = get_swap_time(down_it->ss, id);
        redundant_miners.insert({T, down_it->ss});
        optimal_miners.insert({income[id], id});
    }

    void remove_miner(int id) {
        pair<ll, int> curr = {income[id], id};
        if(optimal_miners.find(curr) == optimal_miners.end()) return;
        optimal_miners.erase(curr);
        auto up_it = optimal_miners.upper_bound(curr);
        if(up_it == optimal_miners.end() || up_it == optimal_miners.begin()) return;
        auto down_it = prev(optimal_miners.upper_bound(curr));
        int up_id = up_it->ss, down_id = down_it->ss;
        ll T = get_swap_time(down_id, up_id);
        redundant_miners.insert({T, down_id});
    }

    void simplify() {
        while(redundant_miners.size() > 0) {
            auto curr = *redundant_miners.begin();
            if(curr.ff > time) break;
            redundant_miners.erase(curr);
            int id = curr.ss;
            remove_miner(id);
        }
    }
};

int main() {
    int N; ll B;
    cin >> N >> B;
    State s;
    s.time = 0;
    s.optimal_miners.insert({0, 0});
    s.price.resize(N+1);
    s.income.resize(N+1);
    s.base_income.resize(N+1, 0);
    s.base_income[0] = B;
    for(int t = 1; t <= N; t++) {
        cin >> s.price[t] >> s.income[t];
        s.time = t;
        s.simplify();
        s.add_miner(t);
        s.simplify();
    }
    s.time++;
    s.simplify();
    cout << s.miner_value(s.optimal_miners.begin()->ss) << "\n";
    return 0;
}