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

Návodník na řešení

malá kategorizace grafových úloh

Další úlohy pro zájemce nebo domácí studium:

• 459 - Graph Connectivity
• 11635 - Hotel booking
• Following Orders
• CATM - The Cats and the Mouse
• 11686 - Pick up sticks
• TFRIENDS - True Friends
• 104 - Arbitrage
• 821 - Page Hopping
• CERC07K - Key Task
• 11624 - Fire!
• Spreadsheet
• 558 - Wormholes

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 zde.

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

• Nalezení (libovolného) topologického uspořádání vrcholů v grafu.
• Nalezení silně souvislých komponent.
• Identifikování mostů. (*_*_*)
• Identifikování artikulací. (*_*_*)

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

COntest na A2OJ: https://a2oj.com/contest?ID=28483

Seznam úloh:

• 10369 - Arctic Network
• 11631 - Dark roads
• 572 - Oil Deposits
• 929 - Number Maze
• 423 - MPI Maelstrom
• 280 - Vertex
• 200 - Rare Order
• 11504 - Dominos
• 10410 - Tree Reconstruction
• 10926 - How Many Dependencies?

Ilustrační jednodušší 1D varianty DP úloh

• 900 - Brick Wall Patterns
• 10334 - Ray Through Glasses
• Voda v rourách
• 10862 - Connect the Cable Wires, čím se liší od Vody v rourách?
• FARIDA, Princess Farida - max sum with limitations
• MMAXPER, Rectangles Perimeter - max upper envelope length
• Základní všechno možné průchodem DAG
• nejdelší rostoucí podposloupnost v čase O(N log N)

Ukázka kódu -- manipulace s DAG

Základní úloha “lámání klacku” 10003 - Cutting Sticks

DP lze řešit pomocí Excelu 10081 - Tight Words

Dnešní téma: Aritmetika, Kombinatorika a Teorie Čísel

Odkazy na materiály:

• Habalova kombinatorická skripta!
• 10213 - How Many Pieces of Land ? Eulerova formule V+F = E+2 (*_*_*)
• Prvočísla, Eratosthenovo síto a kód
• Výpočet multiplikativní inverse
  • Rozšířený Euclidův algoritmus
  • 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
  • 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

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ář

viz. ACM Maraton 2016