Místo a čas konání
T2:C2-84, čtvrtek od 16:15. Rozvrh FEL
Užitečný server A2OJ je mimo provoz, oceníme každý nápad na jeho alespoň částečnou funkční náhradu.
Seminář | Datum (hodiny) | Náplň | Úlohy/odkazy/prezentace viz také pod tabulkou |
---|---|---|---|
1. | 20.2. (4) | Servery, konta, ukázkové úlohy a témata, cvičná odevzdání | Do zápočtu třetí prezenčně vyřešená a pak každá další prezenčně vyřešená úloha v tomto souboru. |
2. | 27.2 (2) | Dynamické programování | |
3. | 5.3. (4) | Minisoutěž I | |
4. | 12.3. (2) | odpadlo kvůli karanténě | |
5. | 19.3. (4) | odpadlo kvůli karanténě |
Online dálková forma předmětu
Seminář | Datum (hodiny) | Náplň | Úlohy/odkazy/prezentace viz také pod tabulkou |
---|---|---|---|
6. | 26.3. (2) | Grafy a nejkratší cesty | |
7. | 2.4. (4) | Minisoutěž II | |
8. | 9.4. (2) | Odpadá, je sudý pátek možný přesun na jindy | hlasujte v Doodle |
9. | 16.4 (4) | Minisoutěž III | |
10. | 23.4. (2) | Aritmetika a kombinatorika, teorie čísel | |
11. | 30.4. (4) | Minisoutěž IV | |
12. | 7.5. (2) | Výpočetní geometrie, mřížky | |
13. | 14.5. (4) | Minisoutěž V | |
14. | 21.5. (2) | Anatgonistické hry, Nim | |
CELKEM | LS 2019 | Průběžný stav | Průběžný stav |
(Starsi orientacni tabulka zde.)
V průběhu praktických cvičení a také při domácí aktivitě svá řešení budete odevzdávat do serverů
Na každém z těchto serverů si zřiďte konto, pokud ho tam ještě nemáte.
Proces lze vyzkoušet s hotovým řešením
Úlohy pro první seminář
Plus trochu více:
21. 3595 - Linear Pachinko
22. 2061 - The Triangle Game
Ukázky typických postupů a úloh.
Nejdelší společná podposloupnost (LIS - Longest Common Subsequence)
Výklad na GeeksForGeeks
Řezání tyče
Cutting a rod
Úlohy
UVA -- 10192 - Vacation
UVA -- 10066 - The Twin Towers
SPOJ -- AIBOHP - Aibohphobia
SPOJ -- ADFRUITS - Advanced Fruits
Problém batohu (Knapsack Problem)
Ukázka 0-1 varianty na GeeksForGeeks
Ukázka neomezené varianty na GeeksForGeeks
Úlohy
UVA -- 562 - Dividing coins
UVA -- 990 - Diving for Gold
UVA -- 10819 - Trouble of 13-Dots
SPOJ -- PIGBANK - Piggy-Bank
Úlohy na dnešní minisoutěž
Semináře odpadají kvůli karanténě. Doporučenou náhradní činností je samostané řešení zbývajících úloh z 1. a 3. semináře. K nim je níže přídána další skupina úloh na DP. Řešení úloh doma mimo seminář je standardně hodnoceno 1 bodem za každou úspěšně vyřešenou úlohu.
S využitím publikace Antti Laaksonen: Competitive Programmer’s Handbook, s několika komentáři.
Originál: ke stažení.
Nejkratší a nejdelší cesty:
Aplikace prohledávání do hloubky:
Všechny cesty:
Minisoutěž proběhne od 16:15 do 20:15. (Jako vždy, kdo chce skončit dříve, může.)
Bodové hodnocení standardní – každá vyřešená úloha se počítá jako prezenčně vyřešená za 3 body.
Ulohy z Online (UVa) Judge je mozno v ramci minisouteze odevzdavat take behem patku 3.4. (do 24:00). Pritom pravidla bodovani jsou:
A. Pokud na berezovs@fel.cvut.cz do 21:00 ve ctvrtek poslete kod odevzdany do serveru pred 20:15 a upraveny kod bude akceptovan behem patku 3.4., bude reseni hodnoceno 3 body. Podminkou je dodatecne zaslani finalniho akceptovaneho kodu na stejnou adresu.
B. Kazdy dalsi kod akceptovany behem patku 3.4. bude hodnocen 2 body.
1. Zapisujte svoje výkony samostatně do Výsledkové tabulky.
2. Po ukončení pošlete otisky obrazovky serveru se záznamem Vašich vyřešených úloh na berezovs@fel.cvut.cz.
3. Úlohy k řešení
Úlohy 12., 13., 14. byly vybrány spíše pro náročnější řešitele .
Pokud neběží Online (UVA) judge, zkuste SPOJ:
Minisoutěž proběhne od 16:15 do 20:15. (Jako vždy, kdo chce skončit dříve, může.)
1. Zapisujte svoje výkony samostatně do Výsledkové tabulky.
2. Po ukončení pošlete otisky obrazovky serveru se záznamem Vašich vyřešených úloh na berezovs@fel.cvut.cz.
3. Úlohy k řešení
Vyzkoušejte si:
Další odkazy související s úlohami
Catalanova čísla
https://en.wikipedia.org/wiki/Catalan_number
Kombinační čísla
http://arantxa.ii.uam.es/~ssantini/writing/notes/s667_binomial.pdf
http://www.zweigmedia.com/RealWorld/tutstats/bincoeffs.html
Modulární mocnění
https://discuss.codechef.com/questions/20451/a-tutorial-on-fast-modulo-multiplication-exponential-squaring
https://en.wikipedia.org/wiki/Modular_exponentiation
Euklidův algoritmus (největší společný dělitel)
http://mathworld.wolfram.com/EuclideanAlgorithm.html
Prvočísla
http://www.geeksforgeeks.org/sieve-of-eratosthenes/
Minisoutěž proběhne od 16:15 do 20:15. (Jako vždy, kdo chce skončit dříve, může.)
1. Zapisujte svoje výkony samostatně do Výsledkové tabulky.
2. Po ukončení pošlete otisky obrazovky serveru se záznamem Vašich vyřešených úloh na berezovs@fel.cvut.cz.
3. Úlohy k řešení
Reminder: Trigonometric identities
Pick's_theorem http://jwilson.coe.uga.edu/emat6680fa05/schultz/6690/pick/pick_main.htm
Všeobecný přehled na MFF (Programátorské kuchařky) http://ksp.mff.cuni.cz/tasks/24/cook5.html
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
Very Brute force Binary Search: https://onlinejudge.org/external/105/10566.pdf
Sweep line example Touching rectangles
Sweep line rotates:, http://www.spoj.com/problems/CERC07C/ (*_*_*) komentář
Graham Scan demo: http://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/ah/GrahamScan.html (enable java?)
code: http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
Stanford examples: http://web.stanford.edu/class/cs97si/ (Namely: http://web.stanford.edu/class/cs97si/09-computational-geometry.pdf )
Rotate points instead of lines 8258 - Glyph Recognition ( solution idea)
Množství komentovaných základních kódů https://www.geeksforgeeks.org/geometric-algorithms/
Kreslítko GeoGebra online http://www.geogebra.org/
Seznamy geometrických kreslítek https://en.wikipedia.org/wiki/List_of_interactive_geometry_software#2D_programs, http://mathforum.org/geometry/geometry.software.html
Minisoutěž proběhne od 16:15 do 20:15. (Jako vždy, kdo chce skončit dříve, může.)
1. Zapisujte svoje výkony samostatně do Výsledkové tabulky.
2. Po ukončení pošlete otisky obrazovky serveru se záznamem Vašich vyřešených úloh na berezovs@fel.cvut.cz.
3. Úlohy k řešení
Příklady: