Místo a čas konání
KN:E-311, čtvrtek od 16:15, střídavě 2 a 4 hodiny týdně, viz rozpis níže.
Seminář | Datum (hodiny) | Náplň | Úlohy/odkazy viz také pod tabulkou |
---|---|---|---|
1. | 25.2. (4) | Servery, konta, ukázkové úlohy a témata, cvičná odevzdání | Výsledky na A2OJ |
2. | 3.3 (2) | Průchody grafem, | |
3. | 10.3. (4) | Minisoutěž I | Výsledky na A2OJ |
4. | 17.3. (2) | DP I | |
5. | 24.3. (4) | Minisoutěž II | Výsledky na A2OJ |
6. | 31.3. (2) | Pokračování DP plus grafy | |
7. | 7.4. (4) | Minisoutěž III | Výsledky na A2OJ |
8. | 14.4. (2) | Aritmetika a kombinatorika, teorie čísel | |
9. | 21.4 (4) | Minisoutěž IV | Výsledky na A2OJ |
10. | 28.4. (5) | Minisoutěž V | Trénink s FIT a MFF Nácvik soutěže v týmech Výsledky na A2OJ |
11. | 5.5. (2) | Komentáře k úlohám z tréninku, singulární úlohy, doplnění starších témat | |
12. | 12.5 (2) | Výpočetní geometrie, mřížky | |
13. | 19.5. (4) | Minisoutěž VI | Výsledky na A2OJ |
14. | 26.5. (2) | Opakování a doplnění restů | |
CELKEM | LS 2015 | Průběžný stav | Tabulka |
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:
Po vytvoření účtů se můžete registrovat do soutěže na A2 Online Judge, klikněte zde.
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.
Úlohy pro zamyšlení:
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.
Některé ukázky s kódem (v support)
http://www.spoj.com/problems/BYTESH1/
Minisoutěž v programování - téma: Dynamické programování (“lehčí” varianty úloh). Registrace do soutěže - ACM_S16E03 (Standings)
Úlohy
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:
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:
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=657
Diskuse k tréninku SWERC 2014:
Odkazy k řešení úloh:
Algoritmy pro Maximální Párování v Bipartitních Grafech:
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