Matfyz Wiki
Zadani
co největší popis a,b-stromů.
DFS, jak tam fungují cykly, pojmenování hran
setřiď posloupnost N čísel, kde různých čísel je K, kde K je mnohem menší, jak N (lineárně)
vypiš nejdelší cestu (o nejvíce hranách) z těch nejlevnější cest mezi A a B v grafu
najdi nejdelší souvislou podposloupnost čísel, ve které se čísla neopakují.
Reseni
(1) viz Průvodce
(2) viz Průvodce
(3) zmenšení na posloupnost K čísel (v lineárním čase -> je potřeba zvolit chytře Datovou strukturu (více možností)), normální sort - třeba marge -> O(klogk + n)-> O(n)
(4)Upravená Dijkstra
(5) Rozděluj a panuj
Poznamky
Bohatě stačí shlédnout natočené přednášky Mareše z roku 2015 a párkrát si projít od něj vyfocené tabule. Nic víc v testu nebude. Průvodce je prej taky dobrej.