Search
Místo a čas konání
T2:C2-84, čtvrtek od 16:15. Rozvrh FEL
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.
Návodník na řešení
Proces lze vyzkoušet s hotovým řešením
Komentáře k úlohám na zamyšlení, jednoduché obraty ve snazších úlohách
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 Výkony v minisoutěži 0, 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.)
Pokročilí nebo začínající zkusí
Především BFS, DFS, Dijkstra, odkazy viz níže.
Nejkratší a nejdelší cesty:
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.
Aplikace prohledávání do hloubky:
Poznámky k minimálním kostrám
Negativní cykly:
Cesty mezi všemi páry uzlů:
Další vizualizace
Dalších 200+ ukázek a úloh:
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í
Mimořádné opatření Během semináře 6.10. mohou začínající účastníci také řešit a odevzdávat libovolné úlohy z 1. semináře (22.9.). Body se za ně budou započítávat stejně jako za úlohy níže.
Sada pokročilá
Ukázky typických postupů a úloh.
Úlohy pro rozmyšlení
10066 - The Twin Towers 10912 - Simple Minded Hashing 11432 - Busy Programmer Square Brackets 147 - Dollars 10081 - Tight Words Vertex Cover LATGACH3 11617 - An Odd Love
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.
Dodělávky: Viz Seminář 04 a úlohy v něm.
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.
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/
Způsobil však změnu v rozvrhu:
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.
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
Jednoduchá aplikace 438 - The Circumference of the Circle, 10335 - Ray Inside a Polygon
Poloha bodu a polygonu
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ář
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/ ??) (začni variantou “classic”).
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 pro pokročilce
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.