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.
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.1 Každá burza otvorená v tomto čase sa ráta za jednu ujdenú príležitosť.
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$)2 v ktorom je otvorená burza $i$.
V polovici sád testovacích vstupov navyše platí, že $t \leq 250$.
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.3 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ť.
Input:
100
2
100 200
200 300
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:
150
3
100 300
140 260
190 350
Output:
3
3
100 250 400
V čase 250 Cyrilovi ujdu príležitosti na všetkých troch burzách.
Input:
150
3
100 300
140 260
190 350
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:
150
3
100 300
140 260
190 350
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. ↩
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.1
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.
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.2 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()
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';
}
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete