**Místo a čas konání** Místo: T2:C2-84, čas: čtvrtek od 16:15. [[https://fel.cvut.cz/cz/education/rozvrhy-ng.B212/public/html/mistnosti/10/12/m10125804.html|Rozvrh FEL]] ===== Semináře ===== ==== Tabulka s průběžným stavem ==== ^ Seminář ^ Datum \\ (hodiny) ^ Náplň ^ | **1.** | **17.2** (2) | Snadné počítání a příprava na dynamické programování | | **2.** | **24.2** (4) | ** Minisoutěž I** | | **3.** | **3.3.** (2) | Dynamické programování (DP) | | **4.** | **10.3.** (4) | ** Minisoutěž II** | | **5.** | **17.3.** (2) | Cesty v grafech | | **6.** | **24.3.** (4) | ** Minisoutěž III** | | **7.** | **31.3.** (2) | Aritmetika a kombinatorika, teorie čísel | | **8.** | **7.4.** (4) | ** Minisoutěž IV** | | **9.** | **14.4** (2) | Výpočetní geometrie, mřížky | | **10.** | **21.4.** (4) | ** Minisoutěž V** - | | **11.** | **28.4.** (2) | Anatgonistické hry, Nim | | **12.** | **5.5.** (4) | ** Minisoutěž VI** | | **13.** | **12.5.** (2) | Opakování DP, grafů a aritmetiky | | **14.** | **19.5.** (4) | ** Minisoutěž VII** opakování DP, grafů a aritmetiky | | **CELKEM** | LS2022 . **VÝSLEDKY ** | TABULKA - [[https://docs.google.com/spreadsheets/d/1ACpo3qMZx-lrdJEtuCtFv73nRrmMZZsqU_jW11FhWQs/edit?usp=sharing| Celkový stav ]] | ---- ==== Seminář 01. (17.2.) Běžné počítání a příprava na DP ==== Komentáře k úlohám na [[https://projecteuler.net/|Project Euler]]. * [[https://projecteuler.net/problem=28|Number spiral diagonals]] * [[https://projecteuler.net/problem=81|Path sum: two ways]] * [[https://projecteuler.net/problem=67|Maximum path sum II]] * [[https://projecteuler.net/problem=114|Counting block combinations I]] * [[https://projecteuler.net/problem=115|Counting block combinations II]] * [[https://projecteuler.net/problem=116|Red, green or blue tiles]] * [[https://projecteuler.net/problem=117|Red, green, and blue tiles]] * [[https://projecteuler.net/problem=191|Prize Strings]] **Vyzkoušejte si:** [[https://projecteuler.net/problem=112|Bouncy numbers]] \\ [[https://projecteuler.net/problem=158|Exploring strings for which only one character comes lexicographically after its neighbour to the left]]\\ [[https://projecteuler.net/problem=31|Coin sums]] **Pro pokročílé:** Vykoušejte níže některou Vámi nedodělanou úlohu, vloni nebo vůbec. Vyřešená úloha do 18:00 bude bodována standardnímí 3 body. - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=142&page=show_problem&problem=47|111 - History Grading]] - [[https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&category=144&page=show_problem&problem=503|562 - Dividing coins]] - [[https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&category=144&page=show_problem&problem=1071|10130 - SuperSale]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1072|10131 - Is Bigger Smarter?]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1142|10201 - Adventures in Moving - Part IV]] - [[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=21&page=show_problem&problem=1854|10913 - Walking on a Grid]] - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2591|11555 - Aspen Avenue]] - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=117&page=show_problem&problem=2882|11782 - Optimal Cut]] - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=117&page=show_problem&problem=2890|11790 - Murcia's Skyline]] ===== Seminář 02 (25.2.) ===== \\ === Servery === 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. \\ === Proces odevzdávání úloh === [[https://cw.fel.cvut.cz/wiki/courses/a4b36acm1/intro_basic|Proces lze vyzkoušet s hotovým řešením]]\\ [[https://cw.fel.cvut.cz/wiki/courses/a4b36acm1/trenink#jak_na_reseni| Přidané upřesňující poznámky ]] \\ === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/17Prs1B-qKjLvUkcjrZfDQBZM2sOnH93Ym0rynMmGq9Q/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. // \\ V této sadě je polovina úloh na dynamické programování, ostatní slouží jako rozcvičkové ad hoc úlohy s různorodými metodami řešení. - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=94&page=show_problem&problem=431|490 - Rotating Sentences]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=99&page=show_problem&problem=787|846 - Steps]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=766|825 - Walking on the Safe Side]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2533|11538 - Chess Queen]] - [[https://www.spoj.com/problems/CPTTRN7/|CPTTRN7 - Character Patterns (Act 7)]] - [[https://www.spoj.com/problems/HOTELS/|HOTELS - Hotels Along the Croatian Coast]] - [[https://www.spoj.com/problems/NFURY/|NFURY - Training Land of Fury]] - [[https://www.spoj.com/problems/NY10E/|NY10E - Non-Decreasing Digits]] - [[https://www.spoj.com/problems/SUMITR/|SUMITR - Sums in a Triangle]] - [[https://www.spoj.com/problems/TRAVERSE/|TRAVERSE - Traverse through the board]] **Sada pokročilá** - [[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=94&page=show_problem&problem=1012|10071 - Back to High School Physics]] - [[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=18&page=show_problem&problem=1583|10642 - Can You Solve It?]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1663|10722 - Super Lucky Numbers]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1859|10918 - Tri Tiling]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2173|11232 - Cylinder]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2692|11645 - Bits]] - [[https://www.spoj.com/problems/BABTWR/|BABTWR - Tower of Babylon]] - [[https://www.spoj.com/problems/CPCRC1C/|CPCRC1C - Sum of Digits]] ---- ===== Seminář 03 (3.3.) Dynamické programování ===== komntáře k minulým úlohám, pozor na log2(2^63-1), není to nutně menší než 63. 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 }} ===== Seminář 04 (10.3.) ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1bgIs4bEpnUMm-FUwwfF_QL24OBJhC9i7HMpfwEDFxgw/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. **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. // \\ V této sadě je část úloh na dynamické programování, ostatní slouží jako rozcvičkové ad hoc úlohy s různorodými metodami řešení. - [[https://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=12&page=show_problem&problem=961|10020 - Minimal coverage]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=653&page=show_problem&problem=2078|11137 - Ingenuous Cubrency]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=655&page=show_problem&problem=2402|11407 - Squares]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2486|11491 - Erasing and Winning]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=441&page=show_problem&problem=3990|12545 - Bits Equalizer]] - [[https://www.spoj.com/problems/AMR10G/|AMR10G - Christmas Play]] - [[https://www.spoj.com/problems/GERGOVIA/|GERGOVIA - Wine trading in Gergovia]] - [[https://www.spoj.com/problems/MISERMAN/|MISERMAN - Wise And Miser]] - [[https://www.spoj.com/problems/SQRBR/|SQRBR - Square Brackets]] **Sada pokročilá** Také v této sadě nejsou všechny úlohy na dynamické programování (DP), některé lze řešit i bez DP. - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=167|231 - Testing the CATCHER]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1662|10721 - Bar Codes]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=655&page=show_problem&problem=1851|10910 - Marks Distribution]] - [[https://www.spoj.com/problems/ACODE/|ACODE - Alphacode]] - [[https://www.spoj.com/problems/CANDY/|CANDY - Candy I]] - [[https://www.spoj.com/problems/DCEPC501/|DCEPC501 - Save Thy Toys]] - [[https://www.spoj.com/problems/MAXWOODS/|MAXWOODS - MAXIMUM WOOD CUTTER]] - [[https://www.spoj.com/problems/RAONE/|RAONE - Ra-One Numbers]] - [[https://www.spoj.com/problems/ROCK/|ROCK - Sweet and Sour Rock]] - [[https://www.spoj.com/problems/WACHOVIA/|WACHOVIA - Wachovia Bank]] ===== Seminář 05 (17.3.) Cesty v grafech ===== ==== 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 }} [[https://www.youtube.com/watch?v=NUgMa5coCoE|Ukázka BFS za běhu]] __ Porovnej s ukázkou DFS níže {{ :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://cw.fel.cvut.cz/wiki/courses/a4b36acm1/2022_ls/code|DFS snadný kód]] * [[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]] Tok v síti a maximální párování: * [[https://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/?ref=gcse| Tok v síti]] * [[https://www.geeksforgeeks.org/maximum-bipartite-matching/|Tok v síti a maximální párován]] * [[https://algorithms.tutorialhorizon.com/maximum-bipartite-matching-problem/| totéž na tutorialhorizon ]] Různé vizualizace na USFCA * [[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ář 06 (24.3.) ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/166pTT85xUA9O6CaQ07Sd-Ms-ycSEHbo6NwMdXtr8Ick/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. **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. // \\ - [[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=175&page=show_problem&problem=556|615 - Is It A Tree?]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=175&page=show_problem&problem=640|699 - The Falling Leaves]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1351|10410 - Tree Reconstruction]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=164&page=show_problem&problem=1742|10801 - Lift Hopping]] - [[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=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2513|11518 - Dominos 2]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2671|11624 - Fire!]] - [[https://www.spoj.com/problems/ELEVTRBL/|ELEVTRBL - Elevator Trouble]] - [[https://www.spoj.com/problems/EPIC1304/|EPIC1304 - Graph Cycle Detection]] **Sada pokročilá** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=165&page=show_problem&problem=499|558 - Wormholes]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=9&page=show_problem&problem=737|796 - Critical Links]] - [[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=12&page=show_problem&problem=988|10047 - The Monocycle]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=547&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=1642|10701 - Pre, in and post]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=152&page=show_problem&problem=1867|10926 - How Many Dependencies?]] - [[https://onlinejudge.org/index.php?option=com_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]] ===== Seminář 07 (31.3.) Aritmetika a kombinatorika ===== * [[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 }} * [[https://en.wikipedia.org/wiki/Modular_arithmetic|Modulární aritmetika]] (Převážně stejná jako ta běžná) ([[https://math.fel.cvut.cz/cz/lide/habala/teaching/dma/dmknih07.pdf|+Habala]]) * [[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 Vyzkoušejte si: * http://www.spoj.com/problems/AMR11E/ (4) * http://www.spoj.com/problems/APS/ (2) * https://www.spoj.com/problems/PTIME/ (3) * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2403|11408 - Count DePrimes]] (1) **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ář 08 ( 7.4.) ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1e_W9zYbvx5irLphjrcSvUHBgYKE9uOYeZxiHiS-aGe8/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. **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. // \\ - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=192&page=show_problem&problem=310|374 - Big Mod]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=200&page=show_problem&problem=903|962 - Taxicab Numbers]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=200&page=show_problem&problem=1532|10591 - Happy Number]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=474&page=show_problem&problem=1563|10622 - Perfect P-th Powers]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1640|10699 Count the factor]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1674|10733 The Colored Cube]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=162&page=show_problem&problem=2423|11428 - Cubes]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2533|11538 - Chess Queen]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2549|11554 - Hapless Hedonism]] - [[https://www.spoj.com/problems/BREAKING/|BREAKING - Number Breaking]] **Sada pokročilá** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=49|113 - Power of Cryptography]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=474&page=show_problem&problem=1002|10061 - How many zero's and how many digits ?]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1051|10110 Light, more ligh ]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=850&page=show_problem&problem=1761|10820 - Send a Table]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=470&page=show_problem&problem=1979|11038 - How Many O's?]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=516&page=show_problem&problem=2868|11768 - Lattice Point or Not]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=469&page=show_problem&problem=2906|11806 - Cheerleaders]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=515&page=show_problem&problem=3185|12034 - Race]] - [[https://www.spoj.com/problems/CANTON/|CANTON - Count on Cantor]] - [[https://www.spoj.com/problems/FIBOSUM/|FIBOSUM - Fibonacci Sum]] ===== Seminář 09 (14.4.) Geometrie ===== 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]] ** [[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ář }} ** Konvexní obal** **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/ ??) **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ář 10 ( 21.4.) ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/16c-z0z5o0MCEFfzrHsfJYUOQYaerMwCXy4m0MdfZKN8/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. **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. // \\ - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=212&page=show_problem&problem=120|184 - Laser Lines]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=532&page=show_problem&problem=3799|5788 - Wally World]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=533&page=show_problem&problem=3817|5806 - Rancher's Gift]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=534&page=show_problem&problem=3960|5949 - Line of Sight]] - [[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=213&page=show_problem&problem=1373|10432 - Polygon Inside A Circle]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2173|11232 - Cylinder]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2256|11281 - Triangular Pegs in Round Holes]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=219&page=show_problem&problem=2673|11626 - Convex Hull]] - [[https://www.spoj.com/problems/VMILI/|VMILI - Military Story]] **Sada pokročilá** - [[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=5&page=show_problem&problem=249|313 - Intervals]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=219&page=show_problem&problem=752|811 - The Fortified Forest]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=532&page=show_problem&problem=3797|5786 - Have You Driven a Fjord Lately?]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=41&page=show_problem&problem=953|10012 - How Big Is It?]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=41&page=show_problem&problem=1108|10167 - Birthday Cake]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1856|10915 - War on Weather]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=297&page=show_problem&problem=3722|12300 - Smallest Regular Polygon]] - [[https://www.spoj.com/problems/FSHEEP/|FSHEEP - Fencing in the Sheep]] - [[https://www.spoj.com/problems/TETRA/|TETRA - Sphere in a tetrahedron]] ===== Seminář 11 (28.4.) Kombinatoricke hry ===== * [[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:2022_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ář 12 ( 5.5.) Různé ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1EW0srP3LoAeNtV1LOxteg6DAt6zMtm0WR0CNMZYpZSk/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. **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. // \\ - [[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=29&page=show_problem&problem=1078|10137 - The Trip]] - [[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=229&page=show_problem&problem=3146|11995 - I Can Guess the Data Structure!]] - [[https://www.spoj.com/problems/ALTSEQ/|ALTSEQ - Alternating Sequences]] - [[https://www.spoj.com/problems/FISHER/|FISHER - Fishmonger]] - [[https://www.spoj.com/problems/HPYNOS/|HPYNOS - Happy Numbers I]] **Sada pokročilá** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=620|679 - Dropping Balls]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1052|10111 - Find the Winning Move]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1206|10265 - Toroidal Chess Queens' Problem]] - [[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=27&page=show_problem&problem=2529|11534 - Say Goodbye to Tic-Tac-Toe]] - [[https://www.spoj.com/problems/AE00/|AE00 - Rectangles]] - [[https://www.spoj.com/problems/EIGHTS/|EIGHTS - Triple Fat Ladies]] - [[https://www.spoj.com/problems/NOTATRI/|NOTATRI - Not a Triangle]] - [[https://www.spoj.com/problems/PALNUM/|PALNUM - Palindromic Number]] - [[https://www.spoj.com/problems/SHAKTI/|SHAKTI - SHAKTIMAN AND KILWISH]] ===== Seminář 13 ( 12.5.) Opakování zejména grafových postupů ===== Viz zejména seminář 05. ===== Seminář 14 ( 19.5.) Závěrečná směs ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1Nrof4V5P_GCX_vEKmTd01KDMLGfcT0F6bLpvfZASjI0/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. **Společná sada** //Tentokrát posluchači začínající i pokročilí vybírají z jediné společné sady úloh, body získají za každou vyřešenou úlohu. // - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=204&page=show_problem&problem=363|422 - Word-Search Wonder]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=33&page=show_problem&problem=642|701 - The Archeologists' Dilemma]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=33&page=show_problem&problem=788|847 - A Multiplication Game]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=33&page=show_problem&problem=959|10018 - Reverse and Add]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=33&page=show_problem&problem=1068|10127 - Ones]] - [[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=41&page=show_problem&problem=1108|10167 - Birthday Cake]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=41&page=show_problem&problem=1121|10180 - Rope Crisis in Ropeland!]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=1124|10183 - How Many Fibs?]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=1139|10198 - Counting]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=41&page=show_problem&problem=1156|10215 - The Largest/Smallest Box ...]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=41&page=show_problem&problem=1251|10310 - Dog and Gopher]] - [[https://www.spoj.com/problems/BALLSUM/|BALLSUM - Ball sum]] - [[https://www.spoj.com/problems/CADYDIST/|CADYDIST - Candy Distribution]] - [[https://www.spoj.com/problems/CPTTRN8/|CPTTRN8 - Character Patterns (Act 8)]]