Warning
This page is located in archive.

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

courses:a4b36acm2:2016_ls:seminare [2018/10/03 03:51] (current)
Line 1: Line 1:
 +**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]]
 +
  
courses/a4b36acm2/2016_ls/seminare.txt · Last modified: 2018/10/03 03:51 (external edit)