DomJudge - 04Heslo¶
41 riešení
| jazyk | Počet | Čas | Znakov |
|---|---|---|---|
C++ |
5 | 0,01 - 0,02 s | 1.850 - 5.481 B |
Java |
19 | 0,19 - 8,26 s | 1.588 - 8.662 B |
Python |
17 | 0,1 - 6,91 s | 747 - 2.763 B |
Úloha sa dá riešiť simuláciou programu uvedeného v zadaní. Napríklad pre vzorový vstup +--+- môžeme začať simuláciu so štvoricou a, b, c, d (neznáme). Podľa znamienok na vstupe budeme vymienať poradie týchto neznámych až dostaneme na konci postupnosť d, a, c, b. A keďže vieme, že výsledkom je usporiadaná permutácia čísel 1 až 4, tak pôvodná postupnosť musela byť 2, 4, 3, 1.
- vstup je potrebné spracovať po znakoch, prípadne prechádzať podľa indexu (nie skracovať ho)
%%time
pole = list('a'*100_000)
while len(pole) > 0:
pole = pole[1:]
CPU times: total: 25.8 s Wall time: 25.8 s
%%time
pole = list('a'*100_000)
while len(pole) > 0:
pole.pop(0)
CPU times: total: 3.42 s Wall time: 3.41 s
%%time
pole = list('a'*100_000)
while len(pole) > 0:
pole.pop()
CPU times: total: 62.5 ms Wall time: 62.4 ms
%%time
pole = list('a'*100_000)
for index in range(len(pole)):
znak = pole[index]
CPU times: total: 31.2 ms Wall time: 31.3 ms
%%time
pole = list('a'*100_000)
for index, prvok in enumerate(pole):
znak = prvok
CPU times: total: 15.6 ms Wall time: 15.6 ms
Štruktúry údajov¶
R. Sedgewick, K. Wayne: Algorithms (4th Edition), Addison-Wesley Professional, 2011, ISBN 978-0321573513 https://algs4.cs.princeton.edu/12oop/
Abstraktná štruktúra údajov / Abstraktná dátová štruktúra
- dátový typ (množina hodnôt a súbor operácií nad nimi), ktorý je prístupný iba cez rozhranie. Konkrétnu implementáciu využívajú programy ako klienti. Z pohľadu používania je to čierna skrinka.
- Štruktúry údajov
http://opendatastructures.org/ods-python/
https://kubokovac.eu/gnarley-trees/
https://algs4.cs.princeton.edu/12oop/
- Implementácie v jednotlivých jazykoch uvádzajú zložitosť v dokumentácii
https://docs.python.org/3/library/heapq.html :
https://en.cppreference.com/w/cpp/container/deque :
https://docs.oracle.com/en/java/javase/23/docs/api/java.base/java/util/ArrayList.html :
Zásobník Stack¶
- Last In, First Out
push/put,pop/get,empty
Rad Queue¶
- First In, First Out
- put, get, empty
Prioritný rad Priority Queue¶
vyberáme podľa priority (najmenšej-najväčšej hodnoty)
pohľad zvonku
- put, get, empty
pohľad zvnútra
- veľa rôznych implementácií - pole, usporiadené pole, spájaný zoznam, usporiadaný spájaný zoznam, halda
Abstraktné dátové štruktúry v praxi¶
http://foja.dcs.fmph.uniba.sk/ads/skripta/99ads-lang.pdf
| Štruktúra | C++ | Python | Java |
|---|---|---|---|
| dynamické pole | vector |
[] |
ArrayList, Vector |
| zásobník | stack |
queue.LifoQueue |
Stack |
| rad | queue |
queue.Queue |
Queue |
| prioritný rad | priority_queue |
queue.PriorityQueue |
PriorityQueue |
| obojsmerný rad | dequeue |
collections.dequeue |
bez indexovania Deque |
| spájaný zoznam | list (jednosmerný) slist |
pypi.llist |
LinkedList |
| usporiadaná množina | set, multiset |
sortedcontainers.SortedSet |
TreeSet |
| neusporiadaná množina | C++11 unordered_set |
set |
HashSet |
| neusp. asociatívne pole | C++11 unordered_map |
{} |
HashMap |
| usp. asociatívne pole | map |
sortedcontainers.SortedDict |
TreeMap |
from queue import Queue, LifoQueue, PriorityQueue
def ads_test(ads):
ads.put(5)
ads.put(7)
ads.put(2)
while not ads.empty():
print(ads.get())
print('Rad:')
ads_test(Queue())
print('Zasobnik:')
ads_test(LifoQueue())
print('Prioritny rad:')
ads_test(PriorityQueue())
Rad: 5 7 2 Zasobnik: 2 7 5 Prioritny rad: 2 5 7
Prioritný rad - pohľad zvnútra¶
| implementácia | vloženie prvku | nájdenie najmenšieho prvku | odstránenie najmenšieho prvku | ||
|---|---|---|---|---|---|
| pole | |||||
| usporiadané pole | |||||
| spájaný zoznam začiatok+nasledovník |
|||||
| obojsmerný spájaný zoznam začiatok,koniec+nasledovník a prechodca |
|||||
| usporiadaný spájaný zoznam | |||||
| binárna halda |
| implementácia | vloženie prvku | nájdenie najmenšieho prvku | odstránenie najmenšieho prvku | spojenie dvoch prioritných radov |
|---|---|---|---|---|
| pole | $O(n)$ | $O(n)$ | $O(n)$ | $O(n+m)$ |
| usporiadané pole | $O(n)$ | $O(1)$ | $O(n)$, resp. $O(1)$, ak na konci poľa môžu byť neobsadené prvky |
$O(n+m)$ |
| spájaný zoznam-začiatok+nasledovníci | $O(1)$ | $O(n)$ | $O(n)$ | $O(\min\{n,m\})$ |
| obojsmerný spájaný zoznam-začiatok,koniec+nasledovníci a prechodcovia | $O(1)$ | $O(n)$ | $O(n)$ samotné odtránenie je v $O(1)$ |
$O(1)$ |
| usporiadaný spájaný zoznam | $O(n)$ | $O(1)$ | $O(1)$ | $O(n+m)$ |
| binárna halda | $$O(\log n)$$ | $O(1)$ | $O(\log n)$ | $$\min\{n,m\} \cdot \log (n+m)$$ resp. metódou heapify v čase $O(n+m)$ |
| binomický rad | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ | $O(\log n)$ |
| Fibonacciho halda | $O(1)$ | $O(1)$ | $O(\log n)$ | $O(1)$ |
https://en.wikipedia.org/wiki/Priority_queue
https://en.wikipedia.org/wiki/Weak_heap https://link.springer.com/content/pdf/10.1007/BF01990520.pdf
Binomický rad (1978 Jean Vuillemin)¶
https://www.cs.princeton.edu/~appel/Binom.pdf
- halda mocniny 2 (zľava haldovo usporiadaný binárny strom, ľavý podstrom úplný binárny strom, pravý je prázdny)
- spojenie 2 háld mocniny 2
- binomický rad (množina háld mocniny dva, navzájom rôznych veľkostí)
reprezentácia pomocou zľava haldovo usporiadaného binomického stromu
$ 13 = (1101)_2$
Úloha 1 - súčet súvislej podpostupnosti¶
Pre danú postupnosť $pole[]$ a indexy $a, b$ vypočítajte súčet $pole[a]+pole[a+1]+\dots+pole[b]$.
Ako efektívne vypočítať súčet hodnôt na intervale?
Priamočiare riešenie je prejsť všetky hodnoty a spočítať súčet hodnôt
#vstupne hodnoty
pole = [16, 19, 40, 26, 19, 39, 26, 18, 18, 21, 32, 12, 27, 8, 25, 18, 18, 17, 42, 4]
a, b = 2, 6
sucet = 0
for i in range(a, b+1):
sucet += pole[i]
print(sucet)
150
sum(pole[a:b+1])
150
Čo ak potrebujeme takýchto súčtov počítať veľa? Napríklad aké sú vzdialenosti medzi mestami počas jazdy vlakom. Hodnoty uvedené vyššie sú vzdialenosti na jednotlivých úsekoch na trase Košice-Bratislava. Na každý zakúpený lístok sa vytlačí prejdená vzdialenosť na trase, ktorá určuje výslednú cenu.
Aby sa nemuselo zakaždým počítať (čo by malo zložitosť $\Theta(n \cdot q)$, kde $n$ je počet prvkov v poli a $q$ je počet otázok/lístkov), tak by sme mohli napr. všetky dvojice predpočítať do dvojrozmerného poľa sucet[i][j] a potom odpovedať v konštantom čase. To vieme urobiť v čase $\Theta(n^2 \cdot n)=\Theta(n^3)$, ale aj dynamickým programovaním v čase $\Theta(n^2)$. Celková časová zložitosť by bola $\Theta(n^2+q)$, čo pri veľkom počte otázok ($q>>n$, teda $q$ je rádovo väčšie ako $n$) už bude efektívnejšie. Predpočítanie ako aj pamäťová zložitosť je $\Theta(n^2)$.
Ak by sme sa pozreli na cestovný poriadok vlaku (cp.sk), tak by ste asi vzdialenosť z Margecian do Ružomberka (teda od indexu 2 po index 6) vedeli vypočítať asi aj z hlavy ako rozdiel 185−35=150
Prefixový súčet¶
Vidíme, že stačí si pamätať súčty od začiatku (prvý stĺpec na vyššie uvedenom obrázku), tzv. prefixové súčty, a potom rýchlo vypočítame súčet na intervale ako rozdiel dvoch hodnôt. Súčet od $a$ po $b$, t.j. $sum([a:b+1])=sum([0:b+1)−sum([0:a])$, teda $sum([a:b+1])=PS[b+1]−PS[a]$
, keďže prefixový súčet začína nulou (aby sa dalo počítať aj od indexu nula, začiatku).
Tento súčet vieme vypočítať v čase aj v pamäti $\Theta(n)$ , postupním pripočítavaním:
#vstup: pole, a, b
n = len(pole)
PS = [0 for _ in range(n+1)] #prefixovy sucet
for i in range(n):
PS[i+1] = PS[i]+pole[i]
print(PS)
print(PS[b+1]-PS[a])
[0, 16, 35, 75, 101, 120, 159, 185, 203, 221, 242, 274, 286, 313, 321, 346, 364, 382, 399, 441, 445] 150
- máme ADŠ, kde súčet na intervale vieme vypočítať v konštantom čase
V jazyku Python to (bez úvodnej nuly) vieme vypočítať aj použitím funckie accumulate z knižnice itertools:
import itertools
print(*itertools.accumulate(pole))
16 35 75 101 120 159 185 203 221 242 274 286 313 321 346 364 382 399 441 445
Úloha 2 - minimum súvislej podpostupnosti¶
Pri nákupoch cez verejné obstarávanie sa vyberá zvyčajne najnižšia cena. Ako overiť, či vysúťažená cena bola naozaj najnižšia? Predstavme si, že vláda objednala pre svojich občanov respirátory. Z dostupných zverejnených cien v rôznych dňoch overte, či nákup bol efektívny. Teda zistite najmenšiu cenu dostupnú v období zverejnenia verejného obstarávania (čo je niekoľko dní). Napríklad si vezmime vývoj ceny respirátora FPP2 na Heureke:
Aká bola minimálna cena v období 11/2019-12/2019 a aká v období medzi 22.3.2020 a 25.3.2020 ?
Nájsť minimum na súvislom úseku v poli môžeme obdobne ako súčet riešiť priamočiaro
pole = [1, 1, 1, 1, 1, 2, 19, 9]
a, b = 5, 7 #minimum na indexoch od 5 az po 7
m = pole[a] #zacneme prvym prvkom
for index in range(a+1, b+1): #postupne prechadzame dalsie prvky
if pole[index] < m: #ak najdeme mensi prvok
m = pole[index] #zaktualizujem si doteraz najmensi prvok
#m = min(m, pole[index]) ... kratsi zapis pouzitim funkcie min
print(m)
2
V jazyku Python s použitím funkcie min priamo na "rez" (slice) poľa:
#minimum na intervale 4 az 5
a, b = 4, 5
print(a, '-', b, ':', min(pole[a:b+1]))
#minimum na intervale 5 az 7
a, b = 5, 7
print(f"{a} - {b} : {min(pole[a:b+1])}") #formatovanie retazca v Python 3
4 - 5 : 1 5 - 7 : 2
V prípade veľa otázok/dopytov na minimálnu cenu to zase nie je efektívne. Ako to zrýchliť?
"Prefixovým minimom" to nepôjde ... minimum na úseku <a,b> nevieme určiť z miním na úsekoch <0,a−1>,<0,b>. Pomôže nám nasledujúca štruktúra.
Intervalový strom¶
Nad poľom (graficky) si vytvoríme úplný binárny strom a vyplníme tak, že hodnota vo vrchole bude minimum zo všetkých hodnôt v listoch v podgrafe z daného vrchola (grafová terminológia), teda minimum zo všetkých hodnôt v jeho podstrome. V intervalovom strome môžu byť použité aj funkcie max, sum. (Obrázok z interaktívnej vizualizácie[https://people.ksp.sk/~kuko/gnarley-trees/]) Ukladať si daný strom môžeme do poľa rovnako ako haldu. Na obrázku sú pri vrcholoch aj čísla udávajúce reprezentujúci interval podstromu daného vrcholu.
Najmenšiu hodnodu na intervale a dokonca aj aktualizáciu, teda zmenu hodnoty prvku vieme potom urobiť v čase Θ(logn). Zmena hodnoty prvku (v poli/liste stromu) znamená aktualizáciu všetkých hodnôt smerom nahor (ku koreňu). Pre najmenšiu hodnotu na intervale treba prejsť niektoré vrcholy - podstromy. Napríklad pre interval 6. až 8. hodnoty treba vybrať minimum z dvoch červenou zvýraznených hodnôt:
Pre 15 hodnôt a interval 3-15 by to vyzeralo nasledovne:
Vidíme, že sa doplní na veľkosť mocniny dva a zoberú sa do úvahy len 4 červeno zvýrazné prvky - tie sa nájdu prechodom od krajného prvku ku koreňu (zvýraznené modrou farbou, teda dvakrát výška stromu), t.j. v časovej zložitosti Θ(2.logn)=Θ(logn).
pole[2:7]
Úloha 3 - predaj miesteniek¶
Vrátime sa k ceste vlakom. Úlohou je teraz implementovať rezervačný systém miesteniek. Máme zadanú kapacitu vlaku a postupne požiadavky na kúpu lístka (medzi 2 stanicami pre x ľudí).
Obsadenosť si môžeme uložiť do intervalového stromu. Zistenie, či je voľná kapacita na zakúpenie lístka vieme urobiť nájdením maximálnej obsadenosti na intervale medzi 2 stanicami a porovnaním s celkovou kapacitou vlaku a počtom ľudí. Po zakúpení by ale bolo potrebné aktualizovať viacero hodnôt a celý podstrom nad nimi, čo by zhoršilo časovú zložitosť. Efektívne sa to dá riešiť zaznamenaním prírastkov do všetých červených vrcholoch (+x). Podrobnejšie informácie nájdete v úlohe z Olympiády v informatike OI-2007-A-I-2 [http://oi.sk/archiv/2007/sl-2007-1-zad-A_a4.pdf#5] so vzorovým riešením.
Segmentový strom Segment Tree¶
- rozdelenie postupnosti na spôsob usporiadania spájaním (na dve polovice, "menšiu" $\left\lfloor\frac{n}{2}\right\rfloor$ a "väčšiu" $\left\lceil\frac{n}{2}\right\rceil$)
pre mocniny dvojky je zhodný s intervalovým stromom
1 3 -2 8 -7
Fínsky/Fenwickov strom Fenwick Tree/Binary Index Tree¶
- strom uložený v poli $ft$, efektívne počíta súčet od začiatku
- hodnota $ft[i]$ je súčet predchádzajúcich $2^k$ hodnôt, pričom $k$ je pozícia posledného jednotkového bitu
lowbitv binárnom zápise čísla $i$ - $ \text{lowbit}(i) = i \text{&} (−i) $ pri reprezentácii záporného čísla ako dvojkový doplnok, teda $-k == \neg(k) + 1$ (zmena/negácia všetkých bitov a pripočítanie jedničky)
nedá sa priamočiaro použiť pre min/max ... sú potrebné 2 fínske stromy+pole
def pripocitaj(index, hodnota):
print('Pridavam:', index, end=' ...')
while index < len(ft):
print(f' {index}', end='')
ft[index] += hodnota
index += index & (-index)
print()
def prefixovy_sucet(index):
print('pref. sucet', index, end=":")
sucet = 0;
while index > 0:
print(f' {index} (+{ft[index]})', end="")
sucet += ft[index]
index = index & (index-1) #vynuluje posledny jednotkovy bit
print()
return sucet
i = 3
i + (i & (-i))
4
i = 4
i + (i & (-i))
8
$3 = (11)_2$, $-3 = (11111101)_2$
$ 3 \& -3 = (00000011)_2 \& (11111101)_2 = (00000001)_2 $
$4 = (100)_2$, $-4 = (11111100)_2$
$ 4 \& -4 = (00000111)_2 \& (11111100)_2 = (00000100)_2 $
i = 6
i & (i-1)
4
i = 4
i & (i-1)
0
$6 = (110)_2$
$5=(101)_2$
$4=(100)_2$
$3=(011)_2$
$0=(000)_2$
efektívne prechádza všetky jednotky v binárnom zápise čísla (vynuluje najpravejšiu jednotku)
pole = [10+3*i for i in range(1, 17)]; print(*pole)
13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58
ft = [0 for i in range(1+len(pole))] #nulty prvok nepouzivame
for i in range(len(pole)): #nastav hodnoty 1 az 16
pripocitaj(i+1, pole[i]) #zaciname od indexu 1
print('FT:', *ft); print('Vysledok', prefixovy_sucet(13))
sum(pole[:13])
Pridavam: 1 ... 1 2 4 8 16 Pridavam: 2 ... 2 4 8 16 Pridavam: 3 ... 3 4 8 16 Pridavam: 4 ... 4 8 16 Pridavam: 5 ... 5 6 8 16 Pridavam: 6 ... 6 8 16 Pridavam: 7 ... 7 8 16 Pridavam: 8 ... 8 16 Pridavam: 9 ... 9 10 12 16 Pridavam: 10 ... 10 12 16 Pridavam: 11 ... 11 12 16 Pridavam: 12 ... 12 16 Pridavam: 13 ... 13 14 16 Pridavam: 14 ... 14 16 Pridavam: 15 ... 15 16 Pridavam: 16 ... 16 FT: 0 13 29 19 70 25 53 31 188 37 77 43 166 49 101 55 568 pref. sucet 13: 13 (+49) 12 (+166) 8 (+188) Vysledok 403
403
pref. sucet 13: 13 (+49) 12 (+166) 8 (+188)
