**Místo a čas konání** T2:C2-84, čtvrtek od 16:15. [[https://fel.cvut.cz/cz/education/rozvrhy-ng.B211/public/html/mistnosti/10/12/m10125804.html|Rozvrh FEL]] ===== Semináře ===== ==== Tabulka s průběžným stavem bodování ==== ^ Seminář ^ Datum \\ (hodiny) ^ Náplň ^ Úlohy/odkazy/prezentace \\ viz také pod tabulkou ^ | **1.** | **26.9.** (2) | Servery, konta, ukázkové úlohy a témata, cvičná odevzdání, jednoduchá opakování | | | **2.** | **3.10.** (4) | ** Minisoutěž I** - úlohy na informatický postřeh a zkušenost | | | **3.** | **10.10.** (2) | Dynamické programování I | | | **4.** | **17.10.** (4) | ** Minisoutěž II** | | | **5.** | **24.10.** (2) | Dynamické programování II | | | **6.** | **31.10.** (4) | ** Minisoutěž III** | | | **7.** | **7.11.** (2) | Cesty v grafech | | | **8.** | **14.11.** (4) | ** Minisoutěž IV** | | | **9.** | **21.11.** (2) | Aritmetika a kombinatorika, teorie čísel | | | **10.** | **28.11.** (4) | ** Minisoutěž V** | | | **11.** | **5.12.** (2) | Výpočetní geometrie, mřížky | | | **12.** | **12.12.** (4) | ** Minisoutěž VI** | | | **13.** | **19.12.** (4) | ** Minisoutěž VII** opakování témat | | | **14.** | **9.1.** (2) | // odpadá // | | | **CELKEM** | ZS 2024 . . . . | **TABULKA - VÝSLEDKY ** | [[https://docs.google.com/spreadsheets/d/1dy5l1hzkezNkRTDsO3Zqvj4ngRSQqS1MOFFbDrcv9Kk/edit?usp=sharing| Tady je celkový stav ]] | ---- ===== Seminář 1 (26.9.) ===== ==== Provoz a administrace ==== V průběhu praktických cvičení a také při domácí aktivitě svá řešení budete odevzdávat do serverů * [[https://onlinejudge.org/|Online Judge]] (dříve "UVa Online Judge") * [[https://www.spoj.com/|Sphere Online Judge]] (neboli "SPOJ") Na každém z těchto serverů si zřiďte konto, pokud ho tam ještě nemáte. [[https://cw.fel.cvut.cz/wiki/courses/a4b36acm/trenink?&#jak_na_reseni| Návodník na řešení ]] [[https://cw.fel.cvut.cz/wiki/courses/a4b36acm1/intro_basic|Proces lze vyzkoušet s hotovým řešením]] ==== Úlohy pro první seminář ==== Komentáře k úlohám na [[https://projecteuler.net/|Project Euler]]. * [[https://projecteuler.net/problem=29|Distinct Powers]] * [[https://projecteuler.net/problem=28|Number spiral diagonals]] * [[https://projecteuler.net/problem=85|Counting Rectangles]] * [[https://projecteuler.net/problem=15|Lattice Paths]] * [[https://projecteuler.net/problem=67|Maximum path sum II]] * [[https://projecteuler.net/problem=31|Coin Sums]] * [[https://projecteuler.net/problem=44|Pentagon Numbers]] * [[https://projecteuler.net/problem=81|Path Sum: Two Ways]] * [[https://projecteuler.net/problem=82|Path Sum: Three Ways]] * [[https://projecteuler.net/problem=83|Path Sum: Four Ways]] Vyzkoušejte si: \\ [[https://www.spoj.com/problems/TEST/|TEST - Life, the Universe, and Everything]] \\ [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=36|100 - The 3n + 1 problem]] \\ [[https://www.spoj.com/problems/PERMUT2/|PERMUT2 - Ambiguous Permutations]] \\ [[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://www.spoj.com/problems/MARTIAN/|MARTIAN - Martian Mining]]\\ **Pokročilí zkusí** * [[https://www.spoj.com/problems/SHP/|SHP - Shuffling Problem]] * [[https://www.spoj.com/problems/MZVRK/|MZVRK - Whirligig number]] * [[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=onlinejudge&page=show_problem&problem=1884|10943 - How do you add?]] * nebo si vyberte ze soutěže: [[https://contest.felk.cvut.cz/19prg/contest.html|CTU Open Contest, 2019]] ===== Seminář 02 (3.10.) ===== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1Mx9iDE0S_YGt0bmUHnpOYrPldi3TcO6hH-55PIDUVGk/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. //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. // \\ === Úlohy === **Začínající zkusí** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=431|490 - Rotating Sentences]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=30&page=show_problem&problem=784|843 - Crypt Kicker]] - [[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=33&page=show_problem&problem=959|10018 - Reverse and Add]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=30&page=show_problem&problem=979|10038 - Jolly Jumpers]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=41&page=show_problem&problem=1156|10215 - The Largest/Smallest Box]] - [[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=26&page=show_problem&problem=2486|11491 - Erasing and Winning]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2533|11538 - Chess Queen]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2544 |11549 - Calculator Conundrum ]] **pokročilí nebo začínající zkusí** - [[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=13&page=show_problem&problem=1095|10154 - Weights and Measures]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1341|10400 - Game Show Math]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1342|10401 - Injured Queen Problem]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2322|11347 - Multifactorials]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2502|11507 - Bender B. Rodríguez]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2692|11645 - Bits]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=602&page=show_problem&problem=4399|12661 - Funny Car Racing]] ===== Seminář 03 (10.10.) 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ář 04 (17.10.) ===== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1Eq7-94ZygnyXLt3LvaOubzohrzDPpIAYaQXNrD32nzE/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. // \\ === Úlohy === - [[https://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=onlinejudge&page=show_problem&problem=929|988 - Many Paths, One Destination]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=1010|10069 - Distinct Subsequences]] - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1022|10081 - Tight Words]] - [[https://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=114&page=show_problem&problem=2225|11258 - String Partition]] - [[https://www.spoj.com/problems/CPCRC1C/|CPCRC1C - Sum of Digits]] - [[http://www.spoj.com/problems/MMAXPER/|MMAXPER - Rectangles Perimeter]] - [[https://www.spoj.com/problems/MISERMAN/|MISERMAN - Wise And Miser]] - [[https://www.spoj.com/problems/RPLB/|RPLB - Blueberries]] **pokročilí nebo začínající zkusí** - [[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=15&page=show_problem&problem=1269|10328 - Coin Toss]] - [[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=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]] - [[https://www.spoj.com/problems/MFISH/|MFISH - Catch Fish]] - [[https://www.spoj.com/problems/ROCK|ROCK - Sweet and Sour Rock]] - **Náhradní úloha**: [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=167|231 - Testing the CATCHER]] Neřeš následující, nefunguje na ní odevzdavání [[http://www.spoj.com/problems/SUBP/|SUBP - Subsequence Problem]] - [[https://www.spoj.com/problems/TRAVERSE/|TRAVERSE - Traverse through the board]] - [[https://www.spoj.com/problems/WPC4F/|WPC4F - Through the troops]] ===== Seminář 05 (24.10.) Dynamické programování II ===== S využitím materiálů v semináři 03. ===== Seminář 06 (31.10.) ===== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1hZ8mFhQHjS0d1Weo5OTSdUG4guRJ6xTCh7gsgS7qwoI/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. // \\ === Úlohy === **Začínající zkusí** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=944|10003 - Cutting Sticks]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=992|10051 - Tower of Cubes]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1133|10192 - Vacation]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1226|10285 - Longest Run on a Snowboard]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1505|10564 - Paths through the Hourglass]] - [[https://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=26&page=show_problem&problem=2415|11420 - Chest of Drawers]] - [[https://www.spoj.com/problems/ANARC05B/|ANARC05B - The Double HeLiX]] - [[https://www.spoj.com/problems/FARIDA/|FARIDA - Princess Farida]] - [[https://www.spoj.com/problems/MIXTURES/|MIXTURES - Mixtures]] **Pokročilí nebo začínající zkusí** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1142|10201 - Adventures in Moving - Part IV]] - [[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=114&page=show_problem&problem=1540|10599 - Robots(II)]] - [[https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=2022|11081 - Strings]] - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2701|11654 - Arithmetic Subsequence]] - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=117&page=show_problem&problem=2882|11782 - Optimal Cut]] - [[https://www.spoj.com/problems/JEDNAKOS/|JEDNAKOS - JEDNAKOST]] - [[https://www.spoj.com/problems/MENU/|MENU - Menu]] - [[https://www.spoj.com/problems/SCUBADIV|SCUBADIV - Scuba diver]] - [[https://www.spoj.com/problems/TWENDS|TWENDS - Two Ends]] ===== Seminář 7 (7.11.) 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ář 08 (14.11.) ===== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1iSO3noAWFuS6huCGrG_AcYwv7Lv9khqBg4But9RAEKU/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. // \\ === Úlohy === **Začínající zkusí** - [[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=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=2620|11573 - Ocean Currents]] - [[https://www.spoj.com/problems/CHICAGO/|CHICAGO - 106 miles to Chicago]] - [[https://www.spoj.com/problems/HIGHWAYS/|HIGHWAYS - Highways]] - [[https://www.spoj.com/problems/LABYR1/|LABYR1 - Labyrinth]] - [[https://www.spoj.com/problems/MLASERP/|MLASERP - Laser Phones]] - [[https://www.spoj.com/problems/PT07Z/|PT07Z - Longest path in a tree]] - [[https://www.spoj.com/problems/TDBFS/|TDBFS - Searching the Graph]] - [[https://www.spoj.com/problems/UCV2013H/|UCV2013H - Slick]] **Pokročilí nebo začínající zkusí** - [[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=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=onlinejudge&page=show_problem&problem=2768|11721 - Instant View of Big Bang]] - [[https://www.spoj.com/problems/CERC07K/|CERC07K - Key Task]] - [[https://www.spoj.com/problems/CLEANRBT/|CLEANRBT - Cleaning Robot]] - [[https://www.spoj.com/problems/PA06ANT/|PA06ANT - Ant]] - [[https://www.spoj.com/problems/POUR1/|POUR1 - Pouring water]] - [[https://www.spoj.com/problems/TFRIENDS/|TFRIENDS - True Friends]] ===== Seminář 09 ( 21.11.) Aritmetika a kombinatorika, teorie čísel ===== * [[https://math.fel.cvut.cz/cz/lide/habala/teaching/dma/dmknih11.pdf|Habalova kombinatorická skripta]]! * {{ :courses:a4b36acm1:2020_ls:habalavycuckombi.pdf | Z těchto skript tahák}} * {{ :courses:a4b36acm1:2020_ls:primes.pdf | Prvočísla, Eratosthenovo síto a kód }} * [[hhttps://en.wikipedia.org/wiki/Modular_arithmetic|Modulární aritmetika]] (Převážně stejná jako ta běžná) * [[https://en.wikipedia.org/wiki/Arithmetico–geometric_sequence| Sčítání čísel (aritmeticko-geometrická posloupnost)]] * Čísla různých druhu: * [[https://en.wikipedia.org/wiki/Combination|Kombinační]] * [[https://en.wikipedia.org/wiki/Fibonacci_number|Fibonacciho]] * [[https://www.geeksforgeeks.org/applications-of-catalan-numbers/|Catalanova]] , [[http://mathworld.wolfram.com/CatalanNumber.html|na Mathworld]] * **OEIS** Vynikající všeobecná referenční příručka [[https://oeis.org/|The On-Line Encyclopedia of Integer Sequences]] * Rychlé mocnění * https://www.geeksforgeeks.org/exponential-squaring-fast-modulo-multiplication/ * https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/ * * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=34&page=show_problem&problem=1154|10213 - How Many Pieces of Land ?]] Eulerova formule V+F = E+2 * Příklad nezbytného předpočítání [[https://contest.felk.cvut.cz/22prg/solved/array/problem.pdf|Arrays/CTU Open 2022]] Vyzkoušejte si: * http://www.spoj.com/problems/AMR11E/ * http://www.spoj.com/problems/APS/ * http://www.spoj.com/problems/LCMSUM/ * https://www.spoj.com/problems/PTIME/ * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2403|11408 - Count DePrimes]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=474&page=show_problem&problem=74|138 - Street Numbers]] **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 (28.11.) ===== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1iSl80O6pZrfCQqF93oWDQ7_0abL2L-3hkS_c-61a08o/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. // \\ === Úlohy === **Začínající zkusí** - [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=192&page=show_problem&problem=310|374 - Big Mod]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=353|412 - Pi]] - [[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=19&page=show_problem&problem=1674|10733 The Colored Cube]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2287|11312 - Flipping Frustration]] - [[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=2549|11554 - Hapless Hedonism]] - [[https://www.spoj.com/problems/BREAKING/|BREAKING - Number Breaking]] **Pokročilí nebo začínající zkusí** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=720&page=show_problem&problem=1109|10168 - Summation of Four Primes]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1153|10212 - The Last Non-zero Digit.]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1432|10491 - Cows and Cars]] - [[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/APS/|APS - Amazing Prime Sequence]] - [[https://www.spoj.com/problems/CUBEFR/|CUBEFR - Cube Free Numbers]] - [[https://www.spoj.com/problems/DIVSUM/|DIVSUM - Divisor Summation]] ===== Seminář 11 (05.12.) 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ář 12 (12.12.) ===== **Nejprve plán na příští týden** Hlasujte pro organizaci semináře v příštím týdnu 19.12. [[https://forms.gle/4i1vA5gzBKjApsPj9|Hlasujte zde co nejdříve]]. **Dále jako obvykle** Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1Q9iqHyHdCML7Aan2BA-0T-Uugx_Wi01F9kw51mzwAA4/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. // \\ === Úlohy === **Začínající zkusí** - [[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=5&page=show_problem&problem=311|375 - Inscribed Circles and Isosceles Triangles]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1006|10065 - Useless Tile Packers]] - [[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=15&page=show_problem&problem=1294|10353 - Circles in Hexagon :-)]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1323|10382 - Watering Grass]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=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=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2673|11626 - Convex Hull]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2695|11648 - Divide The Land]] **Pokročilí nebo začínající zkusí** - [[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=213&page=show_problem&problem=946|10005 - Packing polygons]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1515|10574 - Counting Rectangles]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1516|10575 - Polylops]] - [[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=216&page=show_problem&problem=1838|10897 - Travelling Distance]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=217&page=show_problem&problem=1053|10112 - Myacm Triangles]] - [[https://www.spoj.com/problems/KPPOLY/|KPPOLY - Projections Of A Polygon]] - [[https://www.spoj.com/problems/TRANSMIT/|TRANSMIT - Transmitters]] ===== Seminář 13 (19.12.) ===== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/18_SKmkIhNvwkLEWH2o8d5Vq7UDWfId08hbvOw6qZSQY/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. === Úlohy === //Tentokrát, na závěr semestru, máme jen jedinou sadu, společnou pro začínající i pokročilé, 3 body získá každý za každou vyřešenou úlohu. // **Sada společná** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=649&page=show_problem&problem=448|507 - Jill Rides Again]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=603|662 - Fast Food]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=127&page=show_problem&problem=614|673 - Parentheses Balance]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=802|861 - Little Bishops]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=854|913 - Joana and the Odd Numbers]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=1342|10401 - Injured Queen Problem]] - [[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=861&page=show_problem&problem=4721|12856 - Counting substhreengs]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2616|11569 - Lovely Hint]] - [[https://www.spoj.com/problems/BLMIRANA/| BLMIRANA - Mayonnaise Arrow]] - [[https://www.spoj.com/problems/BYTESH1/|BYTESH1 - Filchs Dilemna]] - [[https://www.spoj.com/problems/CHASE/| CHASE - A Chase In WonderLand ]] - [[https://www.spoj.com/problems/FCDC/|FCDC - Factorial Modulo]] - [[https://www.spoj.com/problems/GEOM/|GEOM - Geometry and a Square]] - [[https://www.spoj.com/problems/PIGBANK/|PIGBANK - Piggy-Bank]]