**Místo a čas konání** T2:C2-84, čtvrtek od 16:15. [[https://fel.cvut.cz/cz/education/rozvrhy-ng.B221/public/html/mistnosti/10/12/m10125804.html|Rozvrh FEL]] ===== Semináře ===== ==== Tabulka s průběžným stavem bodování ==== ^ Seminář ^ Datum \\ (hodiny) ^ Náplň ^ Úlohy/odkazy/prezentace \\ viz také pod tabulkou ^ | **1.** | **22.9.** (4) | Servery, konta, ukázkové úlohy a témata, cvičná odevzdání, jednoduchá opakování | | | **2.** | **29.9.** (2) | Cesty v grafech | | | **3.** | **6.10.** (4) | ** Minisoutěž I** | | | **4.** | **13.10.** (2) | Dynamické programování I | | | **5.** | **20.10.** (4) | ** Minisoutěž II** | | | **6.** | **27.10.** (2) | Dynamické programování II | | | **7.** | **3.11.** (4) | ** Minisoutěž III** | | | **8.** | **10.11.** (2) | Aritmetika a kombinatorika, teorie čísel | | | **9.** | **17.11.** (4) | // odpadá, je státní svátek // | | | **10.** | **24.11.** (4) | ** Minisoutěž IV** | | | **11.** | **1.12.** (2) | Výpočetní geometrie, mřížky | | | **12.** | **8.12.** (4) | ** Minisoutěž V** | | | **13.** | **15.12.** (2) | Kombinatorické hry, Nim | | | **14.** | **12.1.** (4) | ** Minisoutěž VI** | | | **CELKEM** | ZS 202` . . . . | **TABULKA - VÝSLEDKY ** | [[https://docs.google.com/spreadsheets/d/1K87iUVGJkD69ELQccQYcWY5BJRbjpyb6r1GrN8GV8k4/edit?usp=sharing| Tady je celkový stav ]] | ---- ===== Seminář 1 (22.9.) ===== ==== 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ář ==== Komentáře k úlohám na zamyšlení, jednoduché obraty ve snazších úlohách * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=74|138 - Street Numbers]] * [[https://www.spoj.com/problems/BUSYMAN/|BUSYMAN - I AM VERY BUSY]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=99&page=show_problem&problem=1102|10161 - Ant on a Chessboard]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=99&page=show_problem&problem=1731|10790 - How Many Points of Intersection?]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=72|136 - Ugly Numbers]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2510|11515 - Cranes]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=41|105 - The Skyline Problem]] ** Vyzkoušejte si:** \\ //Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady "začínající" nezískají body.\\ Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady. // \\ Svoje výkony zapisujte **samostatně** do tabulky [[https://docs.google.com/spreadsheets/d/1E2w0SkJvNr8aqb2mDuSkT14P-gF80rlM4LgSKZFdlpw/edit?usp=sharing|Výkony v minisoutěži 0]],\\ po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz. **Začínající zkusí** (**Upozornění**: Úlohy níže jsou řazeny abecedně podle svých názvů, což nesouvisí s jejich tématikou, obtížností nebo jinými parametry.) - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=36|100 - The 3n + 1 problem]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=38|102 - Ecological Bin Packing]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=30&page=show_problem&problem=979|10038 - Jolly Jumpers]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1238|10297 - Beavergnaw]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=121&page=show_problem&problem=1985|11044 - Searching for Nessy]] - [[https://www.spoj.com/problems/PERMUT2/|PERMUT2 - Ambiguous Permutations]] - [[https://www.spoj.com/problems/TEST/|TEST - Life, the Universe, and Everything]] **Pokročilí nebo začínající zkusí** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=48|112 - Tree Summing]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=56|120 - Stacks of Flapjacks]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=515|574 - Sum It Up]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=802|861 - Little Bishops]] - [[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=841&page=show_problem&problem=2000|11059 - Maximum Product]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2614|11567 - Moliu Number Generator]] ===== Seminář 2 (29.9.) Cesty v grafech ===== ==== Přednáška ==== Především BFS, DFS, Dijkstra, odkazy viz níže. ==== 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 }} {{ :courses:a4b36acm1:2021_zs:dijkstra_n_2.pdf | Dijkstra v O(n^2) }} Cesty v stromech (nejdelší, nejkratší i jiné) bývají řešitelné pomocí DP,\\ to jest zakořeněním stromu a aplikací postorder průchodu stromem. * https://www.geeksforgeeks.org/dynamic-programming-trees-set-1/ Aplikace prohledávání do hloubky: * [[https://www.youtube.com/watch?v=NUgMa5coCoE|Napřed ukázka DFS za běhu]] * {{ :courses:a4b36acm1:2021_zs:dfs.pdf | statický přehled }} * [[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 }} Negativní cykly: * [[https://www.geeksforgeeks.org/detect-negative-cycle-graph-bellman-ford/|Bellman-Ford]] Cesty mezi všemi páry uzlů: * [[https://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/|Floyd-Warshall]] * [[https://www.cs.usfca.edu/~galles/visualization/Floyd.html|Floyd-Warshall algorithm example]] [[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html|Další vizualizace]] Dalších 200+ ukázek a úloh: * [[https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/|Graph Data Structure And Algorithms]] ===== Seminář 03 (6.10.) ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1sfKyl4uubWONqIjcoXSzoHyU_3rTXzZOU2BNaF2vBuA/edit?usp=sharing|Výkony v minisoutěži I]],\\ po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz. **Sada začínající** //Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady "začínající" nezískají body.\\ Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady. // \\ **Mimořádné opatření** Během semináře 6.10. mohou **začínající** účastníci také řešit a odevzdávat libovolné úlohy z 1. semináře (22.9.). Body se za ně budou započítávat stejně jako za úlohy níže. - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=39|103 - Stacking Boxes]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=667&page=show_problem&problem=725|784 - Maze Exploration]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=148&page=show_problem&problem=865|924 - Spreading The News]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=22&page=show_problem&problem=1990|11049 - Basic wall maze]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=551&page=show_problem&problem=2352|11367 - Full Tank?]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2306|11331 - The Joys of Farming]] - [[https://www.spoj.com/problems/ALLIZWEL/|ALLIZWEL - ALL IZZ WELL]] - [[https://www.spoj.com/problems/CATM/|CATM - The Cats and the Mouse]] - [[https://www.spoj.com/problems/HIGHWAYS/|HIGHWAYS - Highways]] - [[https://www.spoj.com/problems/LABYR1/|LABYR1 - Labyrinth]] **Sada pokročilá** - [[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=11&page=show_problem&problem=926|985 - Round and Round Maze]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=160&page=show_problem&problem=1338|10397 - Connect the Campus]] - [[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=17&page=show_problem&problem=1451|10510 - Cactus]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1613|10672 - Marbles on a tree]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1645|10704 - Traffic!]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2540|11545 - Avoiding Jungle in the Dark]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=117&page=show_problem&problem=2870|11770 - Lighting Away]] - [[https://www.spoj.com/problems/SAMER08A/|SAMER08A - Almost Shortest Path]] ===== Seminář 4 (13.10.) Dynamické programování I ===== Ukázky typických postupů a úloh. * {{ :courses:a4b36acm2:2018_ls:dag.pdf | Základní všechno možné průchodem 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/a4b36acm1/2016_zs/code#elementary_dag_manipulation| Ukázka kódu -- manipulace s DAG]] * Násobení Matic: https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/ * Řezání tyče: https://www.geeksforgeeks.org/cutting-a-rod-dp-13/ * Nejdelší společná podposloupnost (LCS): https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/ * Online výpočet LCS: https://www.cs.usfca.edu/~galles/visualization/DPLCS.html (rekurze, tabulka, memoizace = kombinace rekurze a tabulky) * Úloha batohu 0/1: https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/ * Úloha batohu neomezená: https://www.geeksforgeeks.org/unbounded-knapsack-repetition-items-allowed/ * Zkopírováno z ALG: {{ :courses:a4b36acm1:2020_zs:batoh01.pdf | batoh01}}, {{ :courses:a4b36acm1:2020_zs:lcs.pdf | LCS Nejdelsi spolecna podposloupnost}}, {{ :courses:a4b36acm1:2020_zs:mtice.pdf | nasobeni matic }}. **Úlohy pro rozmyšlení** [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1007|10066 - The Twin Towers]] \\ [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1853| 10912 - Simple Minded Hashing]] \\ [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2427|11432 - Busy Programmer]] \\ [[http://www.spoj.com/problems/SQRBR/|Square Brackets]] \\ [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=83|147 - Dollars]] \\ [[http://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/PT07X/|Vertex Cover]] \\ [[http://www.spoj.com/problems/M3TILE/|LATGACH3]] \\ [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2664|11617 - An Odd Love]] ===== Seminář 05 (20.10.) ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/13SYfNGfWcr8kZ_KcquSVKnLuoaJgP9Fap9K00IMLWIM/edit?usp=sharing|Výkony v minisoutěži II]],\\ po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz. //Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady "začínající" nezískají body.\\ Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady. // \\ **Sada začínající** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=378|437 - The Tower of Babylon]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=825&page=show_problem&problem=4507|1632 - Alibaba]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1226|10285 - Longest Run on a Snowboard]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1505|10564 - Paths through the Hourglass]] - [[https://www.spoj.com/problems/ACODE/|ACODE - Alphacode]] - [[https://www.spoj.com/problems/ANARC05B/|ANARC05B - The Double HeLiX]] - [[https://www.spoj.com/problems/BYTESM2/|BYTESM2 - Philosophers Stone]] - [[https://www.spoj.com/problems/CPCRC1C/|CPCRC1C - Sum of Digits]] - [[https://www.spoj.com/problems/DIEHARD/|DIEHARD - DIE HARD]] - [[https://www.spoj.com/problems/FARIDA/|FARIDA - Princess Farida]] **Sada pokročilá** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=780|839 - Not so Mobile]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=823|882 - The Mailbox Manufacturers]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=931|990 - Diving for Gold]] - [[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=18&page=show_problem&problem=1567|10626 - Buying Coke]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1875|10934 - Dropping water balloons]] - [[https://www.spoj.com/problems/ABA12C/|ABA12C - Buying Apples!]] - [[https://www.spoj.com/problems/ADASEQEN/|ADASEQEN - Ada and Subsequence]] - [[https://www.spoj.com/problems/AE2A/|AE2A - Dice]] - [[https://www.spoj.com/problems/BORW/|BORW - Black or White]] ===== Seminář 06 (27.10.) Dynamické programování II ===== Dodělávky: Viz Seminář 04 a úlohy v něm. ===== Seminář 07 (3.11.) ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1C9qhusrYsORofmgRfnCA67MM2GSOGzmlbHtLn7rwlDg/edit?usp=sharing|Výkony v minisoutěži III]],\\ po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz. //Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady "začínající" nezískají body.\\ Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady. // \\ **Sada začínající** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=841|900 - Brick Wall Patterns]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=944|10003 - Cutting Sticks]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=992|10051 - Tower of Cubes]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1133|10192 - Vacation]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1202|10261 - Ferry Loading]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1275|10334 - Ray Through Glasses]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=22&page=show_problem&problem=2022|11081 - Strings]] - [[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://www.spoj.com/problems/MMAXPER/|MMAXPER - Rectangles Perimeter]] **Sada pokročilá** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=603|662 - Fast Food]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1221|10280 - Old Wine Into New Bottles]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1254|10313 - Pay the Price]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1342|10401 - Injured Queen Problem]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1592|10651 - Pebble Solitaire]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1884|10943 - How do you add?]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=22&page=show_problem&problem=1944|11003 - Boxes]] - [[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=27&page=show_problem&problem=2616|11569 - Lovely Hint]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2701|11654 - Arithmetic Subsequence]] ===== Seminář 08 (10.11.) Aritmetika a kombinatorika, teorie čísel ===== * [[https://math.fel.cvut.cz/cz/lide/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á) * [[https://en.wikipedia.org/wiki/Arithmetico–geometric_sequence| Sčítání čísel (aritmeticko-geometrická posloupnost)]] * Čí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 * Příklad nezbytného předpočítání [[https://contest.felk.cvut.cz/22prg/solved/array/problem.pdf|Arrays/CTU Open 2022]] 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 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ář 09 (17.11.) Není ===== Způsobil však změnu v rozvrhu: {{:courses:a4b36acm3:2022_zs:clipboard03.jpg?650|}} ===== Seminář 10 (24.11.) ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1nTih4psf1FszxeLMtVeVQrGVxL8VXMdRVNevMyd_NtM/edit?usp=sharing|Výkony v minisoutěži IV]],\\ po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz. //Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady "začínající" nezískají body.\\ Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady. // \\ **Sada začínající** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=305|369 - Combinations]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=188&page=show_problem&problem=484|543 - Goldbach's Conjecture]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=196&page=show_problem&problem=932|991 - Safe Salutations]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=188&page=show_problem&problem=1474|10533 - Digit Primes]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=188&page=show_problem&problem=1640|10699 - Count the factors]] - [[https://www.spoj.com/problems/DIVSUM/|DIVSUM - Divisor Summation]] - [[https://www.spoj.com/problems/GUANGGUN/|GUANGGUN - 111…1 Squared]] - [[https://www.spoj.com/problems/MB1/|MB1 - PP numbers]] - [[https://www.spoj.com/problems/MMFLPDIV/|MMFLPDIV - Least prime divisor]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=247&page=show_problem&problem=3671|1230 - MODEX]] **Sada pokročilá** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=188&page=show_problem&problem=947|10006 - Carmichael Numbers]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1039|10098 - Generating Fast]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1218|10277 - Boastin' Red Socks]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1432|10491 - Cows and Cars]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1700|10759 - Dice Throwing]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=416&page=show_problem&problem=2319|11344 - The Huge One]] - [[https://www.spoj.com/problems/APS/|APS - Amazing Prime Sequence]] - [[https://www.spoj.com/problems/BINSTIRL/|BINSTIRL - Binary Stirling Numbers]] - [[https://www.spoj.com/problems/CUBEFR/|CUBEFR - Cube Free Numbers]] - [[https://www.spoj.com/problems/HS08PAUL/|HS08PAUL - A conjecture of Pál Erdős]] ===== Seminář 11 (1.12.) Výpočetní geometrie, mřížky ===== Determinant matice, většinou stačí 2×2. **{{ :courses:a4b36acm1:2020_ls:geombas1upd.pptx | Některé základní výpočty }}** ({{ :courses:a4b36acm1:2021_zs:geombas1upd.pdf |pdf verze }}) **[[https://en.wikipedia.org/wiki/Intersection_(Euclidean_geometry)| Počítání průsečíků]]** Soustava lin. rovnic, [[https://en.wikipedia.org/wiki/Cramer%27s_rule#Explicit_formulas_for_small_systems|Cramerovo pravidlo]] Jednoduchá aplikace [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=526&page=show_problem&problem=379|438 - The Circumference of the Circle]], [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=529&page=show_problem&problem=1276|10335 - Ray Inside a Polygon]] ** [[https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/| Poloha bodu a polygonu ]] ** **[[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:a4b36acm1:2020_zs:sweeplinexx.pdf | Touching rectangles}} **Sweep line rotates:**, http://www.spoj.com/problems/CERC07C/ (*_*_*) {{ :courses:a4b36acm1:2020_zs:spojcerc07c.pdf | 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 (ICPC Live Archive | Regionals 2017 | Europe-Northwestern)]], {{ :courses:a4b36acm1:2021_zs:glyphs.pdf | solution idea }} **Množství komentovaných základních kódů** https://www.geeksforgeeks.org/geometric-algorithms/ **Kreslítko GeoGebra online** https://www.geogebra.org/graphing?lang=en (http://www.geogebra.org/ ??) (začni variantou "classic"). **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ář 12 (8.12.) ===== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1pB0V6aoHI0g-mZ8qQIaZVw7NWQ7YiVP86OzzUGuXvvE/edit?usp=sharing|Výkony v minisoutěži V]],\\ po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz. //Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady "začínající" nezískají body.\\ Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady. // \\ **Sada začínající** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=763&page=show_problem&problem=419|478 - Points in Figures: Rectangles, Circles, Triangles]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=529&page=show_problem&problem=444|503 - Parallelepiped walk]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=759&page=show_problem&problem=1121|10180 - Rope Crisis in Ropeland!]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=212&page=show_problem&problem=1204|10263 - Railway]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=763&page=show_problem&problem=2037|11096 - Nails]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=758&page=show_problem&problem=2301|11326 - Laser Pointer]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=760&page=show_problem&problem=2320|11345 - Rectangles]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=763&page=show_problem&problem=2468|11473 - Campus Roads]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=758&page=show_problem&problem=2626|11579 - Triangle Trouble]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=760&page=show_problem&problem=2934|11834 - Elevator]] **Sada pro pokročilce** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=760&page=show_problem&problem=91|155 - All Squares]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=763&page=show_problem&problem=799|858 - Berry Picking]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=763&page=show_problem&problem=1053|10112 - Myacm Triangles]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=759&page=show_problem&problem=1224|10283 - The Kissing Circles]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=763&page=show_problem&problem=1347|10406 - Cutting tabletops]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=757&page=show_problem&problem=1407|10466 - How Far?]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=529&page=show_problem&problem=1497|10556 - Biometrics]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=763&page=show_problem&problem=1593|10652 - Board Wrapping]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=757&page=show_problem&problem=1773|10832 - Yoyodyne]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=763&page=show_problem&problem=2442|11447 - Reservoir logs]] ===== Seminář 13 (15.12.) Kombinatorické hry, Nim ===== * [[https://math.fel.cvut.cz/en/people/gollova/lgr/lgr_11a.pdf|Interní opáčko -- 18. přednáška z LGR]] * [[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://web.mit.edu/sp.268/www/2010/impartialGames.pdf|Přehled na MIT]] * [[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:a4b36acm1:2021_ls: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. ===== Seminář 14 (12.1.) ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1yt5B5aPgs9sLorgtwVT6Zq8cVZUEDM6VXG3m3jkcTBk/edit?usp=sharing|Výkony v minisoutěži VI]],\\ po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz. //Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady "začínající" nezískají body.\\ Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady. // \\ **Sada začínající** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=315&page=show_problem&problem=247|311 - Packets]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=226&page=show_problem&problem=2918|11818 - Game --- Mouse and Cheese]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=226&page=show_problem&problem=2999|11877 - The Coco-Cola Store]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=244&page=show_problem&problem=3711|12290 - Counting Game]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=861&page=show_problem&problem=4721|12856 - Counting substhreengs]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=866&page=show_problem&problem=4980|13082 - High School Assembly]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=878&page=show_problem&problem=5167|13244 - Space Happiness]] - [[https://www.spoj.com/problems/KMOVES/|KMOVES - Knight Moves]] - [[https://www.spoj.com/problems/QCJ3/|QCJ3 - The Game]] - [[https://www.spoj.com/problems/TFRIENDS/|TFRIENDS - True Friends]] **Sada pokročilá** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=200|264 - Count on Cantor]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=955|10014 - Simple calculations]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1323|10382 - Watering Grass]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1803|10862 - Connect the Cable Wires]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=244&page=show_problem&problem=3714|12293 - Box Game]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=866&page=show_problem&problem=4965|13067 - Prime Kebab Menu]] - [[https://www.spoj.com/problems/EQBOX/|EQBOX - Equipment Box]] - [[https://www.spoj.com/problems/GAME2/|GAME2 - Looks like Nim - but it is not]] - [[https://www.spoj.com/problems/MCOINS/|MCOINS - Coins Game]] - [[https://www.spoj.com/problems/MMMGAME/|MMMGAME - M&M Game]]