6. Cyrilove investície (vzorové riešenie) - Korešpondenčný seminár z programovania

Zadanie

Ako aj mnoho iných v Krajine Sedemhranných Päťkorunákov, aj Cyril sa venuje investovaniu. Od rána do večera sleduje ceny rôznych aktív, aby mu neušla žiadna príležitosť. Našťastie, aj burzy majú svoje otváracie hodiny, a Cyril môže ísť niekedy aj spať.

Cyril ešte nedokončil svoje vzdelanie, a preto sa musí pravidelne účastniť (virtuálnych) prednášok. Aby mu nezapísali neprítomnosť, musí sa ukázať aspoň raz na každej prednáške. Keď je ale na prednáške, nemôže sledovať kurzy, a môže mu ujsť výhodná ponuka!

V Krajine Sedemhranných Päťkorunákov majú burzy neobvyklé otváracie hodiny, jedna je otvorená od 7:14:23.49 do 9:31:07.98, ďalšia od 8:42:22.72 do 11:53:21.44… Cyril by preto rád našiel časy, v ktorých keď sa objaví na prednáškach, príde o čo najmenej investičných príležitostí. Keďže Cyril venuje všetok svoj čas investovaniu, nemá čas si to spočítať, a preto potrebuje vašu pomoc.

Úloha

V Krajine Sedemhranných Päťkorunákov sa nachádza \(n\) búrz. Každá burza má svoje otváracie hodiny uvedené v centisekundách otvoreným intervalom \((a_i, b_i)\). Keďže Cyril na prednáškach nedáva pozor, ani nevie aké sú dlhé. Vie ale, že sa na nich musí ukázať aspoň raz za \(t\) centisekúnd.

Vašou úlohou je nájsť takú postupnosť časov, v ktorých keď sa Cyril ukáže na prednáškach, ujde mu čo najmenej príležitostí. Za ujdenú príležitosť Cyril považuje to, že sa ukáže na prednáške v čase keď je otvorená niektorá burza.¹ Každá burza otvorená v tomto čase sa ráta za jednu ujdenú príležitosť.

Formát vstupu

V prvom riadku vstupu je číslo \(t\) (\(2\leq t\leq 1\,000\,000\)) udávajúce maximálny čas medzi Cyrilovými účasťami na prednáškach. V druhom riadku vstupu je číslo \(n\) (\(1\leq n\leq 1\,000\,000\)) udávajúce počet búrz v Krajine Sedemhranných Päťkorunákov.

V každom z nasledujúcich \(n\) riadkov sa nachádzajú dve čísla oddelené medzerou, udávajúce interval \((a_i, b_i)\) (\(1\leq a_i < b_i\leq 8\,640\,000\))² v ktorom je otvorená burza \(i\).

V polovici sád testovacích vstupov navyše platí, že \(t \leq 250\).

Formát výstupu

Vypíšte práve tri riadky.

Na prvom riadku vypíšte číslo \(p\) udávajúce najmenší možný počet ujdených príležitostí.

Na druhom riadku vypíšte číslo \(m \leq 250\,000\) udávajúce počet účastí na prednáškach.

Na treťom riadku vypíšte zoradenú postupnosť \(m\) čísiel \(u_i\) oddelených medzerami udávajúcu časy, v ktorých keď sa Cyril ukáže na prednáškach, ujde mu najviac \(p\) príležitostí. Prvé číslo \(u_1\) musí byť menšie alebo rovné času otvorenia prvej burzy a posledné musí byť väčšie alebo rovné času zatvorenia poslednej burzy.³ Rozdiel dvoch susedných čísiel musí byť \(1 \leq u_{i+1} - u_i \leq t\).

Vo všetkých testovaných vstupoch stačí Cyrilovi ukázať sa na prednáškach maximálne \(250\,000\) krát, dlhšie postupnosti nie je ochotný uznať.

Príklady

Input:

Output:

0
3
100 200 300

Cyril sa stíha zúčastniť sa prednášky v čase 200 bez toho aby mu ušla nejaká príležitosť.

Input:

Output:

3
3
100 250 400

V čase 250 Cyrilovi ujdu príležitosti na všetkých troch burzách.

Input:

Output:

3
4
50 190 300 400

Iné platné riešenie pre predchádzajúci vstup. V čase 190 Cyrilovi ujdú príležitosti na prvých dvoch burzách, v čase 300 na tretej burze.

Input:

Output:

3
4
50 130 270 400

Ďalšie platné riešenie pre predchádzajúci vstup. V čase 130 Cyrilovi ujde príležitosť na prvej burze, v čase 270 znovu na prvej a aj na tretej burze.

Cyrilovi stačí na prednáške sa iba ukázať, nemusí tam stráviť žiaden čas. Ak sa jedna burza v nejakom čase zatvára a druhá burza sa v tom čase otvára, Cyril sa v tomto čase stíha ukázať na prednáške bez toho aby mu ušla príležitosť na týchto burzách.↩︎
\(8\,640\,000 = 24 \cdot 3600 \cdot 100\), počet centisekúnd v jednom dni.↩︎
Keď už sú všetky burzy zatvorené, vie si Cyril sám určiť kedy sa zúčastní prednášok a nepotrebuje s tým vašu pomoc.↩︎

Pomalé riešenie

Máme nájsť postupnosť časov, v ktorých sa má Cyril ukázať na prednáškach tak, aby mu ušlo čo najmenej príležitostí na investovanie. Toto môžeme riešiť dynamikou nasledovne: Nech \(o_i\) je najmenší možný počet ujdených príležitostí do času \(i\) (vrátane), ak sa Cyril ukáže na prednáške v čase \(i\). Potom je \(o_{8\;640\;000}\) riešenie úlohy, najmenší možný počet ujdených príležitostí do konca dňa.¹

Nech \(p_i\) je počet príležitostí, ktoré Cyrilovi ujdú zúčastnením sa prednášky v čase \(i\), teda počet búrz otvorených v čase \(i\). Potom je \(o_i = p_i + \min_{i-t \leq j < i} o_j\), keďže v čase \(i\) Cyrilovi ujde \(p_i\) príležitostí, a pred tým sa musel zúčastniť na prednáške niekedy v intervale \(\left<i-t, i\right)\). Na to, aby sme našli aj postupnosť časov, v ktorých sa má Cyril zúčastniť prednášok, stačí nám uložiť si pri počítaní \(o_i\) aj zvolený čas \(j\) predchádzajúcej účasti na prednáške.

Aby sme nevypisovali zbytočne veľa účastí, stačí úlohu riešiť na intervale \(\left<\min_{0 \leq i < n} a_i, \max_{0 \leq i < n} b_i\right>\), keďže podľa zadania si Cyril vie mimo tohto intervalu poradiť aj sám. Zadanie nám zaručuje, že najlepšie riešenie v tomto intervale bude dostatočne krátke.

Nakoniec ešte musíme nájsť postupnosť časov, v ktorých sa má Cyril ukázať na prednáškach. Keďže sme si pre každé \(o_i\) zapísali čas predchádzajúcej účasti na prednáške, stačí postupovať od konca vždy k predchádzajúcemu času, a jednotlivé časy si zapisovať. Toto je jednoduchý cyklus kratší ako počítanie \(o_i\), takže nám časovú ani pamäťovú zložitosť neovplyvní.

Nech \(d = \max_{0 \leq i < n} b_i - \min_{0 \leq i < n} a_i + 1\) je dĺžka intervalu, v ktorom hľadáme riešenie. Najjednoduchší spôsob ako vypočítať hodnoty \(p_i\) je v cykle spočítať ktoré burzy sú otvorené v čase \(i\), čo má časovú zložitosť \(O(dn)\). Hodnoty \(o_i\) potom môžeme zrátať cyklom v čase \(O(dt)\), teda celková časová zložitosť je \(O(dn + dt)\), čo stačí na prvú sadu vstupov za 2 body.

Rýchle riešenie

Hodnoty \(p_i\) a \(o_i\) je samozrejme príliš pomalé počítať cyklom.

Ak by sme mali hodnoty \(a_i\) a \(b_i\) usporiadané od najmenšej, \(p_i\) môžeme vypočitať ako rozdiel počtu začiatkov a koncov intervalov od času \(0\) po aktuálny čas, na čo nám stačí prejsť oba utriedené zoznamy po jednotlivých centisekundách pomocou dvoch indexov. Počet búrz otvorených v danej centisekunde je totiž rovný počtu búrz, ktoré boli otvorené pred touto centisekundou, mínus počet búrz, ktoré boli zatvorené najneskôr v tejto centisekunde. To vieme vypočítať ako počet búrz \(p_{i-1}\), ktoré boli otvorené v predchádzajúcej centisekunde, zväčšený o jedna pre každú burzu, ktorá sa otvára v čase \(i-1\), a zmenšený o jedna pre každú burzu, ktorá sa zatvára v čase \(i\). Keďže ale najprv musíme zoznamy \(a_i\) a \(b_i\) utriediť, má toto časovú zložitosť \(O(n \log n + d)\).

Počítanie \(o_i\) vieme zrýchliť tým, že namiesto cyklu vyberieme najmenšie hodnoty \(o_j\) pomocou intervalového stromu alebo haldy. Ľahšie je použiť haldu, keďže tá je vstavaná vo väčšine programovacích jazykov.² Stačí nám každú vypočítanú hodnotu \(o_i\) vložiť do haldy, a pri hľadaní najmenšieho \(o_j\) najprv vyhodíme tie hodnoty, ktoré sú už príliš staré. Nakoniec nám na vrchu haldy vždy ostane minimum. Túto časť teda vieme vypočítať s časovou zložitosťou \(O(d \log d)\).

Celkové riešenie má teda časovú zložitosť \(O(d \log d + n \log n)\). Na toto riešenie potrebujeme \(O(d + n)\) pamäte, keďže si musíme pamätať celý vstup dĺžky \(n\) na to, aby sme ho mohli utriediť, a pre každú z \(d\) hodnôt \(o_i\) si musíme pamätať čas predchádzajúcej hodnoty \(o_j\). Dobre napísané riešenie s touto časovou zložitosťou by malo prejsť všetky štyri sady vstupov.


#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    long long t, n;
    cin >> t >> n;

    // nacitaj intervaly burz a_min utried ich
    vector<long long> starts(n), ends(n);
    for (long long i = 0; i < n; i++) {
        cin >> starts[i] >> ends[i];
    }
    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());

    long long a_min = starts[0];
    long long b_max = ends[n - 1];
    long long d = b_max - a_min + 1;

    vector<long long> cost(d), prev(d);
    priority_queue<pair<long long, long long>,
                   vector<pair<long long, long long>>,
                   greater<pair<long long, long long>>> best;
    prev[0] = -1;
    best.emplace(0, a_min);

    long long p_i = 0;
    auto starts_it = starts.cbegin(), ends_it = ends.cbegin();
    auto starts_end = starts.cend(), ends_end = ends.cend();
    for (long long i = a_min + 1; i <= b_max; i++) {
        // pricitaj burzy ktore sa otvaraju v case < i
        while (starts_it != starts_end && *starts_it < i) {
            ++starts_it;
            p_i++;
        }

        // odcitaj burzy ktore sa zatvaraju v case <= i
        while (ends_it != ends_end && *ends_it <= i) {
            ++ends_it;
            p_i--;
        }

        while (best.top().second + t < i)
            best.pop(); // odstran prilis stare o_j z haldy

        auto x = best.top();
        cost[i - a_min] = x.first + p_i; // vypocitaj o_i
        prev[i - a_min] = x.second;

        best.emplace(cost[i - a_min], i); // vloz o_i do haldy
    }

    // rekonstrukcia postupnosti
    vector<long long> out;
    out.push_back(b_max);
    long long i = b_max;
    while (prev[i - a_min] != -1) {
        out.push_back(prev[i - a_min]);
        i = prev[i - a_min];
    }

    cout << cost[b_max - a_min] << '\n';
    cout << out.size() << '\n';
    bool first = true;
    for (auto it = out.rbegin(), en = out.rend(); it != en; ++it) {
        if (first)
            first = false;
        else
            cout << ' ';
        cout << *it;
    }
    cout << '\n';
}

import heapq
import sys


def main():
    t = int(sys.stdin.readline())
    n = int(sys.stdin.readline())

    # nacitaj intervaly burz a_min utried ich
    starts = [0] * n
    ends = [0] * n
    for i in range(n):
        a_i, b_i = sys.stdin.readline().split(maxsplit=1)
        starts[i] = int(a_i)
        ends[i] = int(b_i)
    starts.sort()
    ends.sort()

    a_min = starts[0]
    b_max = ends[-1]
    d = b_max - a_min + 1

    cost = [0] * d
    prev = [0] * d

    prev[0] = -1
    best = [(0, a_min)]

    p_i = 0
    starts_it = 0
    ends_it = 0
    for i in range(a_min + 1, b_max + 1):
        # pricitaj burzy ktore sa otvaraju v case < i
        while starts_it < n and starts[starts_it] < i:
            starts_it += 1
            p_i += 1

        # odcitaj burzy ktore sa zatvaraju v case <= i
        while ends_it < n and ends[ends_it] <= i:
            ends_it += 1
            p_i -= 1

        # odstran prilis stare o_j z haldy
        while best[0][1] + t < i:
            heapq.heappop(best)

        best_cost, best_prev = best[0]
        cost[i - a_min] = best_cost + p_i  # vypocitaj o_i
        prev[i - a_min] = best_prev
        heapq.heappush(best, (best_cost + p_i, i))  # vloz o_i do haldy

    # rekonstrukcia postupnosti
    out = []
    i = b_max
    while i != -1:
        out.append(str(i))
        i = prev[i - a_min]

    print(cost[-1])
    print(len(out))
    print(*reversed(out))


if __name__ == '__main__':
    main()

Rýchlejšie riešenie

Výpočty \(p_i\) aj \(o_i\) sa dajú ešte zrýchliť, a pri tom vieme vylepšiť aj pamäťovú zložitosť.

Ako prvé môžeme zrýchliť výpočet \(p_i\) tým, že sa zbavíme triedenia hodnôt \(a_i\) a \(b_i\). To vieme spraviť tak, že si najprv pripravíme hodnoty \(p_i'\) určujúce počet búrz, ktoré sa otvárajú v danú centisekundu, mínus počet búrz, ktoré sa zatvárajú v nasledujúcej centisekunde. Hodnoty \(p_i\) potom dostaneme jednoducho prefixovými súčtami \(p_i = \sum_{0 \leq j < i} p_j'\). Toto je správne preto, lebo takto do \(p_i\) zarátame počet všetkých búrz otvorených pred časom \(i\) (pretože každá z týchto búrz je započítaná v jednom z \(p_j'\) pre \(j<i\)) a odrátame počet všetkých búrz zatvorených najneskôr v čase \(i\) (pretože každá z týchto búrz je odpočítaná v jednom z \(p_j'\) pre \(j<i\)). Táto časť má časovú zložitosť \(O(d+n)\), keďže potrebujeme \(O(n)\) času na zarátanie každej burzy a \(O(d)\) času na zrátanie prefixových súčtov.

Výpočet \(o_i\) môžeme zrýchliť nasledovným pozorovaním. Ak pre \(m < n\) platí \(o_m \geq o_n\), hodnotu \(o_m\) už nepoužijeme pre žiadne ďalšie \(o_i\) s \(i > n\), keďže ak môžeme použiť \(o_n\), je to vždy prinajhoršom rovnako dobrá voľba ako \(o_m\), a hodnotu \(o_n\) budeme môcť použiť aj pre \(n + t \geq i > m + t\) (narozdiel od \(o_m\)). Pri výpočte \(o_i\) nám preto stačí pamätať si iba rastúcu podpostupnosť predchádzajúcich hodnôt \(o_j\), a vždy keď nájdeme hodnotu, ktorá je menšia ako nejaké číslo v tejto podpostupnosti, predchádzajúce číslo môžeme zabudnúť. Taktiež môžeme vždy zabudnúť hodnoty, ktoré sú síce malé, ale už príliš staré. Preto vieme každé číslo \(o_i\) vypočítať v konštantnom čase. Udržiavanie tejto podpostupnosti nám zaberie dokopy \(O(d)\) času, keďže každé číslo do nej vložíme a z nej odstránime maximálne raz.

Celkové riešenie má teda časovú zložitosť \(O(d + n)\). Keďže sme sa zbavili triedenia, vieme toto riešenie naprogramovať s pamäťovou zložitosťou \(O(d)\), lebo stačí aby sme si pamätali hodnoty \(p_i'\), konkrétne intervaly jednotlivých búrz nás nezaujímajú (samozrejme, musíme si pamätať aj \(o_i\), predchádzajúce časy, atď., ale to je tiež \(O(d)\)).


#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    long long t, n;
    cin >> t >> n;

    // nacitaj interval prvej burzy
    long long a_min, b_max;
    cin >> a_min >> b_max;
    long long d = b_max - a_min + 1;

    // zapis prvy interval do p'
    deque<long long> p(d);
    p[1] += 1;
    p[b_max - a_min] -= 1;

    for (long long i = 1; i < n; i++) {
        // nacitaj ostatne intervaly burz
        long long ai, bi;
        cin >> ai >> bi;
        if (ai < a_min) {
            // zvacsi pole p' na lavej strane
            p.insert(p.cbegin(), a_min - ai, 0);
            a_min = ai;
        }
        if (bi > b_max) {
            // zvacsi pole p' na pravej strane
            p.insert(p.cend(), bi - b_max, 0);
            b_max = bi;
        }
        // uloz interval do p'
        p[ai - a_min + 1] += 1;
        p[bi - a_min] -= 1;
    }

    d = b_max - a_min + 1;

    vector<long long> cost(d), prev(d);
    deque<pair<long long, long long>> best; // podpostupnost malych o_i
    prev[0] = -1;
    best.emplace_back(0, a_min);

    long long p_sum = p[0];
    for (long long i = a_min + 1; i <= b_max; i++) {
        p_sum += p[i - a_min]; // prefixovy sucet

        while (best.front().second + t < i)
            best.pop_front(); // odstran stare hodnoty o_j

        auto x = best.front();
        cost[i - a_min] = x.first + p_sum; // vypocitaj o_i
        prev[i - a_min] = x.second;

        while (!best.empty() && best.back().first >= cost[i - a_min])
            best.pop_back(); // odstran vacsie hodnoty o_j
        best.emplace_back(cost[i - a_min], i); // uloz novu hodnotu o_i
    }

    // rekonstrukcia postupnosti
    vector<long long> out;
    out.push_back(b_max);
    long long i = b_max;
    while (prev[i - a_min] != -1) {
        out.push_back(prev[i - a_min]);
        i = prev[i - a_min];
    }

    cout << cost[b_max - a_min] << '\n';
    cout << out.size() << '\n';
    bool first = true;
    for (auto it = out.rbegin(), en = out.rend(); it != en; ++it) {
        if (first)
            first = false;
        else
            cout << ' ';
        cout << *it;
    }
    cout << '\n';
}

Každá burza sa zatvára najneskôr na konci dňa, takže touto účasťou na prednáške Cyrilovi neujdú žiadne príležitosti.↩︎
priority_queue v C++, heapq v Pythone, java.util.PriorityQueue v Jave↩︎

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

6. Cyrilove investície vzorové riešenie

Zadanie

Úloha

Formát vstupu

Formát výstupu

Príklady

Pomalé riešenie

Rýchle riešenie

Rýchlejšie riešenie

Diskusia