Místo a čas konání
Místo: T2:C2-84, čas: čtvrtek od 16:15. Rozvrh FEL
Seminář | Datum (hodiny) | Náplň |
---|---|---|
1. | 17.2 (2) | Snadné počítání a příprava na dynamické programování |
2. | 24.2 (4) | Minisoutěž I |
3. | 3.3. (2) | Dynamické programování (DP) |
4. | 10.3. (4) | Minisoutěž II |
5. | 17.3. (2) | Cesty v grafech |
6. | 24.3. (4) | Minisoutěž III |
7. | 31.3. (2) | Aritmetika a kombinatorika, teorie čísel |
8. | 7.4. (4) | Minisoutěž IV |
9. | 14.4 (2) | Výpočetní geometrie, mřížky |
10. | 21.4. (4) | Minisoutěž V - |
11. | 28.4. (2) | Anatgonistické hry, Nim |
12. | 5.5. (4) | Minisoutěž VI |
13. | 12.5. (2) | Opakování DP, grafů a aritmetiky |
14. | 19.5. (4) | Minisoutěž VII opakování DP, grafů a aritmetiky |
CELKEM | LS2022 . VÝSLEDKY | TABULKA - Celkový stav |
Komentáře k úlohám na Project Euler.
Vyzkoušejte si:
Bouncy numbers
Exploring strings for which only one character comes lexicographically after its neighbour to the left
Coin sums
Pro pokročílé:
Vykoušejte níže některou Vámi nedodělanou úlohu, vloni nebo vůbec. Vyřešená úloha do 18:00 bude bodována standardnímí 3 body.
V průběhu praktických cvičení a také při domácí aktivitě svá řešení budete odevzdávat do serverů
Na každém z těchto serverů si zřiďte konto, pokud ho tam ještě nemáte.
Svoje výkony zapisujte samostatně do tabulky
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í.
Sada pokročilá
komntáře k minulým úlohám, pozor na log2(2^63-1), není to nutně menší než 63.
Ukázky typických postupů a úloh.
Doporučené úvodní přehledové a úctyhodné publikace, asi nejpřístupněji napsané:
Jednotlivé metody:
Svoje výkony zapisujte samostatně do tabulky
Výkony v minisoutěži II,
po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz.
Sada začínající
Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady “začínající” nezískají body.
Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady.
V této sadě je část úloh na dynamické programování, ostatní slouží jako rozcvičkové ad hoc úlohy s různorodými metodami řešení.
Sada pokročilá
Také v této sadě nejsou všechny úlohy na dynamické programování (DP), některé lze řešit i bez DP.
Nejkratší a nejdelší cesty:
Ukázka BFS za běhu __ Porovnej s ukázkou DFS níže
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.
Aplikace prohledávání do hloubky:
Negativní cykly:
Cesty mezi všemi páry uzlů:
Tok v síti a maximální párování:
Různé vizualizace na USFCA
Dalších 200+ ukázek a úloh:
Svoje výkony zapisujte samostatně do tabulky
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.
Sada pokročilá
Vyzkoušejte si:
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/
Svoje výkony zapisujte samostatně do tabulky
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.
Sada pokročilá
Determinant matice, většinou stačí 2×2.
Některé základní výpočty (pdf verze )
Počítání průsečíků Soustava lin. rovnic, Cramerovo pravidlo
Reminder: Trigonometric identities
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 Touching rectangles
Sweep line rotates:, http://www.spoj.com/problems/CERC07C/ (*_*_*) komentář
Konvexní obal Graham Scan demo: http://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/ah/GrahamScan.html (enable java?)
code: http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
Stanford examples: http://web.stanford.edu/class/cs97si/ (Namely: http://web.stanford.edu/class/cs97si/09-computational-geometry.pdf )
Rotate points instead of lines 8258 - Glyph Recognition (ICPC Live Archive | Regionals 2017 | Europe-Northwestern), 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
Svoje výkony zapisujte samostatně do tabulky
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.
Sada pokročilá
Příklady:
Svoje výkony zapisujte samostatně do tabulky
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.
Sada pokročilá
Viz zejména seminář 05.
Svoje výkony zapisujte samostatně do tabulky
Výkony v minisoutěži VII,
po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz.
Společná sada
Tentokrát posluchači začínající i pokročilí vybírají z jediné společné sady úloh, body získají za každou vyřešenou úlohu.