Pěkná motivační úloha na úvod: Kings on the Chessboard, řešení: kings_bruteforce.c, kings_dp.c, kings_graphs.c

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. Odevzdejte libovolnou úlohu.
2. Přejděte na následující stránku.
3. Sledujte odkaz u své odevzdané úlohy ve sloupci “user”.
4. Konec URL výsledné stránky obsahuje vaše UVA ID (URL: …&userid=[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.

1. Pro bojácné:
   • Crazy tea party (Hint: Tužka a Papír :)) - Ukázkové řešení v jazyce C
2. Pro mírně statečnější:
   • Factorial (Hint: Prvočíselný rozklad. Co tvoří 0 v zápisu čísla?) - Ukázkové řešení v jazyce C
   • Alphacode (Hint: Fibonacci?! Jednoduché DP: co takhle si pamatovat počet dekódovaní pro každý prefix zprávy a využít je pro vypočítání delších prefixů.) - Ukázkové řešení v jazyce C
3. Pro drakobijce:
   • Little Tiger vs. Deep Monkey (Hint: Malý rozsah součtů skóre! Subset Sum Problem. Pozor na rozsah hodnot standardních datových typů!) - Ukázkové řešení v jazyce C

1. Používejte k ladění uDebug. Odkaz nahoře napravo v úloze UVA nebop ICPC Archive.

2. Mějte soupis vzorečků.

Dnes nás čeká povídání o grafových algoritmech.

• 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

Úlohy pro zamyšlení:

• Marbles on a tree
• Pick up sticks
• Oil Deposits
• Wormholes
• Numbering Paths
• Almost Shortest Path

Minisoutěž v programování - téma: Grafové algoritmy. Registrace do soutěže - ACM_S16E02 (Standings)

658 - It's not a Bug, it's a Feature! - Source-Target Shortest Path (Consider input sizes! - what is a node and what is an edge?)

10985 - Rings'n'Ropes - All-Pairs Shortest Path (How is the task related to the graph diameter?)

10608 - Friends Largest Connected Component (Union-Find) (Can be solved without building the graph in the memory.)

10305 - Ordering Tasks - Topological Sort (DFS)

567 - Risk - Source-Target Shortest Path (BFS)

10596 - Morning Walk - Graph Connectivity and Degree Check (How is the problem related to the Euler trail problem?)

534 - Frogger - Shortest Path (tricky) (Can you modify the Dijkstra algorithm somehow?)

532 - Dungeon Master - Shortest Path (BFS)

10459 - The Tree Root - Tree Center and Diameter (Think of a solution in linear time wrt the number of nodes.)

10701 - Pre, in and post - (Pre/In)-Order to Post-Order Conversion

Zdroje úloh

http://a2oj.com/Category.jsp?ID=33, http://uvatoolkit.com/problemssolve.php

Výklady s příklady

DP v kuchařce [PK]: html výklad I , html výklad II, přibližně shrnuto v pdf.

Ukázky klasických úloh TT&MB

LCS , LCS pdf

Některé ukázky s kódem (v support)

roury ppt, roury pdf

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=841

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1300

http://www.spoj.com/problems/BYTESH1/

http://www.spoj.com/problems/MMAXPER/

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=944

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=52

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=142&page=show_problem&problem=

Minisoutěž v programování - téma: Dynamické programování (“lehčí” varianty úloh). Registrace do soutěže - ACM_S16E03 (Standings)

Úlohy

• 1472 - Beautiful Numbers
• 11420 - Chest of Drawers
• 674 - Coin Change
• CRSCNTRY - Cross-country
• COINS - Bytelandian gold coins
• DCEPC501 - Save Thy Toys
• BORW - Black or White
• ACODE - Alphacode
• BYTESM2 - Philosophers Stone
• EDIST - Edit distance
• M00PAIR - 0 0 Pairs

odkazy

Ukázky DAG (Directed Acyclic Graph

LIS (Longest Increasing Subsequence)

Lámání klacku tady a tady

Násobení matic

Minisoutěž v programování - téma: Dynamické programování. Registrace do soutěže - ACM_S16E03 (Standings)

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

Odkazy na materiály:

• Habalova kombinatorická skripta!
• 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

Minisoutěž v programování - téma: Aritmetika, Kombinatorika a Teorie čísel. Registrace do soutěže - ACM_S16E05 (Standings)

Trenink s MFF a FIT: SWERC 2014:

http://swerc.up.pt/2014/

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=657

Diskuse k tréninku SWERC 2014:

• Problem Set
• Solutions Discussion

Odkazy k řešení úloh:

• Golf - FFT (výtah z přednášky ADS II. na MFF, výtah z přednášky z Algoritmizace na CMU)
• Book Club - Perfektní párování v bipartitním grafu (Maximum Cardinality Matching)

Algoritmy pro Maximální Párování v Bipartitních Grafech:

• Ford-Fulkerson
• Hopcroft-Karp

Geometrie

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

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

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/

Minisoutěž v programování - téma: Výpočetní Geometrie a Párování v Grafech. Registrace do soutěže - ACM_S16E06 (Standings)

Úlohy z minisoutěže a k tréninku:

105 - The Skyline Problem
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=41

270 - Lining Up
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=206

313 - Intervals
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=249

737 - Gleaming the Cubes
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=9&page=show_problem&problem=678

833 - Water Falls
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=774

920 - Sunny Mountains
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=861

10088 - Trees on My Island
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1029

11030 - Predator II
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=22&page=show_problem&problem=1971

11579 - Triangle Trouble
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2626

11626 - Convex Hull
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2673

11704 - Caper pizza
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=117&page=show_problem&problem=2751

11648 - Divide The Land
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2695

Diskuze k úloze, analytická geometrie
313 - Intervals
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=249
https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line

“Univerzální” řešitel
11648 - Divide The Land
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2695\ https://en.wikipedia.org/wiki/Trapezoid
https://en.wikipedia.org/wiki/Bisection_method

Jednoduché uvažování!
737 - Gleaming the Cubes
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=9&page=show_problem&problem=678

Statický intervalový strom