**Místo a čas konání** Místo: online prostor, čas: čtvrtek od 16:15. [[https://www.fel.cvut.cz/cz/education/rozvrhy-ng.B201/public/html/mistnosti/10/12/m10125804.html|Rozvrh FEL]] **Na druhý seminář (1.10.) použijte v brute vygenerovaný odkaz na BBB konferenci** [[https://cw.felk.cvut.cz/brute/student/bbb/cw_nUYiAZZosh|https://cw.felk.cvut.cz/brute/student/bbb/cw_nUYiAZZosh]] ===== Semináře ===== ==== Tabulka s průběžným stavem bodování ==== ^ Seminář ^ Datum \\ (hodiny) ^ Náplň ^ Úlohy/odkazy/prezentace \\ viz také pod tabulkou ^ | **1.** | **24.9** (2) | Servery, konta, ukázkové úlohy a témata, cvičná odevzdání, jednoduchá opakování | [[https://a2oj.com/register?ID=41235|Úlohy na A2OJ]] [[https://a2oj.com/standings?ID=41235| (Výsledky)]] \\ [[https://docs.google.com/spreadsheets/d/1v6KeMSCRm0MK7TuAbRimaD27pZ3ivNZ-v8DNGH5WG00/edit?usp=sharing|Zapište svoje vykony sem]] | | **2.** | **1.10** (4) | ** Minisoutěž I** - úlohy na informatický postřeh a zkušenost | Viz úlohy níže na této stránce | | **3.** | **8.10.** (2) | Dynamické programování I | | | **4.** | **15.10.** (4) | ** Minisoutěž II** | | | **5.** | **22.10.** (2) | Dynamické programování II | | | **6.** | **29.10.** (4) | ** Minisoutěž III** | | | **7.** | **5.11.** (2) | Cesty v grafech | | | **8.** | **12.11.** (4) | ** Minisoutěž IV** | | | **9.** | **19.11** (2) | Aritmetika a kombinatorika, teorie čísel | | | **10.** | **26.11.** (4) | ** Minisoutěž V** | | | **11.** | **3.12.** (2) | Výpočetní geometrie, mřížky | | | **12.** | **10.12.** (4) | ** Minisoutěž VI** | | | **13.** | **17.12.** (2) | Anatgonistické hry, Nim | | | **14.** | **7.1.** (4) | ** Minisoutěž VII** | | | **CELKEM** | ZS 2020 . . . . | **TABULKA - VÝSLEDKY ** | [[https://docs.google.com/spreadsheets/d/1tkd-6Urjr0fLFa45BUruLwqxKc1WECo_ieU-sV_1274/edit?usp=sharing| Celkový stav ]] | ---- ===== Seminář 1 ===== ==== Provoz a administrace ==== **Na první seminář použijte v brute vygenerovaný odkaz na BBB konferenci** [[https://cw.felk.cvut.cz/brute/student/bbb/cw_nUYiAZZosh|https://cw.felk.cvut.cz/brute/student/bbb/cw_nUYiAZZosh]] Rozhraní A2OJ nefungovalo, udělali jsme offline google tabulku s výkony jednotlivců, \\ pokud jste je ještě nezapsali, tak [[https://docs.google.com/spreadsheets/d/1v6KeMSCRm0MK7TuAbRimaD27pZ3ivNZ-v8DNGH5WG00/edit?usp=sharing|zapište svoje vykony sem]]. 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]] ---- === Ahmed Aly Online Judge === V průběhu praktických cvičení (sudé výukové týdny) svá řešení budete odevzdávat do **A2 Online Judge**. Prosíme, vytvořte si každý svůj vlastní účet sledováním následujícího linku: [[http://a2oj.com/signup|Sign Up]]. Vzhledem k tomu, že A2 Online Judge je pouze tzv. //agregátor výsledků//, musíte si vytvořit účty v příslušných judgích, které skutečně ověřují správnost vašich řešení, a to: [[http://www.spoj.com/register/|Sphere Online Judge]], [[https://uva.onlinejudge.org/index.php?option=com_comprofiler&task=registers|UVa Online Judge]] a [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_comprofiler&task=registers|ACM-ICPC Live Archive]]. \\ Aby A2OJ věděl o odevzdaných úlohách, musíte vyplnit ve svém profilu ID, které jste si vytvořili či vám bylo přiděleno u výše uvedených judgů. Zde je shrnut postup, jak se k nim dostat: === Sphere Online Judge (SPOJ) === - Neuvěřitelné, ale login je vaše ID. === UVA Online Judge === - V hlavním menu po přihlášení ťukněte na [My Account] - Ve vašem profilu na řádku **Online Judge ID:** je Vaše UVA ID. === ACM-ICPC Online Judge === * Odevzdejte libovolnou úlohu (klidně prázný soubor). * Přejděte na stránku **[[https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&Itemid=19|Live Archive: Posledních 50 Odevzdání]]** * Najděte řádku přislušící vaší odevzdané úloze a klikněte na své uživatelské jméno. * V parametrech URL naleznete své __userid__. === Test odevzdávacího systému === Po vytvoření účtů se můžete registrovat do soutěže na A2 Online Judge, klikněte na odkaz nahoře v prvním řádku tabulky. ---- ==== Úlohy pro první seminář ==== * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=98&page=show_problem&problem=235 | 299 - Train Swapping]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=101&page=show_problem&problem=520| 579 - Clock Hands]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=31&page=show_problem&problem=1073| 10132 - File Fragmentation]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=101&page=show_problem&problem=1328| 10387 - Billiard]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=456&page=show_problem&problem=2515| 11520 - Fill the Square]] * [[https://www.spoj.com/problems/AE00/| AE00 - Rectangles]] * [[https://www.spoj.com/problems/AE1B/| AE1B - Tables]] * [[https://www.spoj.com/problems/AMR10G/| AMR10G - Christmas Play]] * [[https://www.spoj.com/problems/BYTESE2/| BYTESE2 - The Great Ball]] * [[https://www.spoj.com/problems/SHP/ | SHP - Shuffling Problem]] * [[https://www.spoj.com/problems/TEST/|TEST - Life, the Universe, and Everythin ]] ===== Seminář 2 ===== **Online:** Připojte se do konference:[[https://cw.felk.cvut.cz/brute/student/bbb/cw_zvuhVQ3J5w|https://cw.felk.cvut.cz/brute/student/bbb/cw_zvuhVQ3J5w]] ==== Úlohy pro druhý seminář ==== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1dd9AxhDcOCaDTvt3g5HrwnctsS8KAUCscopzvuERKAo/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. Vyberte si sadu podle svého zaměření, můžete také mixovat úlohy z obou sad: **Sada pro začínající** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=457&page=show_problem&problem=56|120 - Stacks of Flapjacks]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=190|189 - Mobile Casanova]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2091|11150 - Cola]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=513&page=show_problem&problem=2619|11572 - Unique Snowflakes]] - [[https://www.spoj.com/problems/ATOMS/|ATOMS - Atoms in the Lab]] - [[https://www.spoj.com/problems/BUSYMAN/|BUSYMAN - I AM VERY BUSY]] - [[https://www.spoj.com/problems/CRAN02/|CRAN02 - Roommate Agreement]] - [[https://www.spoj.com/problems/EXPEDI/|EXPEDI - Expedition]] - [[https://www.spoj.com/problems/FCTRL/|FCTRL - Factorial]] - [[https://www.spoj.com/problems/GOO/|GOO - Game Of Ones]] **Sada pro pokročilce** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=512&page=show_problem&problem=243|307 - Sticks]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=457&page=show_problem&problem=190|254 - Towers of Hanoi]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=457&page=show_problem&problem=953|10012 - How Big Is It?]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=990|10049 - Self-describing Sequence]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=457&page=show_problem&problem=1980|11039 - Building designing]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1020|10079 - Pizza Cutting]] - [[https://www.spoj.com/problems/ABCD/|ABCD - Colours A, B, C, D]] - [[https://www.spoj.com/problems/AGGRCOW/|AGGRCOW - Aggressive cows]] - [[https://www.spoj.com/problems/BTCK/|BTCK - A problem of Backtracking]] - [[https://www.spoj.com/problems/SNGINT/SNGINT - Encode Integer]] ===== Seminář 3 ===== **Online1:** Připojte se do konference: [[https://cw.felk.cvut.cz/brute/bbb.php?join=cw_pc9e6Bo1az|https://cw.felk.cvut.cz/brute/bbb.php?join=cw_pc9e6Bo1az]] **Online2:** Pokud by se nedařilo v Online1, v brute je na 16:10 naplánována záložní konference v předmětu ACM_ALL (pozor, nikoli ACM1 - ACM5). Brute mi hlásí, že odmítá posílat pozvánku komukoli na tuto konferenci v době jejího začátku (??). Zkuste adresu [[https://cw.felk.cvut.cz/brute/student/bbb/cw_7JCHpDhqMS|https://cw.felk.cvut.cz/brute/student/bbb/cw_7JCHpDhqMS]]. 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]] ===== Seminář 4 Dynamické programování ===== **Online:** Připojte se do konference:[[ https://cw.felk.cvut.cz/brute/student/bbb/cw_iiBLJ6px5n| https://cw.felk.cvut.cz/brute/student/bbb/cw_iiBLJ6px5n]] Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1V3_VM2sT6wR2QiVrc3DWf-X6-isD3_5GLM5_B3GBGpA/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. Vyberte si sadu podle svého zaměření, můžete také mixovat úlohy z obou sad: **Sada pro začínající** - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=83|147 - Dollars]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=655&page=show_problem&problem=977|10036 - Divisibility]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=653&page=show_problem&problem=1254|10313 - Pay the Price]] - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1662| 10721- Bar codes ]] - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1853| 10912 - Simple Minded Hashing]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=655&page=show_problem&problem=1884|10943 - How do you add?]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=653&page=show_problem&problem=2078|11137 - Ingenuous Cubrency]] - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2181|11240 - Antimonotonicity]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=655&page=show_problem&problem=2402|11407 - Squares]] - [[http://www.spoj.com/problems/SQRBR/|SQRBR - Square Brackets]] **Sada pro pokročilce** - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=167|231 - Testing the CATCHER]] - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=823|882 - The Mailbox Manufacturers]] - [[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=1500|10559 - Blocks ]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=655&page=show_problem&problem=1851 |10910 - Marks Distribution]] - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1854|10913 - Walking on a Grid]] - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=142&page=show_problem&problem=1944|11003 - Boxes ]] - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2701|11654 - Arithmetic Subsequence]] - [[https://www.spoj.com/problems/ANARC07G/| ANARC07G - Let go to the movies]] - [[https://www.spoj.com/problems/PT07X/| PT07X - Vertex Cover]] ===== Seminář 5 Dynamické programování II ===== Spojen výjimečně s následujícím seminářem. A jinak: * 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 * Ú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/ * {{ :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 }} * {{ :courses:a4b36acm1:2020_zs:vodavrourach.pdf | Voda v rourach }} ===== Seminář 6 Dynamické programování II s minisoutěží ===== ==== Úlohy ==== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1nVZwbe5dW7WncBg8DHrczNZq0LkJnUGrBvieu7DGRA0/edit?usp=sharing|Výkony v minisoutěži III]], Kvůli časovému posunu bude 3 body hodnocena každá úloha odevzdaná do večera (23.59.) pátku 30.10: Posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz. Vyberte si sadu podle svého zaměření, můžete také mixovat úlohy z obou sad: **Sada pro začínající** - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1202|10261 - Ferry Loading]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1221|10280 - Old Wine Into New Bottles]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1567|10626 - Buying Coke]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2010|11069 - A Graph Problem]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2225|11258 - String Partition]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2616|11569 - Lovely Hint]] - [[https://www.spoj.com/problems/BYTESM2/|BYTESM2 - Philosophers Stone]] - [[https://www.spoj.com/problems/FOODIE/|FOODIE - FOODIE]] - [[https://www.spoj.com/problems/PIGBANK/|PIGBANK - Piggy-Bank]] - [[https://www.spoj.com/problems/SQRBR/|SQRBR - Square Brackets]] **Sada pro pokročilce** - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=780|839 - Not so Mobile]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=936|995 - Super Divisible Numbers]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2022|11081 - Strings]] - [[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=onlinejudge&page=show_problem&problem=2738|11691 - Allergy Test]] - [[https://www.spoj.com/problems/AE2A/|AE2A - Dice]] - [[https://www.spoj.com/problems/ABA12C/|ABA12C - Buying Apples!]] - [[https://www.spoj.com/problems/GNYR09F/|GNYR09F - Adjacent Bit Counts]] - [[https://www.spoj.com/problems/JEDNAKOS/|JEDNAKOS - JEDNAKOST]] - [[https://www.spoj.com/problems/MENU/|MENU - Menu]] ===== Seminář 7 Grafy a nejkratší cesty ===== 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 }} {{ :courses:a4b36acm1:2020_zs:dijkstra_n_2.pdf |Dijkstra v O(n^2) }} 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]] * [[https://www.cs.usfca.edu/~galles/visualization/Floyd.html|Floyd-Warshall algorithm example]] [[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html|další vizualizace]] ===== Seminář 8 Prohledávání grafů s minisoutěží ===== ==== Úlohy ==== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1SWmu19AamYDwhJLzm26lxRjinio2cQvNe2Kmf3GhQj4/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. Vyberte si sadu podle svého zaměření, můžete také mixovat úlohy z obou sad: **Sada pro začínající** - [[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=7&page=show_problem&problem=513|572 - Oil Deposits]] - [[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=694&page=show_problem&problem=1142|10201 - Adventures in Moving - Part IV]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1200|10259 - Hippity Hopscotch]] - [[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=25&page=show_problem&problem=2306|11331 - The Joys of Farming]] - [[https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&category=546&page=show_problem&problem=2391|11396 - Claw Decomposition]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2620|11573 - Ocean Currents]] - [[https://www.spoj.com/problems/LABYR1/|LABYR1 - Labyrinth]] **Sada pro pokročilce** - [[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ář 9 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 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ář 10 Aritmetika, kombinatorika a čísla ===== ==== Úlohy ==== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1Fy40SrXRyj4UOSRcaSL5aVp9RV3d7a2NN1_izRSa01o/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. Vyberte si sadu podle svého zaměření, můžete také mixovat úlohy z obou sad: **Sada pro 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://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=416&page=show_problem&problem=2366|11371 - Number Theory for Newbies]] - [[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]] **Sada pro pokročilce** - [[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=474&page=show_problem&problem=1068|10127 - Ones]] - [[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]] ===== Seminář 11: 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: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]], {{ :courses:a4b36acm1:2020_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/ ??) **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 Geometrie ===== ==== Úlohy ==== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1OXI4t7EzqyviU3MzzvK6qHTUhUidsQAgVHsWe50y1kw/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. Vyberte si sadu podle svého zaměření, můžete také mixovat úlohy z obou sad: **Sada pro začínající** * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=214&page=show_problem&problem=379|438 - The Circumference of the Circle]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=218&page=show_problem&problem=1238|10297 - Beavergnaw]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=337&page=show_problem&problem=1347|10406 - Cutting tabletops]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=213&page=show_problem&problem=1392|10451 - Ancient Village Sports]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=212&page=show_problem&problem=2009|11068 - An Easy Task]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=214&page=show_problem&problem=2093|11152 - Colourful Flowers]] * [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2173|11232 - Cylinder]] * [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2340|11355 - Cool Points]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=217&page=show_problem&problem=2468|11473 - Campus Roads]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=214&page=show_problem&problem=2474|11479 - Is this the easiest problem?]] **Sada pro pokročilce** * [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=249|313 - Intervals]] * [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=752|811 - The Fortified Forest]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=221&page=show_problem&problem=861|920 - Sunny Mountains]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=213&page=show_problem&problem=946|10005 - Packing polygons]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=213&page=show_problem&problem=953|10012 - How Big Is It?]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=217&page=show_problem&problem=1053|10112 - Myacm Triangles]] * [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1632|10691 - Subway]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=221&page=show_problem&problem=2318|11343 - Isolated Segments]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=218&page=show_problem&problem=2502|11507 - Bender B. Rodríguez Problem]] * [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2896|11796 - Dog Distance]] ===== Seminář 13 - Kombinatoricke hry ===== * [[https://math.fel.cvut.cz/gollova/lgr/lgr_11.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: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. * ===== Seminář 14 Závěr semestru ===== ==== Úlohy ==== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1Ly9ClBTbv1YNTz0HLcEDWzfU-WvcsxY4BajPjtLHnEo/edit?usp=sharing|Výkony v minisoutěži VII]], 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. Tentokrát jen jediná sada, s nejrůznějšími náměty : - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=41|105 - The Skyline Problem]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=60|124 - Following Orders]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=103|167 - The Sultan's Successors]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=145|209 - Triangular Vertices]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=702&page=show_problem&problem=200|264 - Count on Cantor]] - [[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=788|847 - A Multiplication Game]] - [[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=315&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&page=show_problem&problem=2614|11567 - Moliu Number Generator]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=226&page=show_problem&problem=2918|11818 - Game --- Mouse and Cheese]] - [[https://www.spoj.com/problems/CHICAGO/|CHICAGO - 106 miles to Chicago]] - [[https://www.spoj.com/problems/EIGHTS/|EIGHTS - Triple Fat Ladies]] - [[https://www.spoj.com/problems/PA06ANT/|PA06ANT - Ant]] - [[https://www.spoj.com/problems/RRSCHED/|RRSCHED - Round-Robin Scheduling]]