===== Semináře ACM ===== https://cw.fel.cvut.cz/wiki/courses/a4b36acm3/2023_zs/seminare **Místo a čas konání** T2:C2-84, čtvrtek od 16:15. [[https://intranet.fel.cvut.cz/cz/education/rozvrhy-ng.B231/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.** | **28.9.** (2) | Odpadl | | | **2.** | **5.10.** (4) | Servery, konta, ukázkové úlohy a témata, cvičná odevzdání, jednoduchá opakování, \\ ** Minisoutěž I** | | | **3.** | **12.10.** (2) | Dynamické programování I | | | **4.** | **19.10.** (4) | ** Minisoutěž II** | | | **5.** | **26.10.** (2) | Dynamické programování II | | | **6.** | **2.11.** (4) | ** Minisoutěž III** | | | **7.** | **9.11.** (2) | Aritmetika a kombinatorika, teorie čísel | | | **8.** | **16.11.** (4) | ** Minisoutěž IV** | | | **9.** | **23.11.** (2) | Výpočetní geometrie, mřížky | | | **10.** | **30.11.** (4) | ** Minisoutěž V** | | | **11.** | **7.12.** (2) | Kombinatorické hry, Nim | | | **12.** | **14.12.** (4) | ** Minisoutěž VI** | | | **13.** | **21.12.** (2) | Opakování, shrnutí a rozšíření probraných témat | | | **14.** | **11.1.** (4) | ** Minisoutěž VII** | | | **CELKEM** | ZS 2023 | **TABULKA - VÝSLEDKY ** | [[https://docs.google.com/spreadsheets/d/1dy5l1hzkezNkRTDsO3Zqvj4ngRSQqS1MOFFbDrcv9Kk/edit?usp=sharing| Tady je celkový stav ]] | ---- ===== Seminář 01 (28.9.) ===== Odpadl kvůli státnímu svátku. ===== Seminář 02 (5.10.) ===== ==== Provoz a administrace ==== V průběhu praktických cvičení a také při domácí aktivitě svá řešení budete odevzdávat do serverů * [[https://onlinejudge.org/|Online Judge]] (dříve "UVa Online Judge") * [[https://www.spoj.com/|Sphere Online Judge]] (neboli "SPOJ") * [[https://icpcarchive.ecs.baylor.edu/|Live Archive]] (Úlohy z ACM soutěží) (aktuálně neaktivní -- uvidíme, zda se rozběhne) Na každém z těchto serverů si zřiďte konto, pokud ho tam ještě nemáte. [[https://cw.fel.cvut.cz/wiki/courses/a4b36acm/trenink?&#jak_na_reseni| Návodník na řešení ]] [[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 zamyšlení, jednoduché obraty ve snazších úlohách * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=74|138 - Street Numbers]] * [[https://www.spoj.com/problems/BUSYMAN/|BUSYMAN - I AM VERY BUSY]] * [[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=99&page=show_problem&problem=1731|10790 - How Many Points of Intersection?]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=72|136 - Ugly Numbers]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2510|11515 - Cranes]] * [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=41|105 - The Skyline Problem]] ** Vyzkoušejte si:** \\ //Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady "začínající" nezískají body.\\ Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady. // \\ Svoje výkony zapisujte **samostatně** do tabulky [[https://docs.google.com/spreadsheets/d/1QMHn4-6N_ZxcyPxsgjVKJWnaD8C5UFNs9bs6h7kkyQs/edit#gid=0|Výkony v minisoutěži I]],\\ po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz. **Začínající zkusí** (**Upozornění**: Úlohy níže jsou řazeny abecedně podle svých názvů, což nesouvisí s jejich tématikou, obtížností nebo jinými parametry.) - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=98&page=show_problem&problem=235 | 299 - Train Swapping]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=101&page=show_problem&problem=520| 579 - Clock Hands]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=101&page=show_problem&problem=1328| 10387 - Billiard]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=456&page=show_problem&problem=2515| 11520 - Fill the Square]] - [[https://www.spoj.com/problems/AE00/|AE00 - Rectangles]] - [[https://www.spoj.com/problems/AMR10G/|AMR10G - Christmas Play]] - [[https://www.spoj.com/problems/ATOMS/|ATOMS - Atoms in the Lab]] - [[https://www.spoj.com/problems/CRAN02/|CRAN02 - Roommate Agreement]] - [[https://www.spoj.com/problems/FCTRL/|FCTRL - Factorial]] - [[https://www.spoj.com/problems/GOO/|GOO - Game Of Ones]] **Pokročilí nebo začínající zkusí** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=457&page=show_problem&problem=953|10012 - How Big Is It?]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1020|10079 - Pizza Cutting]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1218|10277 - Boastin' Red Socks]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1700|10759 - Dice Throwing]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1854|10913 - Walking on a Grid]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2664|11617 - An Odd Love]] - [[https://www.spoj.com/problems/ABCD/|ABCD - Colours A, B, C, D]] - [[https://www.spoj.com/problems/BTCK/|BTCK - A problem of Backtracking]] - [[https://www.spoj.com/problems/CUBEFR/CUBEFR - Cube Free Numbers]] - [[https://www.spoj.com/problems/THREECOL/|THREECOL - Three-coloring of binary trees]] ===== Seminář 03 (12.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 (19.10.) ===== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/17cOubiSOEu1u1FrN2Czf7dKwd8RHwPJG-h-2D-stqkM/edit?usp=sharing|Výkony v minisoutěži II]],\\ po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz. //Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady "začínající" nezískají body.\\ Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady. // \\ **Začínající zkusí** (**Upozornění**: Úlohy níže jsou řazeny abecedně podle svých názvů, což nesouvisí s jejich tématikou, obtížností nebo jinými parametry.) - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=99&page=show_problem&problem=787|846 - Steps]] - [[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=17&page=show_problem&problem=1505|10564 - Paths through the Hourglass]] - [[http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1853| 10912 - Simple Minded Hashing]] \\ - [[https://www.spoj.com/problems/BYTESH1/|BYTESH1 - Filchs Dilemna]] - [[http://www.spoj.com/problems/FARIDA/|FARIDA - Princess Farida]] - [[https://www.spoj.com/problems/NY10E/|NY10E - Non-Decreasing Digits]] - [[https://www.spoj.com/problems/SNGINT|SNGINT - Encode Integer ]] - [[https://www.spoj.com/problems/SUMITR/|SUMITR - Sums in a Triangle]] - [[https://www.spoj.com/problems/TOE1|TOE1 - Tic-Tac-Toe ( I ) ]] **pokročilí nebo začínající zkusí** - [[https://www.spoj.com/problems/ACODE|ACODE - Alphacode]] - [[http://www.spoj.com/problems/BABTWR/|BABTWR - Tower of Babylon]] - [[https://www.spoj.com/problems/MARTIAN|MARTIAN - Martian Mining]] - [[http://www.spoj.com/problems/MFISH/|MFISH - Catch Fish]] - [[https://www.spoj.com/problems/MIXTURES|MIXTURES - Mixtures]] - [[http://www.spoj.com/problems/MMAXPER/| MMAXPER, Rectangles Perimeter - max upper envelope length]] - [[https://www.spoj.com/problems/ROCK|ROCK - Sweet and Sour Rock]] - [[https://www.spoj.com/problems/SCUBADIV|SCUBADIV - Scuba diver]] - [[http://www.spoj.com/problems/SUBP/|SUBP - Subsequence Problem]] - [[https://www.spoj.com/problems/TWENDS|TWENDS - Two Ends]] ===== Seminář 05 (26.10.) Dynamické programování II ===== S využitím materiálu z předchozích dvou seminářů ( 03 a 04 ). ===== Seminář 06 (2.11.) ===== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1GaxiKDRoJ_JKcqMi47Ezj8SQD1lHdQNEfbYsmRCqMRg/edit?usp=sharing|Výkony v minisoutěži III]],\\ po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz. //Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady "začínající" nezískají body.\\ Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady. // \\ **Začínající zkusí** (**Upozornění**: Úlohy níže jsou řazeny abecedně podle svých názvů, což nesouvisí s jejich tématikou, obtížností nebo jinými parametry.) - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=615|674 - Coin Change]] - [[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=26&page=show_problem&problem=2415|11420 - Chest of Drawers]] - [[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=26&page=show_problem&problem=2486|11491 - Erasing and Winning]] - [[http://www.spoj.com/problems/BYTESM2/ | BYTESM2 - Philosophers Stone]] - [[http://www.spoj.com/problems/COINS/ | COINS - Bytelandian gold coins]] - [[http://www.spoj.com/problems/DCEPC501/ | DCEPC501 - Save Thy Toys]] - [[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=503|562 - Dividing coins]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=936|995 - Super Divisible Numbers]] - [[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=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]] - [[https://www.spoj.com/problems/GNYR09F/|GNYR09F - Adjacent Bit Counts]] - [[https://www.spoj.com/problems/JEDNAKOS/|JEDNAKOS - JEDNAKOST]] ===== Seminář 07 ( 09.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]] **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 (16.11.) ===== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1sv0BypZ-MVW6TpHxbKZVkdSXLWymjo6CiBN1nX64nyk/edit?usp=sharing|Výkony v minisoutěži IV]],\\ po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz. //Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady "začínající" nezískají body.\\ Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady. // \\ **Začínající zkusí** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=903|962 - Taxicab Numbers]] - [[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=1141|10200 - Prime Time]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1176|10235 - Simply Emirp]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1480|10539 - Almost Prime Numbers]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&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=1725|10784 - Diagonal]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1857|10916 - Factstone Benchmark]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2396|11401 - Triangle Counting]] - [[https://www.spoj.com/problems/FIBOSUM/|FIBOSUM - Fibonacci Sum]] **pokročilí nebo začínající zkusí** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=96|160 - Factors and Factorials]] - [[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=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=908|967 - Circular]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1153|10212 - The Last Non-zero Digit]] - [[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=16&page=show_problem&problem=1432|10491 - Cows and Cars]] - [[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=18&page=show_problem&problem=1630|10689 - Yet another Number Sequence]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=19&page=show_problem&problem=1671|10730 - Antiarithmetic?]] - [[https://www.spoj.com/problems/HS08PAUL/|HS08PAUL - A conjecture of Paul Erdős]] ===== Seminář 09 (23.11.) Výpočetní geometrie, mřížky ===== Determinant matice, většinou stačí 2×2. **{{ :courses:acm_all:2023_ls:geombas1upd2.pptx | Některé základní výpočty }}** {{ :courses:acm_all:2023_ls: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ář 10 (30.11.) ===== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1QdANM1OH8n7SFWNJEINzKSbrFBfHMN3QtrUbaOC4zrw/edit?usp=sharing|Výkony v minisoutěži V]],\\ po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz. //Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady "začínající" nezískají body.\\ Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady. // \\ **Začínající zkusí** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=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=214&page=show_problem&problem=379|438 - The Circumference of the Circle]] - [[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=218&page=show_problem&problem=1238|10297 - Beavergnaw]] - [[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=212&page=show_problem&problem=2009|11068 - An Easy Task]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=214&page=show_problem&problem=2474|11479 - Is this the easiest problem?]] - [[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=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=213&page=show_problem&problem=946|10005 - Packing polygons]] - [[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=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=onlinejudge&page=show_problem&problem=2896|11796 - Dog Distance]] - [[https://www.spoj.com/problems/QUADAREA/|QUADAREA - Maximal Quadrilateral Area]] - [[https://www.spoj.com/problems/TRANSMIT/|TRANSMIT - Transmitters]] ===== Seminář 11 (7.12.) Kombinatorické hry, Nim ===== Odpadl ===== Seminář 12 (14.12.) ===== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1rRoHy0VcmHMzSDNZwGls6c9yOhp1IQL7riNTdKlGJgs/edit?usp=sharing|Výkony v minisoutěži VI]],\\ po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz. //Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady "začínající" nezískají body.\\ Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady. // \\ **Začínající zkusí** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=33&page=show_problem&problem=959|10018 - Reverse and Add]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1078|10137 - The Trip]] - [[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=15&page=show_problem&problem=1304|10363 - Tic Tac Toe]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1561|10620 - A Flea on a Chessboard]] - [[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=2661|11614 - Etruscan Warriors Never Play Chess]] - [[https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&category=230&page=show_problem&problem=3108|11957 - Checkers]] - [[https://www.spoj.com/problems/EQBOX/|EQBOX - Equipment Box]] - [[https://www.spoj.com/problems/KMOVES/|KMOVES - Knight Moves]] **pokročilí nebo začínající zkusí** - [[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=20&page=show_problem&problem=1803|10862 - Connect the Cable Wires]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=457&page=show_problem&problem=1980|11039 - Building designing]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2614|11567 - Moliu Number Generator]] - [[https://www.spoj.com/problems/BLMIRANA/|BLMIRANA - Mayonnaise Arrow]] - [[https://www.spoj.com/problems/DANGER/|DANGER - In Danger]] - [[https://www.spoj.com/problems/IITKWPCN/|IITKWPCN - Playing With Balls]] - [[https://www.spoj.com/problems/PA06ANT/|PA06ANT - Ant]] - [[https://www.spoj.com/problems/PALNUM/|PALNUM - Palindromic Number]] ===== Seminář 13 (21.12.) Kombinatorické hry, Nim ===== * [[https://math.fel.cvut.cz/en/people/gollova/lgr/lgr_11a.pdf|Interní opáčko -- 18. přednáška z LGR]] * [[http://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/intro.pdf|Všeobecné poučení o hrách a Nimu]] [[http://mks.mff.cuni.cz/library/JakHratANeprohratFH/JakHratANeprohratFH.pdf|(výtah, česky)]] * [[http://web.mit.edu/sp.268/www/2010/impartialGames.pdf|Přehled na MIT]] * [[http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames | TopCoder - The Basic Introduction into Games]] * [[http://teorie-grafu.cz/zakladni-pojmy/jadro-grafu.php | Jádro grafu]] * Teorie her na CMU - [[http://www.math.cmu.edu/~mlavrov/arml/12-13/games-02-10-13.pdf|Combinatorial Game Theory]],[[http://www.math.cmu.edu/~mlavrov/arml/12-13/games-02-24-13.pdf|Even More Games]] * Kombinatorické hry - krátká ilustrace {{ :courses:a4b36acm1:2021_ls:combigames.pdf | pdf }} * Nimbers (Sprague-Grundyho čísla) - ukázková úloha ([[http://www.codechef.com/problems/BIGPIZA| Socializing Game around Pizza]], {{ :courses:a4b36acm2:2018_zs:pizza.pdf | kód? }}) * [[http://www.fq.math.ca/Scanned/1-4/whinihan.pdf|Fibonacciho Nim]] Příklady: * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=330&page=show_problem&problem=1345|Bachet's Game]] * [[http://www.spoj.com/problems/CLK/|Chomp]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=330&page=show_problem&problem=1309|Euclid's Game]] * [[http://www.spoj.com/problems/QCJ3/|The Game]] * [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=330&page=show_problem&problem=2484|Integer Game]] * [[http://www.spoj.com/problems/MATGAME/|Matrix Game]] * [[http://www.spoj.com/problems/NGM/|A Game with Numbers]] * [[http://www.spoj.com/problems/PT07A/|Play with a Tree]]: How to tackle a problem of this sort was not covered in the lecture, but if you are interested, see [[http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf|Ferguson's Game Theory]] (lecture 6, specifically, the colon and fusion principles). * [[http://www.spoj.com/problems/BNWNIM/en/|Black and White Nim]]: Difficult, yet intriguing problem. ===== Seminář 14 (11.01.) ===== Svoje výkony zapisujte samostatně do tabulky [[https://docs.google.com/spreadsheets/d/1-ovrB10eSqAlDNmLWiX0CnPEef3Tz3ikz41vik4ym08/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. //Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady "začínající" nezískají body.\\ Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady. // \\ **Začínající zkusí** - [[https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=247|311 - Packets]] - [[https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=788|847 - A Multiplication Game]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=226&page=show_problem&problem=2918|11818 - Game --- Mouse and Cheese]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=226&page=show_problem&problem=2999|11877 - The Coco-Cola Store]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=244&page=show_problem&problem=3711|12290 - Counting Game]] - [[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=com_onlinejudge&Itemid=8&category=866&page=show_problem&problem=4980|13082 - High School Assembly]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=878&page=show_problem&problem=5167|13244 - Space Happiness]] - [[https://www.spoj.com/problems/QCJ3/|QCJ3 - The Game]] - [[https://www.spoj.com/problems/TFRIENDS/|TFRIENDS - True Friends]] **pokročilí nebo začínající zkusí** - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=196&page=show_problem&problem=932|991 - Safe Salutations]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=955|10014 - Simple calculations]] - [[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://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=416&page=show_problem&problem=2366|11371 - Number Theory for Newbies]] - [[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=866&page=show_problem&problem=4965|13067 - Prime Kebab Menu]] - [[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/CPTTRN8/|CPTTRN8 - Character Patterns (Act 8)]] - [[https://www.spoj.com/problems/GAME2/|GAME2 - Looks like Nim - but it is not]]