**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. ===== Rozvrh ===== ^ 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í | [[http://a2oj.com/standings?ID=24209|Výsledky na A2OJ]] | | **2.** | **3.3** (2) | Průchody grafem, | | | **3.** | **10.3.** (4) |** Minisoutěž I** | [[http://a2oj.com/standings?ID=24481|Výsledky na A2OJ]] | | **4.** | **17.3.** (2) | DP I | | | **5.** | **24.3.** (4) | **Minisoutěž II** | [[http://a2oj.com/standings?ID=24775|Výsledky na A2OJ]] | | **6.** | **31.3.** (2) | Pokračování DP plus grafy | | | **7.** | **7.4.** (4) | **Minisoutěž III** | [[http://a2oj.com/standings?ID=25018 |Výsledky na A2OJ]] | | **8.** | **14.4.** (2) | Aritmetika a kombinatorika, teorie čísel | | | **9.** | **21.4** (4) |** Minisoutěž IV** | [[http://a2oj.com/standings?ID=25239|Výsledky na A2OJ]] | | **10.** | **28.4.** (5) | **Minisoutěž V** | **Trénink s FIT a MFF \\ Nácvik soutěže v týmech** \\ [[https://a2oj.com/standings?ID=25341|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** | [[http://a2oj.com/standings?ID=25686|Výsledky na A2OJ]] | | **14.** | **26.5.** (2) | Opakování a doplnění restů | | | **CELKEM** | LS 2015 | **Průběžný stav** | [[https://docs.google.com/spreadsheets/d/1sLJ17qfRHSJkGQA_U6nndN9GDmOvjuvjhXkUuBOHizI/edit#gid=0|Tabulka]] | ---- ===== Seminář 1. ===== ==== Motivační úloha ==== Pěkná motivační úloha na úvod: {{:courses:a4b36acm:2014_zs:acm_presentation_zs2014_01.pdf|Kings on the Chessboard}}, řešení: {{:courses:a4b36acm:2014_zs:kings_bruteforce.txt|kings_bruteforce.c}}, {{:courses:a4b36acm:2014_zs:kings_dp.txt|kings_dp.c}}, {{:courses:a4b36acm:2014_zs:kings_graphs.txt|kings_graphs.c}}\\ ==== Ahmed Aly Online Judge ==== 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: [[http://a2oj.com/signup|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: [[http://www.spoj.com/register/|Sphere Online Judge]], [[https://uva.onlinejudge.org/index.php?option=com_comprofiler&task=registers|UVa Online Judge]] a [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_comprofiler&task=registers|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: === Sphere Online Judge (SPOJ) === - Neuvěřitelné, ale login je vaše ID. === UVA Online Judge === - Odevzdejte libovolnou úlohu. - Přejděte na následující [[http://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=19|stránku]]. - Sledujte odkaz u své odevzdané úlohy ve sloupci "user". - Konec URL výsledné stránky obsahuje vaše UVA ID (URL: ...&userid=[UVA_ID]) === ACM-ICPC Online Judge === * Postup je stejný jako u UVA Online Judge. ==== Test odevzdávacího systému ==== Po vytvoření účtů se můžete registrovat do soutěže na A2 Online Judge, klikněte [[http://a2oj.com/register?ID=24209|zde]]. ==== Výběr úloh pro otestování odevzdávacího systému: ==== - Pro bojácné: * [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=757|Crazy tea party]] (Hint: Tužka a Papír :)) - {{:courses:a4b36acm:2014_zs:2756.txt|Ukázkové řešení v jazyce C}} - Pro mírně statečnější: * [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=67&page=show_problem&problem=159|Factorial]] (Hint: Prvočíselný rozklad. Co tvoří 0 v zápisu čísla?) - {{:courses:a4b36acm:2014_zs:2158.txt|Ukázkové řešení v jazyce C}} * [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=196&page=show_problem&problem=1079|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ů.) - {{:courses:a4b36acm:2014_zs:3078.txt|Ukázkové řešení v jazyce C}} - Pro drakobijce: * [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=630&page=show_problem&problem=4717|Little Tiger vs. Deep Monkey]] (Hint: Malý rozsah součtů skóre! [[http://en.wikipedia.org/wiki/Subset_sum_problem|Subset Sum Problem]]. Pozor na rozsah hodnot standardních datových typů!) - {{:courses:a4b36acm:2014_zs:6705.txt|Ukázkové řešení v jazyce C}} ===== Seminář 2. ===== 1. Používejte k ladění **[[https://www.udebug.com/|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: {{:courses:a4b36acm:2015_zs:spreadsheet.java|spreadsheet.java}}, vstupy: {{:courses:a4b36acm:2015_zs:spreadsheet.txt|spreadsheet.txt}} * **Hádanka s kozou, vlkem a zelím** - kód: {{:courses:a4b36acm:2015_zs:riddle.java|riddle.java}} * **Hádanka s tunelem** - kód: {{:courses:a4b36acm:2015_zs:riddle2.java|riddle2.java}} * **Maze Runner** - kód: {{:courses:a4b36acm:2015_zs:mazerunner.java|mazerunner.java}}, {{:courses:a4b36acm:2015_zs:mazerunner2.java|mazerunner2.java}} (alternativní), vstupy: {{:courses:a4b36acm:2015_zs:mazerunner1.txt|mazerunner1.txt}}, {{:courses:a4b36acm:2015_zs:mazerunner2.txt|mazerunner2.txt}}, {{:courses:a4b36acm:2015_zs:mazerunner3.txt|mazerunner3.txt}}, {{:courses:a4b36acm:2015_zs:mazerunner4.txt|mazerunner4.txt}}, {{:courses:a4b36acm:2015_zs:mazerunner5.txt|mazerunner5.txt}} * **Heretic** - kód: {{:courses:a4b36acm:2015_zs:heretic.java|heretic.java}}, vstupy: {{:courses:a4b36acm:2015_zs:heretic1.txt|heretic1.txt}},{{:courses:a4b36acm:2015_zs:heretic2.txt|heretic2.txt}}, {{:courses:a4b36acm:2015_zs:heretic3.txt|heretic3.txt}}, {{:courses:a4b36acm:2015_zs:heretic4.txt|heretic4.txt}} * **Útěk z hořícího lesa** - kód: {{:courses:a4b36acm:2015_zs:escape.java|escape.java}}, vstupy: {{:courses:a4b36acm:2015_zs:escape1.txt|escape1.txt}}, {{:courses:a4b36acm:2015_zs:escape2.txt|escape2.txt}}, {{:courses:a4b36acm:2015_zs:escape3.txt|escape3.txt}} Úlohy pro zamyšlení: * [[https://uva.onlinejudge.org/external/106/p10672.pdf|Marbles on a tree]] * [[https://uva.onlinejudge.org/external/116/p11686.pdf|Pick up sticks]] * [[https://uva.onlinejudge.org/external/5/572.html|Oil Deposits]] * [[https://uva.onlinejudge.org/external/5/558.html|Wormholes]] * [[https://uva.onlinejudge.org/external/1/125.html|Numbering Paths]] * [[http://www.spoj.com/problems/SAMER08A/|Almost Shortest Path]] ===== Seminář 3. ===== Minisoutěž v programování - téma: Grafové algoritmy. Registrace do soutěže - [[http://a2oj.com/register?ID=24481|ACM_S16E02]] ([[http://a2oj.com/standings?ID=24481|Standings]]) [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=116&page=show_problem&problem=599|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?) [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=116&page=show_problem&problem=1926|10985 - Rings'n'Ropes]] - All-Pairs Shortest Path (How is the task related to the graph diameter?) [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=116&page=show_problem&problem=1549|10608 - Friends]] Largest Connected Component (Union-Find) (Can be solved without building the graph in the memory.) [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=1246|10305 - Ordering Tasks]] - Topological Sort (DFS) [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=116&page=show_problem&problem=508|567 - Risk]] - Source-Target Shortest Path (BFS) [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=1537|10596 - Morning Walk]] - Graph Connectivity and Degree Check (How is the problem related to the Euler trail problem?) [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=475 | 534 - Frogger]] - Shortest Path (tricky) (Can you modify the Dijkstra algorithm somehow?) [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=473 | 532 - Dungeon Master]] - Shortest Path (BFS) [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1400 | 10459 - The Tree Root]] - Tree Center and Diameter (Think of a solution in linear time wrt the number of nodes.) [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1642 | 10701 - Pre, in and post]] - (Pre/In)-Order to Post-Order Conversion ===== Seminář 4. DP ===== **Zdroje úloh** http://a2oj.com/Category.jsp?ID=33, http://uvatoolkit.com/problemssolve.php **Výklady s příklady** DP v kuchařce [PK]: [[https://ksp.mff.cuni.cz/tasks/24/cook2.html| html výklad I ]], [[http://ksp.mff.cuni.cz/tasks/17/cook5.html| html výklad II]], [[http://ksp.mff.cuni.cz/study/cooks/cookbook-chapters/09-dynamicke-programovani.pdf| přibližně shrnuto v pdf.]] [[https://cw.fel.cvut.cz/wiki/_media/courses/a4b36acm/2013_ls/dp.pdf|Ukázky klasických úloh TT&MB]] {{:courses:a4b36acm:internal:alg10_2015c.ppt| LCS }}, {{:courses:a4b36acm:internal:alg10_2015c.pdf| LCS pdf}} **Některé ukázky s kódem (v support)** {{:courses:a4b36acm:ukazkaprez.pptx| roury ppt}}, {{:courses:a4b36acm:ukazkaprez.pdf| 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= ===== Seminář 5 ===== Minisoutěž v programování - téma: Dynamické programování ("lehčí" varianty úloh). Registrace do soutěže - [[http://a2oj.com/register?ID=24775|ACM_S16E03]] ([[http://a2oj.com/standings?ID=24775|Standings]]) Úlohy * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2467 | 1472 - Beautiful Numbers]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2415 | 11420 - Chest of Drawers]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=615 | 674 - Coin Change]] * [[http://www.spoj.com/problems/CRSCNTRY/ | CRSCNTRY - Cross-country]] * [[http://www.spoj.com/problems/COINS/ | COINS - Bytelandian gold coins]] * [[http://www.spoj.com/problems/DCEPC501/ | DCEPC501 - Save Thy Toys]] * [[http://www.spoj.com/problems/BORW/ | BORW - Black or White]] * [[http://www.spoj.com/problems/ACODE/ | ACODE - Alphacode]] * [[http://www.spoj.com/problems/BYTESM2/ | BYTESM2 - Philosophers Stone]] * [[http://www.spoj.com/problems/EDIST/ | EDIST - Edit distance]] * [[http://www.spoj.com/problems/M00PAIR/ | M00PAIR - 0 0 Pairs]] ===== Seminář 6 DP a DAG ===== [[https://cw.fel.cvut.cz/wiki/courses/a4b36acm/links#dynamicke_programovani| odkazy ]] {{:courses:a4b36acm:2016_ls:dag.pptx| Ukázky DAG (Directed Acyclic Graph}} [[https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms|LIS (Longest Increasing Subsequence)]] Lámání klacku [[http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/| tady]] [[http://www.radford.edu/~nokie/classes/360/dp-rod-cutting.html| a tady]] {{:courses:a4b36acm:2016_ls:mtice.ppt| Násobení matic}} ===== Seminář 7 ===== Minisoutěž v programování - téma: Dynamické programování. Registrace do soutěže - [[http://a2oj.com/register?ID=25018|ACM_S16E03]] ([[http://a2oj.com/standings?ID=25018|Standings]]) ===== Seminář 8 ===== Dnešní téma: Aritmetika, Kombinatorika a Teorie Čísel Odkazy na materiály: * [[https://math.feld.cvut.cz/habala/teaching/dma/dmknih11.pdf|Habalova kombinatorická skripta]]! * {{:courses:a4b36acm:2016_ls:primes.pptx| Prvočísla, Eratosthenovo síto a kód}} * [[http://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/|Výpočet multiplikativní inverse]] * [[http://www.geeksforgeeks.org/basic-and-extended-euclidean-algorithms/|Rozšířený Euclidův algoritmus]] * [[https://en.wikipedia.org/wiki/Fermat%27s_little_theorem|Malá Fermatova věta]] * Eulerova věta a funkce ([[https://en.wikipedia.org/wiki/Euler%27s_theorem|1]], [[https://en.wikipedia.org/wiki/Euler%27s_totient_function|2]], [[http://www.geeksforgeeks.org/eulers-totient-function/|3]]) * [[http://www.geeksforgeeks.org/chinese-remainder-theorem-set-2-implementation/|Čínská věta o zbytcích]] * Čísla všeho druhu: * [[https://en.wikipedia.org/wiki/Combination|Kombinační]] * [[https://en.wikipedia.org/wiki/Fibonacci_number|Fibonacciho]] * [[https://en.wikipedia.org/wiki/Catalan_number|Catalanova]] * [[https://en.wikipedia.org/wiki/Motzkin_number|Motzkinova]] * Úloha spojující poslední dva jmenované druhy: [[https://www.codechef.com/problems/MAXGAME|Game Count]] * [[http://fusharblog.com/solving-linear-recurrence-for-programming-contest/|Řešení lineárních rekurentních rovnic s konstantními koeficienty]] * Úloha: [[https://www.codechef.com/problems/HAREJUMP|Chefs new Pet]] ===== Seminář 9 ===== Minisoutěž v programování - téma: Aritmetika, Kombinatorika a Teorie čísel. Registrace do soutěže - [[http://a2oj.com/register?ID=25239|ACM_S16E05]] ([[http://a2oj.com/standings?ID=25239|Standings]]) ===== Seminář 10 ===== 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 ===== Seminář 11 ===== Diskuse k tréninku SWERC 2014: * [[http://swerc.up.pt/2014/reports/problemset.pdf|Problem Set]] * [[http://swerc.up.pt/2014/reports/discussion.pdf|Solutions Discussion]] Odkazy k řešení úloh: * Golf - FFT ([[http://mj.ucw.cz/vyuka/1112/ads2/7-fft.pdf|výtah z přednášky ADS II. na MFF]], [[http://www.cs.cmu.edu/afs/cs/academic/class/15451-s10/www/lectures/lect0423.txt|výtah z přednášky z Algoritmizace na CMU]]) * Book Club - Perfektní párování v bipartitním grafu ([[https://drive.google.com/open?id=1Z2K-0YM9vPn6j8LBvyUp_RK_KZER5pBWbX94vGKWHh4|Maximum Cardinality Matching]]) Algoritmy pro Maximální Párování v Bipartitních Grafech: * [[http://www.geeksforgeeks.org/maximum-bipartite-matching/|Ford-Fulkerson]] * [[http://www.geeksforgeeks.org/hopcroft-karp-algorithm-for-maximum-matching-set-1-introduction/|Hopcroft-Karp]] ===== Seminář 12 ===== **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** {{:courses:a4b36acm:2016_ls:sweepline.pptx| 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/ ===== Seminář 13 ===== Minisoutěž v programování - téma: Výpočetní Geometrie a Párování v Grafech. Registrace do soutěže - [[http://a2oj.com/register?ID=25686|ACM_S16E06]] ([[http://a2oj.com/standings?ID=25686|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 ===== Seminář 14 ===== 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 [[https://docs.google.com/presentation/d/1352wnxlrrj9Z_CbBiDJvYYzlzFeewXV2x1jDkFee3aQ/edit?usp=sharing|Statický intervalový strom]]