==== Program semináře ====

^ Seminář  ^ Datum \\ (hodiny)  ^  Náplň         ^  Úlohy/odkazy    ^
|  **1.**   |  **25.9.** (2) | Konto, odevzdání cvičné úlohy |  | 
|  **2.**   |  **2.10.** (4) | **Minisoutěž **  | [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=78| Regionals 2000: North America - Mid-Central USA]]\\ [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=262|Regionals 2006 :: North America - Greater NY]] \\ Úlohy pro zkušenější jsou pod tabulkou |
|  **3.**   |  **9.10.** (2) | **Prezentují**   | **Úloha**    | 
|           |                | 1. Vyskočil, Marek:  | [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=262&page=show_problem&problem=1419|3418 - Shuffle'm Up]]  | 
|           |                | 2. Hubáček, Pichl:  | [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=262&page=show_problem&problem=1499|3498 - Push Button Lock]]  | 
|           |                | 3. Vavřinec, Šerých: | [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1572|3571 - Visible Lattice Points]] |  
|           |                | **Výklad:**  Řešitelova infrastruktura, znalostní cihly.  | [[http://web.stanford.edu/class/cs97si/|CS 97SI: Introduction to Competitive Programming Contests]]  |  
|  **4.**   |  **16.10.** (4) | **Minisoutěž **  | [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=264| Regionals 2006: North America - Mid-Central USA]]\\ [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=311|Regionals 2008: Asia - Beijing]]\\ |
|  **5.**   |   **23.10.** (2) | **Prezentují**   | **Úloha**     |
|           |                | 1. Hořeňovský   | [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=264&page=show_problem&problem=1599|3598 - Frugal Search]]  | 
|           |                | 2. Horák, Váňa  | [[http://en.wikipedia.org/wiki/Skip_list#References|Skip List - Výklad]] | 
|           |                | 3. Muzika, Briedoň  | ...   | 
|           |                | **Výklad:** DP, elementy|  |  
|  **6.**   |  **30.10.** (4) | **Minisoutěž **  | Úlohy pro tuto minisoutěž jsou pod tabulkou. |
|  **7.**   |  **6.11.** (2) | **Prezentují**   | **Úloha**     | 
|           |                | 1. ...  |  | 
|           |                | 2. ...  |  | 
|           |                | 3. ...  |  | 
|           |                | **Výklad:** DP, pokračování|  |  
|  **8.**   |  **13.11.** (4) | **Minisoutěž **  | [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=337|Regionals 2008 - North America - Pacific Northwest]]\\ [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=301|Regionals 2007 - North America - Pacific Northwest]]|
|  **9.**  |  **20.11** (2)  | **Prezentují**   | **Úloha**     |
|           |                | 1. Muzika, Briedoň   | [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=301&page=show_problem&problem=2069|4068 - Rubik's Cube(R)]]   | 
|           |                | 2.  MB  | [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=301&page=show_problem&problem=1996|3995 - Pebbles]]    |
|           |                | 3. ...  |   |
|           |                | **Výklad:** |  |  
|  **10.**  |  **27.11.** (4) | **Minisoutěž **  | Úlohy pro tuto minisoutěž jsou pod hned tabulkou. |  
|  **11.**  |  **4.12** (2)  | **Prezentují**   | **Úloha**     |
|           |                | 1. ...  |   | 
|           |                | 2. ...  |    |
|           |                | 3. ...  |   |
|           |                | **Výklad:**  Geometrické nezbytnosti a ukázky |  |  
|  **12.**  |  **11.12** (4)  | **Minisoutěž **   | Úlohy pro tuto minisoutěž jsou pod hned tabulkou. |
|  **13.**  |  **18.11.** (2) | **Prezentují**   | **Úloha**    | 
|           |                | 1. ...  |   | 
|           |                | 2. ...  |    |
|           |                | 3. ...  |   |
|           |                | **Výklad:** Něco z her |  |  
|  **14.**   |  **nebude**  |  ----    |  ---  | 
|   **CELKEM**     |  ZS 2014       | **Průběžný stav** |  [[https://docs.google.com/spreadsheets/d/12UDCzmd-ynutx6JIz0MKkgvMelVemw6t4-kFD3rfAVE/edit#gid=809188264|Tabulka]]  |

===== Geometrické úlohy na minisoutěž 11.12.2014 =====
Zadání jsou řazena libovolně a jsou nekomentována, zadání je většinou samo krátké a přehledné.\\     
  * [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=154|218 - Moth Eradication]] .
  * [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1019|10078 - The Art Gallery]] .
  * [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1619|10678 - The Grazing Cow]] .
  * [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1632|10691 - Subway]] .
  * [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=222&page=show_problem&problem=2320|11345 - Rectangles]] .
  * [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2340|11355 - Cool Points]] .
  * [[http://www.spoj.com/problems/LITEPIPE/|102. GX Light Pipeline Inc]] .
  * [[http://www.spoj.com/problems/FSHEEP/|149. Fencing in the Sheep]] .
  * [[http://www.spoj.com/problems/FLBRKLIN/|187. Flat broken lines]] .
  * [[http://www.spoj.com/problems/SHAMAN/|228. Shamans]] .
  * [[http://www.spoj.com/problems/CERC07P/|2056. Rectangular Polygon]] . 
  * [[http://www.spoj.com/problems/GEOPROB/|2901. One Geometry Problem]] .
  * [[http://www.spoj.com/problems/DOORSPEN/|3195. Doors and Penguins]] .
  * [[http://www.spoj.com/problems/MPOLY/|4061. Polygon]] . 
  * [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2677|4676 - Geometry Problem]] .  


===== Geometrické úlohy na minisoutěž 27.11.2014 =====
Zadání jsou pro jednoduchost řazena v klesajícím pořadí podle délky textu zadání. \\
  * [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=101&page=show_problem&problem=520|579 - Clock Hands]] počítání úhlů     
  * [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=212&page=show_problem&problem=120|184 - Laser Lines]] rovnice přímky
  * [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2643|11596 - Convex Orthogonal Polygon]] pravoúhlá manhattanská konvexita 
  * [[http://www.spoj.com/problems/GOALFR/|4987. Goal for Raúl]] tečna ke kružnici
  * [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2693|11646 - Athletics Track]] obvod obdélníka a kružnice  
  * [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2686|11639 - Guard the Land]] obsahy obdélníků  
  * [[http://www.spoj.com/problems/CATTLEB/|3678. Cattle Bruisers]]  kvadratická (ne)rovnice 
  * [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=117&page=show_problem&problem=2749|11702 - Meltdown]] vzdálenost bodu od úsečky  
  * [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=217&page=show_problem&problem=575|634 - Polygon]] bod uvnitř mnohoúhelníka, základní poučení zde: http://en.wikipedia.org/wiki/Point_in_polygon
  * [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2695|11648 - Divide The Land]] plocha čtyřúhelníka  
  * [[ http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=101&page=show_problem&problem=1328|10387 - Billiard]] odstraňte stěny tak, že vydláždíte rovinu kopiemi stolu   
  * [[http://www.spoj.com/problems/HAMSTER1/|4200. Hamster flight]] vrh šikmý, vzorečky zde: http://en.wikipedia.org/wiki/Projectile_motion
  * [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2626|11579 - Triangle Trouble]] trojúhelníková nerovnost a např. Heronův vzorec 
  * [[http://www.spoj.com/problems/KPPOLY/|1431. Projections Of A Polygon]] vzdálenosti bodů od přímky
  * [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=292|356 - Square Pegs And Round Holes]] souřadnice bodů na kružnici  
  * [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2396|11401 - Triangle Counting]] pouze trojúhelníková nerovnost 


===== Náhradní úlohy 16.10.2014 =====
[[http://www.spoj.com/|Sphere Online Judge]]
  * [[http://www.spoj.com/problems/SHPATH/|The Shortest Path (Graphs)]] - Find shortest paths between pairs of cities.\\
  * [[http://www.spoj.com/problems/SAMER08F/|Feynman (Classical)]] - Find the number of squares in a NxN grid.\\
  * [[http://www.spoj.com/problems/NGM/|A Game with Numbers (Games)]] - An easy problem from the game theory, yet it is not needed to solve this problem.\\
  * [[http://www.spoj.com/problems/PT07Z/|Longest Path in a Tree (Graphs)]] - Well-known problem of finding the diameter of a tree.\\
  * [[http://www.spoj.com/problems/PT07Y/|Is it a tree (Graphs)]] - Determine, whether the graph on the input is a tree.\\
  * [[http://www.spoj.com/problems/MARBLES/|Marbles (Combinatorics)]] - Find out the number of ways to choose marbles given the requirements.\\
  * [[http://www.spoj.com/problems/FIBOSUM/|Fibonnaci Sum (Maths)]] - Finding sum of consecutive terms in Fibonacci sequence in the given range.\\
  * [[http://www.spoj.com/problems/NY10A/|Penney Game (Classical)]] - Finding the number of occurences of particular coin toss sequences in a 40 tosses long sequence.\\
  * [[http://www.spoj.com/problems/CANTON/|Count on Cantor (Classical)]] - Telling what is the n-th rational number in the "Cantor's sequence".
  * [[http://www.spoj.com/problems/POUR1/|Pouring Water (Classical)]] - Determine the least number of steps to acquire a given amount of water using 2 vessels.
  * [[http://www.spoj.com/problems/LABYR1/|Labyrinth (Graphs)]] - The same as the problem - [[http://www.spoj.com/problems/PT07Z/|Longest Path in a Tree]] - but it is not as simple as that - you need to parse the input and build the tree.

==== Úlohy pro zkušenější 1.  ====

[[ https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=152|2151 - Telescope]]\\
[[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=220|2219 - Domino Puzzle]] \\
[[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=333|2332 - Cube]] \\
[[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=491|2490 - Clock Synchronisation]] \\
[[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=523|2522 - Chocolate]] \\
[[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=9&page=show_problem&problem=700|2699 - Diamonds]] \\

----

==== První Motivační Přednáška ====
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}}\\

==== 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}}

====== 3. Minisoutěž v Programování ======

V aktuální soutěži Vás čeká výběr úloh z dynamické programování. Úlohy tentokrát budete řešit pro odevzdávací systémy [[http://www.spoj.com/|SPOJ]] a [[http://uva.onlinejudge.org/|UVA]].

**DP on Trees:**
  * [[http://www.spoj.com/problems/THREECOL/|Three-coloring of binary trees]]
  * [[http://www.spoj.com/problems/PT07X/|Vertex Cover]]
  * [[http://www.spoj.com/problems/CNTTREE/|Trees Again]]
  * [[http://uva.onlinejudge.org/external/106/10643.html|UVA/Facing Problem With Trees]]

**DP on Sequences:**
  * [[http://www.spoj.com/problems/BORW/|Black or White]]
  * [[http://www.spoj.com/problems/MFISH/|Catch Fish]]
  * [[http://www.spoj.com/problems/AIBOHP/|Aibohphobia]]
  * [[http://www.spoj.com/problems/GNYR09F/|Adjacent Bit Counts]]
  * [[http://uva.onlinejudge.org/external/105/10534.html|UVA/Wavio Sequence]]
  * [[http://uva.onlinejudge.org/external/106/10645.html|UVA/Menu]]

**DP on Arrays:**
  * [[http://www.spoj.com/problems/JOCHEF/|Farmer Sepp]]
  * [[http://www.spoj.com/problems/FSEATS/|Finding Seats]]
  * [[http://uva.onlinejudge.org/external/105/10564.html|UVA/Paths through the Hourglass]]
  * [[http://uva.onlinejudge.org/external/106/10626.html|UVA/Buying Coke]]

**Tiling Grids DP:**
  * [[http://www.spoj.com/problems/GNY07H/|Tiling a Grid With Dominoes]]
  * [[http://www.spoj.com/problems/BYTESH1/|Filchs Dilemna]]
  * [[http://www.spoj.com/problems/M3TILE/|LATGACH3]] (POZOR! Pro N == 0 je odpověď 1 :-))
  * [[http://uva.onlinejudge.org/external/116/11611.html|UVA/Colored Tiles]]
  * [[http://uva.onlinejudge.org/external/103/10359.html|UVA/Tiling]]

----
==== Přednáškové materiály ====
**Základní a přifařené maličkosti a dovednosti** -- Je užitečné být familiární s většinou témat:\\

A. [[http://web.stanford.edu/class/cs97si/02-mathematics.pdf|mathematics]]\\
B. [[http://web.stanford.edu/class/cs97si/03-data-structures.pdf|data-structures]]\\
C. [[http://web.stanford.edu/class/cs97si/04-dynamic-programming.pdf|dynamic-programming]]\\
D. [[http://web.stanford.edu/class/cs97si/06-basic-graph-algorithms.pdf|basic-graph-algorithms]]\\
E. [[http://web.stanford.edu/class/cs97si/07-shortest-path-algorithms.pdf|shortest-path-algorithms]]\\
F. [[http://web.stanford.edu/class/cs97si/09-computational-geometry.pdf|computational-geometry]] (Stačí konvexní obálka a zametací přímka)\\
G. [[http://web.stanford.edu/class/cs97si/05-combinatorial-games.pdf|combinatorial-games]] (Jako zajímavost na konci semestru)\\

{{:courses:a4b36acm:2013_ls:dp.pdf|Dynamické programování}}\\ 

**Některé referenční implementace** \\ 
[[http://stanford.edu/~liszt90/acm/notebook.html|Stanford ACM team]]

**Přibližně návodná ukázka struktury prezentace**:   {{:courses:a4b36acm:2014_zs:ukazkaprez.pdf| Voda v rourách}}\\
{{:courses:a4b36acm:2014_zs:dp2.pptx| dp}}


----

==== Okruhy pro domácí úlohy ====
Vyberte si libovolnou úlohu z některého okruhu, a řešte. 

1. [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=242|Regionals 2006 - Asia - Beijing]]\\
2. [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=244|Regionals 2006 :: Asia - Dhaka]]\\

Postupně okruhy podle potřeby přibydou...