Seznam účastníků a rozdělení témat

zdary.pdf

Přibližně návodná ukázka struktury prezentace: Voda v rourách

Návodník na řešení

malá kategorizace grafových úloh

V průběhu praktických cvičení (sudé výukové týdny) svá řešení budete odevzdávat do A2 Online Judge. Prosíme, vytvořte si každý svůj vlastní účet sledováním následujícího linku: Sign Up. Vzhledem k tomu, že A2 Online Judge je pouze tzv. agregátor výsledků, musíte si vytvořit účty v příslušných judgích, které skutečně ověřují správnost vašich řešení, a to: Sphere Online Judge, UVa Online Judge a ACM-ICPC Live Archive.

Aby A2OJ věděl o odevzdaných úlohách, musíte vyplnit ve svém profilu ID, které jste si vytvořili či vám bylo přiděleno u výše uvedených judgů. Zde je shrnut postup, jak se k nim dostat:

1. Neuvěřitelné, ale login je vaše ID.

1. V hlavním menu po přihlášení ťukněte na [My Account]
2. Ve vašem profilu na řádku _Online Judge ID:_ je Vaše UVA ID.

• Postup je stejný jako u UVA Online Judge.

Po vytvoření účtů se můžete registrovat do soutěže na A2 Online Judge, klikněte na příslušný odkaz do A2OJ nahoře v tabulce.

Dnešní cvičení bude úvod do grafových algoritmů. Nejprve nás ale čeká diskuze nad úlohami z posledního cvičení. Poté probereme základní pojmy z teorie grafů a popovídáme si o základních úlohách, které lze řešit jedním z nejverzatilnějších algoritmů (z říše grafových algoritmů), a to o prohledávání do hloubky. Ale i mnohem více…

Stěžejní algoritmy a datové struktury:

• Prohledávání do hloubky
• Prohledávání do šířky
• Union-Find

Motivační úlohy s řešeními (hlavně na příští seminář):

• Spreadsheet - kód: spreadsheet.java, vstupy: spreadsheet.txt
• Hádanka s kozou, vlkem a zelím - kód: riddle.java
• Hádanka s tunelem - kód: riddle2.java
• Maze Runner - kód: mazerunner.java, mazerunner2.java (alternativní), vstupy: mazerunner1.txt, mazerunner2.txt, mazerunner3.txt, mazerunner4.txt, mazerunner5.txt
• Heretic - kód: heretic.java, vstupy: heretic1.txt,heretic2.txt, heretic3.txt, heretic4.txt
• Útěk z hořícího lesa - kód: escape.java, vstupy: escape1.txt, escape2.txt, escape3.txt

V dnešním semináři budeme pokračovat v povídání o grafových algoritmech. Tentokrát probereme řadu algoritmů pro hledání nejkratší cesty v grafu a určení jeho minimální kostry.

• Dijkstrův algoritmus (nejkratší cesta) Easy Dijkstra Problem (Řešení v C++)
• Dijkstrův algoritmus (téměř nejkratší cesta) Almost Shortest Path (Řešení v C++)
• Dijkstrův algoritmus (minimální kostra) Dark roads (UVa) (Řešení v C++)
• Bellman-Fordův algoritmus Wormholes (Řešení v C++)
• Floyd-Warshallův algoritmus Arbitrage (SPOJ) (Řešení v C++)

Učební materiály a pár jednodušších úloh na doma.

• Ukázky klasických úloh TT&MB
• Voda v rourách
• Základní všechno možné průchodem DAG
• nejdelší rostoucí podposloupnost v čase O(N log N)
• 900 - Brick Wall Patterns
• 10334 - Ray Through Glasses
• MMAXPER, Rectangles Perimeter - max upper envelope length

Ukázka kódu -- manipulace s DAG

Cycle finding
Algorithm:
Floyd's Tortoise and Hare
Problems:
350 - Pseudo-Random Numbers
10591 - Happy Number
11549 - Calculator Conundrum

String Matching
11019 - Matrix Matcher
1328 - Period
1519 - Dictionary Size
10887 - Concatenation of Languages
1314 - Hidden Password

Automata

Textbook Melichar et al.

Text Search with Automata

Example calendar automaton

Odkazy na materiály:

• Habalova kombinatorická skripta!
  • 369 - Combinations
  • 10329 - Combinatorial Expression
  • 10375 - Choose and divide
• 10213 - How Many Pieces of Land ? Eulerova formule V+F = E+2
• Prvočísla, Eratosthenovo síto a kód
  • 11408 - Count DePrimes
  • 11347 - Multifactorials
• Výpočet multiplikativní inverse
  • Rozšířený Euclidův algoritmus
  • ... A ještě přehledněji!!
  • Malá Fermatova věta
• Eulerova věta a funkce (1, 2, 3)
• Čínská věta o zbytcích
• Čísla všeho druhu:
  • Kombinační
  • Fibonacciho
  • Catalanova
    • 10303 - How Many Trees?
  • Motzkinova
  • Úloha spojující poslední dva jmenované druhy: Game Count
• Řešení lineárních rekurentních rovnic s konstantními koeficienty
  • Úloha: Chefs new Pet

Studijni materialy:

• Range Minimum Query, Lowest Common Ancestor, Heavy-Light Decomposition
• Range Minimum Query
• Static Interval Tree
• Binary Index Tree

Nekolik uloh na doma:

• COT - Count on a tree
• GRASSPLA - Grass Planting
• YODANESS - Yodaness Level
• DCEPC11I - Impossible Boss
• RACETIME - Race Against Time
• BRCKTS - Brackets
• COURAGE - Living with Courage

viz. ACM Maraton 2016

Pár kousků pro pokročilé posluchače:

• Play with a Tree (SPOJ)
• Black and White Nim (SPOJ)
• Racing Car Trail (CERC Regional 2011) - trail.in.gz (input data) - trail.out.gz (correct output)
• Malvika and Animesh play Red-Blue cards Game (Codechef
• To add or to multiply game (Codechef)