===== Semináře ACM ===== **Místo a čas konání** Místo: T2:C2-84, čas: čtvrtek od 16:15. [[https://intranet.fel.cvut.cz/cz/education/rozvrhy-ng.B222/public/html/mistnosti/10/12/m10125804.html|Rozvrh FEL]] [[https://docs.google.com/spreadsheets/d/1bFq4EznwOj6YAqjcRPhCueLSYh8_oTW76lu9fNpOZTk/edit?usp=sharing| TABULKA -- Celkový stav ]] ^ Seminář ^ Datum \\ (hodiny) ^ Náplň ^ | **1.** | **22.2.** (4) | Uvod, seznameni se servery, vybrane ulohy, Minisoutěž I | | **2.** | **29.2.** (2) | Dynamické programování (DP) | | **3.** | **7.3.** (4) | ** Minisoutěž II** | | **4.** | **14.3.** (2) | Cesty v grafech | | **5.** | **21.3.** (4) | ** Minisoutěž III** | | **6.** | **28.3.** (2) | Aritmetika a kombinatorika, teorie čísel | | **7.** | **4.4.** (4) | ** Minisoutěž IV** | | **8.** | **11.4.** (2) | Výpočetní geometrie, mřížky | | **9.** | **18.4** (4) | ** Minisoutěž VI** | | **10.** | **25.4.** (2) | Anatgonistické hry, Nim | | **11.** | **2.5.** (4) | ** Minisoutěž V** | | **12.** | **9.5.** (2) | //odpadá, je středa// | | **13.** | **16.5.** (4) | ** Minisoutěž VII** | | **14.** | **23.5.** (2) | Shrnutí, dodělávky | | **CELKEM** | LS2024 . **VÝSLEDKY ** | [[https://docs.google.com/spreadsheets/d/1bFq4EznwOj6YAqjcRPhCueLSYh8_oTW76lu9fNpOZTk/edit?usp=sharing| TABULKA -- Celkový stav ]] | ---- ===== Seminář 01 (22.2.) ===== ==== 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ěží) (aktuálně neaktivní -- uvidíme, zda se rozběhne) 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í ]] ==== Úlohy pro první seminář ==== ** 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/1DQgMQtfBRNnYExmLDVjxKhqBqUsWPDdqyvA1kUbMiDw/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. **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=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=3&page=show_problem&problem=57|121 - Pipe Fitters]] - [[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=onlinejudge&Itemid=8&page=show_problem&problem=1724|10783 - Odd Sum]] - [[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/BUSYMAN/|BUSYMAN - I AM VERY BUSY]] - [[https://www.spoj.com/problems/GERGOVIA/|GERGOVIA - Wine trading in Gergovia]] - [[https://www.spoj.com/problems/HOTELS/|HOTELS - Hotels Along the Croatian Coast]] - [[https://www.spoj.com/problems/PERMUT2/|PERMUT2 - Ambiguous Permutations]] - [[https://www.spoj.com/problems/SHP/|SHP - Shuffling Problem]] **pokročilí nebo začínající zkusí** - [[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=onlinejudge&page=show_problem&problem=990|10049 - Self-describing Sequence]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2619|11572 - Unique Snowflakes]] - [[https://www.spoj.com/problems/AE1B/|AE1B - Tables]] - [[https://www.spoj.com/problems/AGGRCOW/|AGGRCOW - Aggressive cows]] - [[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/HANGOVER/|HANGOVER - Hangover]] - [[https://www.spoj.com/problems/RRSCHED/|RRSCHED - Round-Robin Scheduling]] ===== Seminář 02 (29.2.) Dynamické programování ===== Komentáře k minulým úlohám. Ukázky typických postupů a úloh. Doporučené úvodní přehledové a úctyhodné publikace, asi nejpřístupněji napsané: * [[https://cses.fi/book/book.pdf |Laaksonen: Competitive Programmer’s Handbook]] * [[http://pruvodce.ucw.cz/|Mareš, Valla: Průvodce labyrintem algoritmů]] Jednotlivé metody: * {{ :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/a4b36acm/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 * Ú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 }} **Úlohy pro rozmyšlení** [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=83|147 - Dollars]] (2D Tab)\\ [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1007|10066 - The Twin Towers]] (LCS)\\ [[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/PT07X/|PT07X - Vertex Cover]] \\ [[http://www.spoj.com/problems/M3TILE/|M3TILE - LATGACH3]] \\ [[http://www.spoj.com/problems/SQRBR/|SQRBR - Square Brackets]] \\ [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=847&page=show_problem&problem=52|116 - Unidirectional TSP]] \\ [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=143&page=show_problem&problem=2078|11137 - Ingenuous Cubrency]] https://www.geeksforgeeks.org/painting-fence-algorithm/ https://leetcode.com/problems/perfect-squares/ ===== Seminář 03 (7.3.) ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1kv2MJojZ-yomKNqoAx9sR7QfEoierADU0c7PsGjC5fw/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. // \\ **Začínající zkusí** - [[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=114&page=show_problem&problem=766 |825 - Walking on the Safe Side]] - [[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=15&page=show_problem&problem=1275|10334 - Ray Through Glasses]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=1505|10564 - Paths through the Hourglass]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=1540 |10599 - Robots(II)]] - [[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=655&page=show_problem&problem=2402|11407 - Squares]] - [[https://www.spoj.com/problems/BYTESM2/ |BYTESM2 - Philosophers Stone]] - [[https://www.spoj.com/problems/DIEHARD/ |DIEHARD - DIE HARD]] **pokročilí nebo začínající zkusí** - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=780|839 - Not so Mobile]] - [[http://uva.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=655&page=show_problem&problem=977|10036 - Divisibility]] - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1500|10559 - Blocks ]] - [[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/ABA12C/|ABA12C - Buying Apples!]] - [[https://www.spoj.com/problems/AE2A/|AE2A - Dice]] - [[https://www.spoj.com/problems/MENU/|MENU - Menu]] ===== Seminář 4 (14.3.) Cesty v grafech ===== ==== Fundamenty ==== 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 }} (Prakticky jde o DP.) {{ :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ář 05 (21.3.) ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/11HXgRYY00L2R81-N4CcZxCcw5br0GUmziYJ4wimYqnw/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. // \\ **Začínající zkusí** - [[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=854&page=show_problem&problem=762| 821 - Page Hopping]] - [[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=onlinejudge&Itemid=8&category=546&page=show_problem&problem=2391|11396 - Claw Decomposition]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=4027|12582 - Wedding of Sultan]] - [[https://www.spoj.com/problems/ACPC10D/|ACPC10D - Tri graphs]] - [[https://www.spoj.com/problems/ALLIZWEL/|ALL IZZ WELL]] - [[https://www.spoj.com/problems/BENEFACT/|BENEFACT - The Benefactor]] - [[https://www.spoj.com/problems/BITMAP/|BITMAP - Bitmap]] - [[https://www.spoj.com/problems/ELEVTRBL/|ELEVTRBL - Elevator Trouble]] **pokročilí nebo začínající zkusí** - [[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=683&page=show_problem&problem=3639|1198 - The Geodetic Set Problem]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=679&page=show_problem&problem=2933|11833 - Route Change]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=853&page=show_problem&problem=4399|12661 - Funny Car Racing]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2733|11686 - Pick up sticks]] - [[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/CAM5/|CAM5 - prayatna PR]] - [[https://www.spoj.com/problems/CERC07K/|CERC07K - Key Task]] - [[https://www.spoj.com/problems/SAMER08A/|SAMER08A - Almost Shortest Path]] - [[https://www.spoj.com/problems/WATER/|WATER - Water among Cubes]] ===== Seminář 06 ( 28.3.) 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ář 07 (4.4.) ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1XV59tcSO0NQS9NXk8seZ9Ctd8NUdQ3YdbAL1CDPjsT4/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. // \\ **Začínající zkusí** - [[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=onlinejudge&page=show_problem&problem=934|993 - Product of digits]] - [[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=188&page=show_problem&problem=1474|10533 - Digit Primes]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=189&page=show_problem&problem=2383|11388 - GCD LCM]] - [[https://www.spoj.com/problems/BALLSUM/|BALLSUM - Ball sum]] - [[https://www.spoj.com/problems/GUANGGUN/|GUANGGUN - 111…1 Squared]] - [[https://www.spoj.com/problems/MARBLES/|MARBLES - Marbles]] - [[https://www.spoj.com/problems/MB1/|MB1 - PP numbers]] - [[https://www.spoj.com/problems/UCV2013A/|UCV2013A - Counting Ids]] **pokročilí nebo začínající zkusí** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=279|343 - What Base Is This?]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=825|884 - Factorial Factors]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=720&page=show_problem&problem=855|914 - Jumping Champion]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1761|10820 - Send a Table]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2271|11296 - Counting Solutions to an Integral Equation]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2322|11347 - Multifactorials]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2656|11609 - Teams]] - [[https://www.spoj.com/problems/BINSTIRL/|BINSTIRL - Binary Stirling Numbers]] - [[https://www.spoj.com/problems/SUMMATION/|SUMMATION - SUMMATION]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=470&page=show_problem&problem=1979|11038 - How Many O's?]] (náhrada za nefunkční ZCR níže) - [[https://www.spoj.com/problems/ZCR/|ZCR - Zen And His Crush]] (vyhodnocení nefunguje, řešení pošlete na berezovs@fel.cvut.cz) ===== Seminář 08 (11.4.) Výpočetní geometrie, mřížky ===== Determinant matice, většinou stačí 2×2. **{{ :courses:a4b36acm1:2024_zs:geombas1upd2.pptx |Některé základní výpočty }} ** {{ :courses:a4b36acm1:2024_zs:geombas1upd2.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 ]] ** (Hack: místo paprsku může postačit dostatečně dlouhá úsečka) **[[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/classic (http://www.geogebra.org/ ??) (začni variantou "classic"). **Zkuste samostatně:** [[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=759&page=show_problem&problem=1121|10180 - Rope Crisis in Ropeland!]] ===== Seminář 09 (18.4.) ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1Ck9aIjt3HrzeWmnO2P7XWmUpf5-oLWujqUazKgR-mT8/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. // \\ **Začínající zkusí** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=212&page=show_problem&problem=120|184 - Laser Lines]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=678|737 - Gleaming the Cubes ]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1001|10060 - A hole to catch a man]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1019|10078 - The Art Gallery]] - [[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=onlinejudge&page=show_problem&problem=2148|11207 - The easiest way]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2173|11232 - Cylinder]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=760&page=show_problem&problem=2934|11834 - Elevator]] - [[https://www.spoj.com/problems/EQBOX/|EQBOX - Equipment Box]] - [[https://www.spoj.com/problems/VMILI/|VMILI - Military Story]] **pokročilí nebo začínající zkusí** - [[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=17&page=show_problem&problem=1518|10577 - Bounding box]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1526|10585 - Center of symmetry]] - [[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=221&page=show_problem&problem=2318|11343 - Isolated Segments]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=217&page=show_problem&problem=2468|11473 - Campus Roads]] - [[https://www.spoj.com/problems/ADAPICK/|ADAPICK - Ada and Cucumber ]] - [[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]] ===== Seminář 10 (25.4.) 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]] * Zkuste si nim online: [[https://education.jlab.org/nim/|Jefferson Lab]], [[https://www.archimedes-lab.org/game_nim/play_nim_game.html|Archimedes Lab]] 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]] * [[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ář 11 (2.5.) ===== **Rozhodněte o plánu na poslední dva semináře v tomto semestru: [[https://forms.gle/yDy5fYWuD1wqC6E69| Přehodit nebo nepřehodit 13.a 14. týden?]] ** === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1Pakai4__967vor1vOI3YaMkX6t5OiP90E8pRozatIas/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. // \\ **Začínající zkusí** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=315&page=show_problem&problem=1704|10763 - Foreign Exchange]] - [[http://www.spoj.com/problems/CATM/|CATM - The Cats and the Mouse]] - [[https://www.spoj.com/problems/DOTAA/|DOTAA - DOTA HEROES]] - [[https://www.spoj.com/problems/EIGHTS/|EIGHTS - Triple Fat Ladies]] - [[https://www.spoj.com/problems/GAMES/|GAMES - How Many Games?]] - [[https://www.spoj.com/problems/HCT00001/|HCT00001 - Interesting Game with Polygons]] - [[https://www.spoj.com/problems/MMMGAME/|MMMGAME - M&M Game]] - [[https://www.spoj.com/problems/NITK06/|NITK06 - MODIFY SEQUENCE]] - [[https://www.spoj.com/problems/PLAYGAME/|PLAYGAME - PLAYGAME]] - [[https://www.spoj.com/problems/VECTAR10/|VECTAR10 - Card Game]] **pokročilí nebo začínající zkusí** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=214|278 - Chess]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=9&page=show_problem&problem=691|750 - 8 Queens Chess Problem]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=965|10024 - Curling up the cube]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2136|11195 - Another n-Queen Problem]] - [[https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&category=230&page=show_problem&problem=3108|11957 - Checkers]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=244&page=show_problem&problem=3714|12293 - Box Game]] - [[https://www.spoj.com/problems/CF36D/|CF36D - New Game with a Chess Piece]] - [[https://www.spoj.com/problems/GOIT/|GOIT - Game of Iron Thrones]] - [[https://www.spoj.com/problems/NOTATRI/|NOTATRI - Not a Triangle]] - [[https://www.spoj.com/problems/SHAKTI/|SHAKTI - SHAKTIMAN AND KILWISH]]