**Místo a čas konání** Místo: online prostor, čas: čtvrtek od 16:15. [[https://fel.cvut.cz/cz/education/rozvrhy-ng.B202/public/html/mistnosti/10/12/m10125804.html|Rozvrh FEL]] ===== Semináře ===== ==== Tabulka s průběžným stavem ==== ^ Seminář ^ Datum \\ (hodiny) ^ Náplň ^ Úlohy/odkazy/prezentace \\ viz také pod tabulkou ^ | **1.** | **18.2** (2) | Snadné počítání a příprava na dynamické programování | | | **2.** | **25.2** (4) | ** Minisoutěž I** | | | **3.** | **4.3.** (2) | Dynamické programování | | | **4.** | **11.3.** (4) | ** Minisoutěž II** | | | **5.** | **28.3.** (2) | Cesty v grafech | | | **6.** | **25.3.** (4) | ** Minisoutěž III** | | | **7.** | **1.4.** (2) | Aritmetika a kombinatorika, teorie čísel | | | **8.** | **8.4.** (4) | ** Minisoutěž IV** | | | **9.** | **15.4** (2) | //Zrušeno - téma a čas náhradního semináře bude po dohodě v příštích týdnech// | | | **10.** | **22.4.** (4) | ** Minisoutěž V** - opakování DP, grafů a aritmetiky | | | **11.** | **29.4.** (2) | Výpočetní geometrie, mřížky | | | **12.** | **6.5.** (4) | ** Minisoutěž VI** | | | **13.** | **13.5.** (2) | Anatgonistické hry, Nim | | | **14.** | **20.5.** (4) | ** Minisoutěž VII** | | | **CELKEM** | ZS 2021 . . . . | **TABULKA - VÝSLEDKY ** | [[https://docs.google.com/spreadsheets/d/12oz87RgUIBEOgwt3rN1fVbqBbyfs-Z5CqeWireXxxgg/edit?usp=sharing| Celkový stav ]] | ---- ==== Seminář 01. (18.2.) Běžné počítání a příprava na DP ==== BBB konference link : [[https://cw.felk.cvut.cz/brute/teacher/bbb/cw_r0Y4Gic9bn|https://cw.felk.cvut.cz/brute/teacher/bbb/cw_r0Y4Gic9bn]] 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://www.spoj.com/problems/MARTIAN/|MARTIAN - Martian Mining]]\\ ===== 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/1Q_8rOcXApK7VyYenrMvZC1TlEjI6L3uCqxfPjstXg5o/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=8&page=show_problem&problem=615|674 - Coin Change]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=841|900 - Brick Wall Patterns]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=532&page=show_problem&problem=3794|5783 - Everyone out of the Pool]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=533&page=show_problem&problem=3812|5801 - The Rascal Triangle]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=526&page=show_problem&problem=3891|5880 - Vigenere Cipher Encryption]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=526&page=show_problem&problem=3897|5886 - The Grille]] - [[https://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&category=121&page=show_problem&problem=1985|11044 - Searching for Nessy]] - [[https://www.spoj.com/problems/FARIDA/|FARIDA - Princess Farida]] - [[https://www.spoj.com/problems/BYTESH1/|BYTESH1 - Filchs Dilemna]] **Sada pokročilá** - [[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=649&page=show_problem&problem=728|787 - Maximum Sub-sequence Product]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=655&page=show_problem&problem=977|10036 - Divisibility]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=655&page=show_problem&problem=1278|10337 - Flight Planner]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=655&page=show_problem&problem=1341|10400 - Game Show Math]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=655&page=show_problem&problem=1387|10446 - The Marriage Interview :-)]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=649&page=show_problem&problem=1625|10684 - The jackpot]] - [[https://www.spoj.com/problems/MBEEWALK/|MBEEWALK - Bee Walk]] - [[https://www.spoj.com/problems/SQRBR/|SQRBR - Square Brackets]] - [[https://www.spoj.com/problems/THREECOL/|THREECOL - Three-coloring of binary trees]] ---- ===== Seminář 03 (4.3.) Dynamické programování ===== Ukázky typických postupů a úloh. * {{ :courses:a4b36acm2:2018_ls:dag.pdf | Základní všechno možné průchodem DAG }} * {{ :courses:a4b36acm2:2018_ls:ukazkaprez3.pdf | Ukázka řešení -- Voda v rourách}} * {{ :courses:a4b36acm2:2018_ls:lisnlogn.pdf | LIS - nejdelší rostoucí podposloupnost v čase O(N log N) }} * [[https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/|LIS na GeeksforGeeks ]] * [[https://cw.fel.cvut.cz/wiki/courses/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 (11.3.) ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1ObQfEcQCDchCsBySw3iIh71Ng-S6aUbyVzSKiFJdCvo/edit?usp=sharing|Výkony v minisoutěži II]],\\ po skončení minisoutěže v 21:00, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz. **Prodloužený termín** Dnes je možno za 3 body odevzdávat úlohy až do 21:00. **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=465&page=show_problem&problem=378|437 - The Tower of Babylon]] - [[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/DIEHARD/|DIEHARD - DIE HARD]] - [[https://www.spoj.com/problems/DSUBSEQ/|DSUBSEQ - Distinct Subsequences]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=539&page=show_problem&problem=3748|5737 - Pills]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=538&page=show_problem&problem=3910|5899 - Tree Count]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=534&page=show_problem&problem=3956|5945 - Raggedy, Raggedy]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=992|10051 - Tower of Cubes]] - [[https://www.spoj.com/problems/CPCRC1C/|CPCRC1C - Sum of Digits]] **Sada pokročilá** - [[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=465&page=show_problem&problem=4097|1351 - String Compression]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=541&page=show_problem&problem=3785|5774 - Robot Navigation]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=538&page=show_problem&problem=3901|5890 - Bracelets]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=1095|10154 - Weights and Measures]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&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=1247|10306 - e-Coins]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=1342|10401 - Injured Queen Problem]] - [[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=114&page=show_problem&problem=1592|10651 - Pebble Solitaire]] ===== Seminář 05 (18.3.) Grafy a nejkratší cesty ===== S využitím publikace {{ :courses:a4b36acm1:2020_ls:laaksonen_programmershandbook.pdf | Antti Laaksonen: Competitive Programmer’s Handbook, s několika komentáři}}. \\ Originál: [[https://cses.fi/book/book.pdf|ke stažení]]. ==== Přehledy a návody ==== Nejkratší a nejdelší cesty: * {{ :courses:a4b36acm2:2018_ls:grafy-cesty.pdf | nejkratší a nejdelší cesty -- celkový přehled }} * {{ :courses:a4b36acm2:2018_ls:dag.pdf | nejkratší a nejdelší cesty v DAG }} {{ :courses:a4b36acm1:2020_zs:dijkstra_n_2.pdf |Dijkstra v O(n^2) }} 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: * {{ :courses:a4b36acm1:2020_ls:dfs.pptx | Napřed vůbec DFS}} * [[https://www.geeksforgeeks.org/topological-sorting-using-departure-time-of-vertex/| topsort by DFS]] * [[http://www.geeksforgeeks.org/detect-cycle-undirected-graph/|Detekce cyklu v grafu]] * [[http://www.geeksforgeeks.org/topological-sorting/|Nalezení topologického uspořádání vrcholů v grafu]] * [[http://www.geeksforgeeks.org/bridge-in-a-graph/|Identifikace mostů.]] (*_*_*) * [[http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/|Identifikace artikulací]] (*_*_*) * [[http://www.geeksforgeeks.org/biconnected-components/|Detekce bloků, tj. 2-souvislých komponent]] * [[http://www.geeksforgeeks.org/strongly-connected-components/|Nalezení silně souvislých komponent]] {{https://cw.fel.cvut.cz/old/_media/courses/a4b36acm/2017_zs/mst3.pptx|Poznámky k minimálním kostrám }} Všechny cesty: * [[https://www.geeksforgeeks.org/detect-negative-cycle-graph-bellman-ford/|Bellman-Ford]] * [[https://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/|Floyd-Warshall]] * [[https://www.cs.usfca.edu/~galles/visualization/Floyd.html|Floyd-Warshall algorithm example]] [[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html|další vizualizace]] ===== Seminář 06 (25.3.) ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1ZXJjVbrZUZRgFnLNDK-s_z_ekte-rD2OBbA9clBAnkg/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://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=302&page=show_problem&problem=1822|3821 - Tree Grafting]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=3355|5354 - The Forrest for the Trees]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=4206|6195 - The Dueling Philosophers Problem]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2733|11686 - Pick up sticks]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=4027|12582 - Wedding of Sultan]] - [[https://www.spoj.com/problems/BENEFACT/|BENEFACT - The Benefactor]] - [[https://www.spoj.com/problems/BITMAP/|BITMAP - Bitmap]] - [[https://www.spoj.com/problems/CATM/|CATM - The Cats and the Mouse]] - [[https://www.spoj.com/problems/CHICAGO/|CHICAGO - 106 miles to Chicago]] - [[https://www.spoj.com/problems/MLASERP/|MLASERP - Laser Phones]] **Sada pokročilá** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=683&page=show_problem&problem=3639|1198 - The Geodetic Set Problem]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=244&page=show_problem&problem=199|2198 - Protecting Zonk]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=343&page=show_problem&problem=2738|4737 - Hop --- Don't Walk!]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2768|11721 - Instant View of Big Bang]] - [[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://www.spoj.com/problems/CERC07K/|CERC07K - Key Task]] - [[https://www.spoj.com/problems/CLEANRBT/|CLEANRBT - Cleaning Robot]] - [[https://www.spoj.com/problems/GRAPHCUT/|GRAPHCUT - Graph Cut]] - [[https://www.spoj.com/problems/PA06ANT/|PA06ANT - Ant]] ===== Seminář 07 (1.4.) Aritmetika a kombinatorika ===== * [[https://math.feld.cvut.cz/habala/teaching/dma/dmknih11.pdf|Habalova kombinatorická skripta]]! * {{ :courses:a4b36acm1:2020_ls:habalavycuckombi.pdf | Z těchto skript tahák}} * {{ :courses:a4b36acm1:2020_ls:primes.pdf | Prvočísla, Eratosthenovo síto a kód }} * [[hhttps://en.wikipedia.org/wiki/Modular_arithmetic|Modulární aritmetika]] (Převážně stejná jako ta běžná) * [[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/ * 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ář 08 (8.4.) ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1_Q-tr8rOxXL6iwNudTfGS-CyJSvL-gnhp84u0ibHOLo/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://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=844|903 - Spiral of Numbers]] - [[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=247&page=show_problem&problem=3671|1230 - MODEX]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1103|10162 - Last Digit]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1170|10229 - Modular Fibonacci]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1176|10235 - Simply Emirp]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1725|10784 - Diagonal]] - [[https://www.spoj.com/problems/CANTON/|CANTON - Count on Cantor]] - [[https://www.spoj.com/problems/FIBOSUM/|FIBOSUM - Fibonacci Sum]] - [[https://www.spoj.com/problems/MARBLES/|MARBLES - Marbles]] **Sada pokročilá** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=279|343 - What Base Is This?]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=244&page=show_problem&problem=197|2196 - Multiplication]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=235&page=show_problem&problem=1342|3341 - Smallest Difference]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=533&page=show_problem&problem=3818|5807 - Maximum in the Cycle of 1]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1020|10079 - Pizza Cutting]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1270|10329 - Combinatorial Expression]] - [[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=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]] ===== Seminář 10 (22.4.) ===== === Úlohy === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1G45V4SzrpNrqXFCilE4dNBH1VCwTWo7Nw1E9R2aUQaw/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=114&page=show_problem&problem=531|590 - Always on the run]] - [[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&category=99&page=show_problem&problem=787|846 - Steps]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=267&page=show_problem&problem=1780|3779 - No Left Turns]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1188|10247 - Complete Tree Labeling]] - [[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&category=133&page=show_problem&problem=1549|10608 - Friends]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=655&page=show_problem&problem=1662|10721 - Bar Codes]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2467|11472 - Beautiful Numbers]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2533|11538 - Chess Queen]] **Sada pokročilá** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=233|297 - Quadtrees]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=272&page=show_problem&problem=72|2071 - Safe Packing]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=272&page=show_problem&problem=73|2072 - The Flat Cupboard]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=272&page=show_problem&problem=188|2187 - Video Watcher]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=268&page=show_problem&problem=1578|3577 - Toothpick Arithmetic]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=268&page=show_problem&problem=1581|3580 - Marbles in Three Baskets]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=532&page=show_problem&problem=3791|5780 - The Agency]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1589|10648 - Chocolate Box]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=407&page=show_problem&problem=1674|10733 - The Colored Cubes]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2692|11645 - Bits]] ===== Seminář 11 (29.4.) Geometrie ===== **{{ :courses:a4b36acm1:2020_ls:geombas1upd.pptx | Některé základní výpočty }} ** **[[https://en.wikipedia.org/wiki/Intersection_(Euclidean_geometry)| Počítání průsečíků]]** **[[https://en.wikipedia.org/wiki/List_of_trigonometric_identities|Reminder: Trigonometric identities]]** **[[https://en.wikipedia.org/wiki/Pick's_theorem|Pick's_theorem]]** http://jwilson.coe.uga.edu/emat6680fa05/schultz/6690/pick/pick_main.htm **Všeobecný přehled na MFF** (Programátorské kuchařky) http://ksp.mff.cuni.cz/tasks/24/cook5.html\\ **Polygon area** example: https://www.mathsisfun.com/geometry/area-irregular-polygons.html, code: http://www.codeproject.com/Articles/13467/A-JavaScript-Implementation-of-the-Surveyor-s-Form Very Brute force **Binary Search**: https://onlinejudge.org/external/105/10566.pdf **Sweep line example** {{ :courses:a4b36acm1:2020_zs:sweeplinexx.pdf | Touching rectangles}} **Sweep line rotates:**, http://www.spoj.com/problems/CERC07C/ (*_*_*) {{ :courses:a4b36acm1:2020_zs:spojcerc07c.pdf | komentář }} **Graham Scan** demo: http://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/ah/GrahamScan.html (//enable java?//)\\ code: http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/\\ Stanford examples: http://web.stanford.edu/class/cs97si/ (Namely: http://web.stanford.edu/class/cs97si/09-computational-geometry.pdf ) **Rotate points instead of lines** [[https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=6280| 8258 - Glyph Recognition]], {{ :courses:a4b36acm1:2020_zs:glyphs.pdf | solution idea}} **Množství komentovaných základních kódů** https://www.geeksforgeeks.org/geometric-algorithms/ **Kreslítko GeoGebra online** https://www.geogebra.org/graphing?lang=en (http://www.geogebra.org/ ??) **Seznamy geometrických kreslítek** https://en.wikipedia.org/wiki/List_of_interactive_geometry_software#2D_programs, http://mathforum.org/geometry/geometry.software.html ===== Seminář 12 (6.5.) ===== === Úlohy === === Výjimečně dnes budou na začátku úlohy zadány pomocí e-mailu. === === Kontrolujte kolem 16:15 svou školní schránku. === Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1uzeGG2GFHAcOBjJ4KPjdc1jNwgP7XMO-P9TnGy0sjXk/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=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]] **Sada pokročilá** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=239|303 - Pipe]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=292|356 - Square Pegs And Round Holes]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=217&page=show_problem&problem=575|634 - Polygon]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1328|10387 - Billiard]] - [[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=com_onlinejudge&Itemid=8&category=216&page=show_problem&problem=1838|10897 - Travelling Distance]] - [[https://www.spoj.com/problems/KPPOLY/|KPPOLY - Projections Of A Polygon]] - [[https://www.spoj.com/problems/QUADAREA/|QUADAREA - Maximal Quadrilateral Area]] - [[https://www.spoj.com/problems/TRANSMIT/|TRANSMIT - Transmitters]] ===== Seminář 13 (13.5.) Kombinatoricke hry ===== * [[https://math.fel.cvut.cz/gollova/lgr/lgr_11.pdf|Interní opáčko -- 18. přednáška z LGR]] * [[http://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/intro.pdf|Všeobecné poučení o hrách a Nimu]] [[http://mks.mff.cuni.cz/library/JakHratANeprohratFH/JakHratANeprohratFH.pdf|(výtah, česky)]] * [[http://web.mit.edu/sp.268/www/2010/impartialGames.pdf|Přehled na MIT]] * [[http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames | TopCoder - The Basic Introduction into Games]] * [[http://teorie-grafu.cz/zakladni-pojmy/jadro-grafu.php | Jádro grafu]] * Teorie her na CMU - [[http://www.math.cmu.edu/~mlavrov/arml/12-13/games-02-10-13.pdf|Combinatorial Game Theory]],[[http://www.math.cmu.edu/~mlavrov/arml/12-13/games-02-24-13.pdf|Even More Games]] * Kombinatorické hry - krátká ilustrace {{ :courses:a4b36acm1:2021_ls:combigames.pdf | pdf }} * Nimbers (Sprague-Grundyho čísla) - ukázková úloha ([[http://www.codechef.com/problems/BIGPIZA| Socializing Game around Pizza]], {{ :courses:a4b36acm2:2018_zs:pizza.pdf | kód? }}) * [[http://www.fq.math.ca/Scanned/1-4/whinihan.pdf|Fibonacciho Nim]] Příklady: * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=330&page=show_problem&problem=1345|Bachet's Game]] * [[http://www.spoj.com/problems/CLK/|Chomp]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=330&page=show_problem&problem=1309|Euclid's Game]] * [[http://www.spoj.com/problems/QCJ3/|The Game]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=330&page=show_problem&problem=2484|Integer Game]] * [[http://www.spoj.com/problems/MATGAME/|Matrix Game]] * [[https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=398&page=show_problem&problem=2824|Game]] * [[http://www.spoj.com/problems/QWERTY04/|TRIVIADOR]] * [[https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=3060|Playing With Stones]] * [[http://www.spoj.com/problems/MMMGAME/en/|M&M Game]] * [[http://www.spoj.com/problems/NGM/|A Game with Numbers]] * [[http://www.spoj.com/problems/PT07A/|Play with a Tree]]: How to tackle a problem of this sort was not covered in the lecture, but if you are interested, see [[http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf|Ferguson's Game Theory]] (lecture 6, specifically, the colon and fusion principles). * [[http://www.spoj.com/problems/BNWNIM/en/|Black and White Nim]]: Difficult, yet intriguing problem. * ===== Seminář 14 (20.5.) ===== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1e6e5D61i9hDwilUPyDZ0JGs-bu0GRC7rwSVHIEM511E/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. **Sada společná** //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.// - [[https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&Itemid=99999999&category=64&page=show_problem&problem=182|2181 - A Version of Nim]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&Itemid=99999999&category=94&page=show_problem&problem=322|2321 - Calendar Game]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&Itemid=99999999&category=90&page=show_problem&problem=407|2406 - Nim]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&Itemid=99999999&category=316&page=show_problem&problem=2270|4269 - A Simple Game]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&Itemid=99999999&category=350&page=show_problem&problem=2530|4529 - A Constrained Queen Game]] - [[https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&Itemid=99999999&category=387&page=show_problem&problem=3089|5088 - Alice and Bob's Trip]] - [[https://www.spoj.com/problems/BDOI16B/|BDOI16B - Beautiful Factorial Game]] - [[https://www.spoj.com/problems/CBIT01/|CBIT01 - Game of Square]] - [[https://www.spoj.com/problems/CF36D/|CF36D - New Game with a Chess Piece]] - [[https://www.spoj.com/problems/GAME3/|GAME3 - Yet Another Fancy Game]] - [[https://www.spoj.com/problems/GAMES/|GAMES - How Many Games?]] - [[https://www.spoj.com/problems/GOIT/|GOIT - Game of Iron Thrones]] - [[https://www.spoj.com/problems/HCT00001/|HCT00001 - Interesting Game with Polygons]] - [[https://www.spoj.com/problems/PLAYGAME/|PLAYGAME - PLAYGAME]] - [[https://www.spoj.com/problems/TRIOMINO/|TRIOMINO - Triomino Game]] - [[https://www.spoj.com/problems/VECTAR10/|VECTAR10 - Card Game]]