Seminář | Datum (hodiny) | Náplň | Úlohy/odkazy |
---|---|---|---|
1. | 25.9. (2) | Konto, odevzdání cvičné úlohy | |
2. | 2.10. (4) | Minisoutěž | Regionals 2000: North America - Mid-Central USA Regionals 2006 :: North America - Greater NY Úlohy pro zkušenější jsou pod tabulkou |
3. | 9.10. (2) | Prezentují | Úloha |
1. Vyskočil, Marek: | 3418 - Shuffle'm Up | ||
2. Hubáček, Pichl: | 3498 - Push Button Lock | ||
3. Vavřinec, Šerých: | 3571 - Visible Lattice Points | ||
Výklad: Řešitelova infrastruktura, znalostní cihly. | CS 97SI: Introduction to Competitive Programming Contests | ||
4. | 16.10. (4) | Minisoutěž | Regionals 2006: North America - Mid-Central USA Regionals 2008: Asia - Beijing |
5. | 23.10. (2) | Prezentují | Úloha |
1. Hořeňovský | 3598 - Frugal Search | ||
2. Horák, Váňa | 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ěž | Regionals 2008 - North America - Pacific Northwest Regionals 2007 - North America - Pacific Northwest |
9. | 20.11 (2) | Prezentují | Úloha |
1. Muzika, Briedoň | 4068 - Rubik's Cube(R) | ||
2. MB | 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 | Tabulka |
Zadání jsou řazena libovolně a jsou nekomentována, zadání je většinou samo krátké a přehledné.
Zadání jsou pro jednoduchost řazena v klesajícím pořadí podle délky textu zadání.
2151 - Telescope
2219 - Domino Puzzle
2332 - Cube
2490 - Clock Synchronisation
2522 - Chocolate
2699 - Diamonds
Pěkná motivační úloha na úvod: Kings on the Chessboard
Řešení: kings_bruteforce.c, kings_dp.c, kings_graphs.c
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 SPOJ a UVA.
DP on Trees:
DP on Sequences:
DP on Arrays:
Tiling Grids DP:
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. mathematics
B. data-structures
C. dynamic-programming
D. basic-graph-algorithms
E. shortest-path-algorithms
F. computational-geometry (Stačí konvexní obálka a zametací přímka)
G. combinatorial-games (Jako zajímavost na konci semestru)
Některé referenční implementace
Stanford ACM team
Přibližně návodná ukázka struktury prezentace: Voda v rourách
dp
Vyberte si libovolnou úlohu z některého okruhu, a řešte.
1. Regionals 2006 - Asia - Beijing
2. Regionals 2006 :: Asia - Dhaka
Postupně okruhy podle potřeby přibydou…