13 riešení
jazyk | Počet | Čas | Veľkosť |
---|---|---|---|
C++ |
1 | 1,07 s | 56 / 1.615 |
Java |
8 | 0,39 - 1,46 s | 68 - 111 / 1.944 - 3.300 B |
Python |
4 | 0.13 - 1,71 s | 7953 - 1.424 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
.
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
http://opendatastructures.org/ods-python/
https://people.ksp.sk/~kuko/gnarley-trees/Intro.html
https://algs4.cs.princeton.edu/12oop/
https://python.readthedocs.io/en/stable/library/heapq.html :
https://en.cppreference.com/w/cpp/container/deque :
https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html :
Stack
¶push
/put, pop
/get, empty
Queue
¶Priority Queue
¶vyberáme podľa priority (najmenšej-najväčšej hodnoty)
pohľad zvonku
pohľad zvnútra
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
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
https://www.cs.princeton.edu/~appel/Binom.pdf
$ 13 = (1101)_2$
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
Vidíme, že stačí si pamätať súčty od začiatku (posledný stĺpec vpravo 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
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
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.
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=[i for i in range(15)]
print(pole)
zobraz_intervalovy_strom(pole)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
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 potrebané 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.
Segment Tree
¶pre mocniny dvojky je zhodný s intervalovým stromom
1 3 -2 8 -7
Fenwick Tree
/Binary Index Tree
¶lowbit
v binárnom zápise čísla $i$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)