…

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.

• Odevzdejte libovolnou úlohu (klidně prázný soubor).
• Přejděte na stránku Live Archive: Posledních 50 Odevzdání
• Najděte řádku přislušící vaší odevzdané úloze a klikněte na své uživatelské jméno.
• V parametrech URL naleznete své userid.

Po vytvoření účtů se můžete registrovat do soutěže na A2 Online Judge, klikněte zde.

Návodník na řešení

malá kategorizace grafových úloh

Dot product - Skalární součin

V první části semináře si zopakujeme standardní grafové úlohy řešitelné pomocí algoritmu prohledávání do hloubky, a to zejména ulohy:

• Detekce cyklu v grafu
• Nalezení topologického uspořádání vrcholů v grafu
• Identifikace mostů. (*_*_*)
• Identifikace artikulací (*_*_*)
• Detekce bloků, tj. 2-souvislých komponent
• Nalezení silně souvislých komponent

Dále:

Tabulky grafových úloh a složitostí

Poznámky k minimálním kostrám

Floyd-Warshall algorithm example

Bellman-Ford algorithm demo

nejkratší a nejdelší cesty -- celkový přehled

nejkratší a nejdelší cesty v DAG

Bellman-Ford

Floyd-Warshall

( topsort by DFS)

další vizualizace

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

Typické a klasické úlohy vedoucí na 2D tabulku DP:

• Základní úloha “lámání klacku” : 10003 - Cutting Sticks
• Analogickou strukturu má optimální pořadí násobení matic: https://www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/
• Klasické plnění batohu (Knapsack problem)
  • https://www.geeksforgeeks.org/knapsack-problem/
  • příklad z ALG
• Nejdelší společná podposloupnost (LCS - Longest Common Subsequence )
  • https://www.geeksforgeeks.org/longest-common-subsequence/
  • příklad z ALG

• Habalova kombinatorická skripta!
• Prvočísla, Eratosthenovo síto a kód
• Čísla různých druhu:
  • Kombinační
  • Fibonacciho
  • Catalanova , na Mathworld
  • OEIS Vynikající všeobecná referenční příručka The On-Line Encyclopedia of Integer Sequences
• Rychlé mocnění
  • https://www.geeksforgeeks.org/exponential-squaring-fast-modulo-multiplication/
  • https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/

Ilustrační úlohy

• 993 - Product of digits
• 10375 - Choose and divide
• 10235 - Simply Emirp
• 11287 - Pseudoprime Numbers

Některé základní výpočty

Počítání průsečíků

Reminder: Trigonometric identities

Pick's_theorem http://jwilson.coe.uga.edu/emat6680fa05/schultz/6690/pick/pick_main.htm

Všeobecný přehled na MFF (Programátorské kuchařky) http://ksp.mff.cuni.cz/tasks/24/cook5.html

Seznamy geometrických kreslítek https://en.wikipedia.org/wiki/List_of_interactive_geometry_software#2D_programs, http://mathforum.org/geometry/geometry.software.html

Kreslítko GeoGebra online http://www.geogebra.org/

Polygon area example: https://www.mathsisfun.com/geometry/area-irregular-polygons.html, code: http://www.codeproject.com/Articles/13467/A-JavaScript-Implementation-of-the-Surveyor-s-Form

Sweep line example Touching rectangles

Graham Scan demo: http://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/ah/GrahamScan.html
code: http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
Stanford examples: http://web.stanford.edu/class/cs97si/

Ideas_in_Geometry https://en.wikiversity.org/wiki/Ideas_in_Geometry/Area

Cyclic quadrilateral, https://en.wikipedia.org/wiki/Cyclic_quadrilateral

Sweep line rotates:, http://www.spoj.com/problems/CERC07C/ (*_*_*) komentář