**Místo a čas konání** T2:C2-84, čtvrtek od 16:15. [[http://www.fel.cvut.cz/cz/education/rozvrhy-ng.B192/public/html/mistnosti/10/12/m10125804.html|Rozvrh FEL]] Od 26.3. pokračuje předmět v dálkové online formě podle původního časového rozvrhu. \\ Další upřesnění viz níže. ===== Semináře ===== Užitečný server [[https://www.a2oj.com/|A2OJ]] je mimo provoz, oceníme každý nápad na jeho alespoň částečnou funkční náhradu. ==== Tabulka s průběžným stavem bodování ==== [[https://docs.google.com/spreadsheets/d/1nZnj_9iuVzU3vnpctgkoF_40C2PgYXoILCdDHFGpB4Y/edit?usp=sharing| Průběžný stav ]] ^ 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** | [[https://doodle.com/poll/99srt6wss9bk9ds9|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 | | https://cw.fel.cvut.cz/wiki/courses/a4b36acm1/2020_ls/seminare?do=edit | **13.** | **14.5.** (4) | **Minisoutěž V** | | | **14.** | **21.5.** (2) | Anatgonistické hry, Nim | | | **CELKEM** | LS 2019 | **Průběžný stav** | [[https://docs.google.com/spreadsheets/d/1nZnj_9iuVzU3vnpctgkoF_40C2PgYXoILCdDHFGpB4Y/edit?usp=sharing| Průběžný stav ]] | (Starsi orientacni tabulka [[https://docs.google.com/spreadsheets/d/1D-CyV5uWdDWAYv5I7Z0ett2qwSQcOntvPIbj_j0QLQM/edit?usp=sharing| zde]].) ---- ===== Seminář 1 ===== ==== Provoz a administrace ==== V průběhu praktických cvičení a také při domácí aktivitě svá řešení budete odevzdávat do serverů * [[https://onlinejudge.org/|Online Judge]] (dříve "UVa Online Judge") * [[https://www.spoj.com/|Sphere Online Judge]] (neboli "SPOJ") * [[https://icpcarchive.ecs.baylor.edu/|Live Archive]] (Úlohy z ACM soutěží) Na každém z těchto serverů si zřiďte konto, pokud ho tam ještě nemáte. [[https://cw.fel.cvut.cz/wiki/courses/a4b36acm/trenink?&#jak_na_reseni| Návodník na řešení ]] [[https://cw.fel.cvut.cz/wiki/courses/a4b36acm1/intro_basic|Proces lze vyzkoušet s hotovým řešením]] **Úlohy pro první seminář** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=9&page=show_problem&problem=646 | 705 - Slash Maze ]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=961 | 10020 - Minimal coverage ]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1073 | 10132 - File Fragmentation ]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1102 | 10161 - Ant on a Chessboard ]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2486 | 11491 - Erasing and Winning ]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2513 | 11518 - Dominos 2 ]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2544 | 11549 - Calculator Conundrum ]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2619 | 11572 - Unique Snowflakes ]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=441&page=show_problem&problem=3990 | 12545 - Bits Equalizer ]] - [[https://www.spoj.com/problems/ADDREV | ADDREV - Adding Reversed Numbers ]] - [[https://www.spoj.com/problems/AE1B | AE1B - Tables ]] - [[https://www.spoj.com/problems/AMR10G | AMR10G - Christmas Play ]] - [[https://www.spoj.com/problems/CANDY | CANDY - Candy I ]] - [[https://www.spoj.com/problems/EMTY2 | EMTY2 - Can You Make It Empty 2 ]] - [[https://www.spoj.com/problems/FACEFRND | FACEFRND - Friends of Friends ]] - [[https://www.spoj.com/problems/GERGOVIA | GERGOVIA - Wine trading in Gergovia ]] - [[https://www.spoj.com/problems/HANGOVER | HANGOVER - Hangover ]] - [[https://www.spoj.com/problems/PERMUT2 | PERMUT2 - Ambiguous Permutations ]] - [[https://www.spoj.com/problems/SNGINT | SNGINT - Encode Integer ]] - [[https://www.spoj.com/problems/TOE1 | TOE1 - Tic-Tac-Toe ( I ) ]] Plus trochu více: 21. [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=264&page=show_problem&problem=1596| 3595 - Linear Pachinko ]] \\ 22. [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=62| 2061 - The Triangle Game]] ---- ===== Seminář 2: Dynamické programování ===== Ukázky typických postupů a úloh. * {{ :courses:a4b36acm2:2018_ls:dag.pdf | Základní všechno možné průchodem DAG }} * [[https://cw.fel.cvut.cz/wiki/courses/a4b36acm2/2016_zs/code#elementary_dag_manipulation| Ukázka kódu -- manipulace s DAG]] * {{ :courses:a4b36acm2:2018_ls:ukazkaprez3.pdf | Ukázka řešení -- Voda v rourách}} * {{ :courses:a4b36acm2:2018_ls:lisnlogn.pdf | LIS - nejdelší rostoucí podposloupnost v čase O(N log N) }} * [[https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/|LIS na GeeksforGeeks ]] * [[https://cw.fel.cvut.cz/wiki/courses/a4b36acm/2016_zs/code#elementary_dag_manipulation| Ukázka kódu -- manipulace s DAG]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=841|900 - Brick Wall Patterns]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1275 * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1022|10081 - Tight Words]] * [[http://www.spoj.com/problems/FARIDA/|FARIDA - Princess Farida]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1275|10334 - Ray Through Glasses]] * [[http://www.spoj.com/problems/MMAXPER/| MMAXPER, Rectangles Perimeter - max upper envelope length]] * [[https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=929|Many Paths, One Destination]] * [[http://www.spoj.com/problems/SUBP/|Subsequence Problem]] * [[http://www.spoj.com/problems/BABTWR/|Tower of Babylon]] * [[http://www.spoj.com/problems/WACHOVIA/|Wachovia Bank]] * [[http://www.spoj.com/problems/MFISH/|Catch Fish]] * [[http://www.spoj.com/problems/GCJ1C09C/|Bribe the Prisoners]] * [[http://www.spoj.com/problems/BORW/|Black or White]] ==== Některé kanonické úlohy DP ==== **Nejdelší společná podposloupnost (LIS - Longest Common Subsequence)**\\ [[https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/| Výklad na GeeksForGeeks]]\\ **Řezání tyče**\\ [[https://www.geeksforgeeks.org/cutting-a-rod-dp-13/|Cutting a rod]]\\ Úlohy\\ [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1133|UVA -- 10192 - Vacation]]\\ [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1007|UVA -- 10066 - The Twin Towers]]\\ [[https://www.spoj.com/problems/AIBOHP/|SPOJ -- AIBOHP - Aibohphobia]]\\ [[https://www.spoj.com/problems/ADFRUITS/|SPOJ -- ADFRUITS - Advanced Fruits]]\\ **Problém batohu (Knapsack Problem)**\\ [[https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/| Ukázka 0-1 varianty na GeeksForGeeks]]\\ [[https://www.geeksforgeeks.org/unbounded-knapsack-repetition-items-allowed/| Ukázka neomezené varianty na GeeksForGeeks]]\\ Úlohy\\ [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=503|UVA -- 562 - Dividing coins]]\\ [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=931|UVA -- 990 - Diving for Gold]]\\ [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1760|UVA -- 10819 - Trouble of 13-Dots]]\\ [[https://www.spoj.com/problems/PIGBANK/|SPOJ -- PIGBANK - Piggy-Bank]]\\ ===== Seminář 3: Dynamické programování ===== Úlohy na dnešní minisoutěž * https://www.spoj.com/problems/ACMAKER * https://www.spoj.com/problems/ACODE * https://www.spoj.com/problems/DCEPC501 * https://www.spoj.com/problems/MARTIAN * https://www.spoj.com/problems/MIXTURES * https://www.spoj.com/problems/ROCK * https://www.spoj.com/problems/SCUBADIV * https://www.spoj.com/problems/STONE2 * https://www.spoj.com/problems/TRIP * https://www.spoj.com/problems/TWENDS ===== Semináře 4 a 5 ===== 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. * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=446&page=show_problem&problem=4097| 1351 - String Compression ]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=970| 10029 - Edit Step Ladders ]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1010| 10069 - Distinct Subsequences ]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1875| 10934 - Dropping water balloons ]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2225| 11258 - String Partition ]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2415| 11420 - Chest of Drawers ]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2547| 11552 - Fewest Flops ]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2664| 11617 - An Odd Love ]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=117&page=show_problem&problem=2890| 11790 - Murcia's Skyline]] ===== Seminář 6 (Online) Grafové algoritmy ===== S využitím publikace {{ :courses:a4b36acm1:2020_ls:laaksonen_programmershandbook.pdf | Antti Laaksonen: Competitive Programmer’s Handbook, s několika komentáři}}. \\ Originál: [[https://cses.fi/book/book.pdf|ke stažení]]. ==== Přehledy a návody ==== Nejkratší a nejdelší cesty: * {{ :courses:a4b36acm2:2018_ls:grafy-cesty.pdf | nejkratší a nejdelší cesty -- celkový přehled }} * {{ :courses:a4b36acm2:2018_ls:dag.pdf | nejkratší a nejdelší cesty v DAG }} Aplikace prohledávání do hloubky: * {{ :courses:a4b36acm1:2020_ls:dfs.pptx | Napřed vůbec DFS}} * [[https://www.geeksforgeeks.org/topological-sorting-using-departure-time-of-vertex/| topsort by DFS]] * [[http://www.geeksforgeeks.org/detect-cycle-undirected-graph/|Detekce cyklu v grafu]] * [[http://www.geeksforgeeks.org/topological-sorting/|Nalezení topologického uspořádání vrcholů v grafu]] * [[http://www.geeksforgeeks.org/bridge-in-a-graph/|Identifikace mostů.]] (*_*_*) * [[http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/|Identifikace artikulací]] (*_*_*) * [[http://www.geeksforgeeks.org/biconnected-components/|Detekce bloků, tj. 2-souvislých komponent]] * [[http://www.geeksforgeeks.org/strongly-connected-components/|Nalezení silně souvislých komponent]] {{https://cw.fel.cvut.cz/old/_media/courses/a4b36acm/2017_zs/mst3.pptx|Poznámky k minimálním kostrám }} Všechny cesty: * [[https://www.geeksforgeeks.org/detect-negative-cycle-graph-bellman-ford/|Bellman-Ford]] * [[https://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/|Floyd-Warshall]] * [[http://wikistack.com/all-pair-shortest-path-floyd-warshall-algorithm/|Floyd-Warshall algorithm example]] [[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html|další vizualizace]] ==== Ukazkové úlohy k domacímu řešení ==== * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=61|125 - Numbering Paths]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=473 | 532 - Dungeon Master]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=475 | 534 - Frogger]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=499|558 - Wormholes]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=116&page=show_problem&problem=508|567 - Risk]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=513|572 - Oil Deposits]] * [[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!]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=1246|10305 - Ordering Tasks]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1400 | 10459 - The Tree Root]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=1537|10596 - Morning Walk]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=116&page=show_problem&problem=1549|10608 - Friends]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1613|10672 - Marbles on a tree]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1642 | 10701 - Pre, in and post]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=116&page=show_problem&problem=1926|10985 - Rings'n'Ropes]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2733|11686 - Pick up sticks]] * [[https://www.spoj.com/problems/SAMER08A/|SAMER08A - Almost Shortest Path]] ===== Seminář 7 (programovací online dne 2.4.) Minisoutěž Grafové algoritmy ===== 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 [[https://docs.google.com/spreadsheets/d/13-FUmkmnbN5QlSxcEyfAuANNtgqZBVdhJbUenRch6AE/edit?usp=sharing|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í** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=372&page=show_problem&problem=3646|1205 - Color a Tree]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=37&page=show_problem&problem=945|10004 - Bicoloring]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=988|10047 - The Monocycle]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=37&page=show_problem&problem=992|10051 - Tower of Cubes]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=38&page=show_problem&problem=995|10054 - The Necklace]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=37&page=show_problem&problem=1008|10067 - Playing with Wheels]] - [[https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1040|10099 - The Tourist Guide]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1310|10369 - Arctic Network]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=373&page=show_problem&problem=2597|11561 - Getting Gold]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2620|11573 - Ocean Currents]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2671|11624 - Fire!]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=251|315 - Network]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=37&page=show_problem&problem=1217|10276 - Hanoi Tower Troubles Again!]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1451|10510 - Cactus]] Úlohy 12., 13., 14. byly vybrány spíše pro náročnější řešitele :-). Pokud neběží Online (UVA) judge, zkuste SPOJ: * 15. https://www.spoj.com/problems/ELEVTRBL/ * 16. https://www.spoj.com/problems/CAM5/ * 17. https://www.spoj.com/problems/PT07Z/ * 18. https://www.spoj.com/problems/MICEMAZE/ * 19. https://www.spoj.com/problems/ANARC08G/ * 20. https://www.spoj.com/problems/WORDS1/ * 21. https://www.spoj.com/problems/SUBMERGE/ ===== Seminář 9 (programovací online dne 16.4.) Minisoutěž Grafové algoritmy a II a DP ===== 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 [[https://docs.google.com/spreadsheets/d/1tfD93Dt1LBRWFMMz1nDVS5Fmc44cUqWZbJJihOO0Ug4/edit?usp=sharing|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í** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=156&page=show_problem&problem=136|200 - Rare Order]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=152&page=show_problem&problem=196|260 - Il Gioco dell'X]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=153&page=show_problem&problem=551|610 - Street Directions]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=152&page=show_problem&problem=725|784 - Maze Exploration]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=149&page=show_problem&problem=1184|10243 - Fire! Fire!! Fire!!!]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=164&page=show_problem&problem=1219|10278 - Fire Station]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=175&page=show_problem&problem=1249|10308 - Roads in the North]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=147&page=show_problem&problem=1643|10702 - Travelling Salesman]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=142&page=show_problem&problem=2451|11456 - Trainsorting]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=159&page=show_problem&problem=2678|11631 - Dark roads]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=155&page=show_problem&problem=2756|11709 - Trust groups]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=159&page=show_problem&problem=2833|11733 - Airports]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=155&page=show_problem&problem=2870|11770 - Lighting Away ]] ===== Seminář 10 Aritmetika a kombinatorika ===== * [[https://math.feld.cvut.cz/habala/teaching/dma/dmknih11.pdf|Habalova kombinatorická skripta]]! * {{ :courses:a4b36acm1:2020_ls:habalavycuckombi.pdf | Z těchto skript tahák}} * {{ :courses:a4b36acm1:2020_ls:primes.pdf | Prvočísla, Eratosthenovo síto a kód }} * [[hhttps://en.wikipedia.org/wiki/Modular_arithmetic|Modulární aritmetika]] (Převážně stejná jako ta běžná) * Čísla různých druhu: * [[https://en.wikipedia.org/wiki/Combination|Kombinační]] * [[https://en.wikipedia.org/wiki/Fibonacci_number|Fibonacciho]] * [[https://www.geeksforgeeks.org/applications-of-catalan-numbers/|Catalanova]] , [[http://mathworld.wolfram.com/CatalanNumber.html|na Mathworld]] * **OEIS** Vynikající všeobecná referenční příručka [[https://oeis.org/|The On-Line Encyclopedia of Integer Sequences]] * Rychlé mocnění * https://www.geeksforgeeks.org/exponential-squaring-fast-modulo-multiplication/ * https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/ * * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=1154|10213 - How Many Pieces of Land ?]] Eulerova formule V+F = E+2 Vyzkoušejte si: * http://www.spoj.com/problems/AMR11E/ * http://www.spoj.com/problems/APS/ * http://www.spoj.com/problems/LCMSUM/ * https://www.spoj.com/problems/PTIME/ * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2403|11408 - Count DePrimes]] **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/\\ ===== Seminář 11 (programovací online dne 30.4.) Minisoutěž Aritmetika a kombinatorika ===== 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 [[https://docs.google.com/spreadsheets/d/1xVUUyg5CGP-MsEn5DuK1GTez-pFhx5poZ7IA57j9FCI/edit?usp=sharing|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í** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=416&page=show_problem&problem=1051|10110 - Light, more light]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=194&page=show_problem&problem=1080|10139 - Factovisors]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=193&page=show_problem&problem=1170|10229 - Modular Fibonacci]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=196&page=show_problem&problem=1316|10375 - Choose and divide]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=196&page=show_problem&problem=1731|10790 - How Many Points of Intersection?]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=196&page=show_problem&problem=2010|11069 - A Graph Problem]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=189&page=show_problem&problem=2383|11388 - GCD LCM]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=162&page=show_problem&problem=2423|11428 - Cubes]] - [[https://www.spoj.com/problems/DIVSUM/ |DIVSUM - Divisor Summation]] - [[https://www.spoj.com/problems/FCDC/ |FCDC - Factorial Modulo]] - [[https://www.spoj.com/problems/HS08PAUL/ |HS08PAUL - A conjecture of Paul Erdos]] - [[https://www.spoj.com/problems/LCMSUM/ |LCMSUM - LCM Sum]] - [[https://www.spoj.com/problems/MB1/ |MB1 - PP numbers]] - [[https://www.spoj.com/problems/TREE1/ |TREE1 - Tree]] - [[https://www.spoj.com/problems/UCV2013A/ |UCV2013A - Counting Ids]] ===== Seminář 12: Geometrie ===== **{{ :courses:a4b36acm1:2020_ls:geombas1upd.pptx | Některé základní výpočty }} ** **[[https://en.wikipedia.org/wiki/Intersection_(Euclidean_geometry)| Počítání průsečíků]]** **[[https://en.wikipedia.org/wiki/List_of_trigonometric_identities|Reminder: Trigonometric identities]]** **[[https://en.wikipedia.org/wiki/Pick's_theorem|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** {{ :courses:a4b36acm2:2018_ls:sweeplinexx.pptx | Touching rectangles}} **Sweep line rotates:**, http://www.spoj.com/problems/CERC07C/ (*_*_*) {{ :courses:a4b36acm2:2018_ls:spojcerc07c.pptx | 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** [[https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=6280| 8258 - Glyph Recognition]] ({{ :courses:a4b36acm1:2019_ls:glyphs.pptx | 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 ===== Seminář 13 (programovací online dne 14.5.) Minisoutěž Geometrie ===== 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 [[https://docs.google.com/spreadsheets/d/1VhwbpviyBIe0v-qMsaNuWqJO9zIK7cxgK2Mr6tR5vyY/edit?usp=sharing|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í** - [[https://www.spoj.com/problems/ADAPICK/ | ADAPICK - Ada and Cucumber ]] - [[https://www.spoj.com/problems/ANARC09F/ | ANARC09F - Air Strike ]] - [[https://www.spoj.com/problems/BLMIRANA/ | BLMIRANA - Mayonnaise Arrow]] - [[https://www.spoj.com/problems/BSHEEP/ | BSHEEP - Build the Fence ]] - [[https://www.spoj.com/problems/CATTLEB/ | CATTLEB - Cattle Bruisers ]] - [[https://www.spoj.com/problems/CHASE/ | CHASE - A Chase In WonderLand ]] - [[https://www.spoj.com/problems/CONDUIT/ | CONDUIT - I Conduit ]] - [[https://www.spoj.com/problems/DOORSPEN/ | DOORSPEN - Doors and Penguins ]] - [[https://www.spoj.com/problems/EQBOX/ | EQBOX - Equipment Box ]] - [[https://www.spoj.com/problems/GEOM/ | GEOM - Geometry and a Square ]] - [[https://www.spoj.com/problems/GEOPROB/ | GEOPROB - One Geometry Problem ]] - [[https://www.spoj.com/problems/GOALFR/ | GOALFR - Goal for Raúl ]] - [[https://www.spoj.com/problems/HAMSTER1/ | HAMSTER1 - Hamster flight ]] - [[https://www.spoj.com/problems/LEAF/ | LEAF - Leaf ]] - [[https://www.spoj.com/problems/RROOT/ | RROOT - REAL ROOTS ]] ===== Seminář 14 - Kombinatoricke hry ===== * [[http://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/intro.pdf|Všeobecné poučení o hrách a Nimu]] [[http://mks.mff.cuni.cz/library/JakHratANeprohratFH/JakHratANeprohratFH.pdf|(výtah, česky)]] * [[http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames | TopCoder - The Basic Introduction into Games]] * [[http://teorie-grafu.cz/zakladni-pojmy/jadro-grafu.php | Jádro grafu]] * Teorie her na CMU - [[http://www.math.cmu.edu/~mlavrov/arml/12-13/games-02-10-13.pdf|Combinatorial Game Theory]],[[http://www.math.cmu.edu/~mlavrov/arml/12-13/games-02-24-13.pdf|Even More Games]] * Kombinatorické hry - krátká ilustrace {{ :courses:a4b36acm2:2018_zs:combigames.pdf | pdf}}. * Nimbers (Sprague-Grundyho čísla) - ukázková úloha ([[http://www.codechef.com/problems/BIGPIZA| Socializing Game around Pizza]], {{ :courses:a4b36acm2:2018_zs:pizza.pdf | kód? }}) * [[http://www.fq.math.ca/Scanned/1-4/whinihan.pdf|Fibonacciho Nim]] Příklady: * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=330&page=show_problem&problem=1345|Bachet's Game]] * [[http://www.spoj.com/problems/CLK/|Chomp]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=330&page=show_problem&problem=1309|Euclid's Game]] * [[http://www.spoj.com/problems/QCJ3/|The Game]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=330&page=show_problem&problem=2484|Integer Game]] * [[http://www.spoj.com/problems/MATGAME/|Matrix Game]] * [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=398&page=show_problem&problem=2824|Game]] * [[http://www.spoj.com/problems/QWERTY04/|TRIVIADOR]] * [[https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=3060|Playing With Stones]] * [[http://www.spoj.com/problems/MMMGAME/en/|M&M Game]] * [[http://www.spoj.com/problems/NGM/|A Game with Numbers]] * [[http://www.spoj.com/problems/PT07A/|Play with a Tree]]: How to tackle a problem of this sort was not covered in the lecture, but if you are interested, see [[http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf|Ferguson's Game Theory]] (lecture 6, specifically, the colon and fusion principles). * [[http://www.spoj.com/problems/BNWNIM/en/|Black and White Nim]]: Difficult, yet intriguing problem. *