Search
Místo a čas konání
Místo: online prostor, čas: čtvrtek od 16:15. Rozvrh FEL
BBB konference link : https://cw.felk.cvut.cz/brute/teacher/bbb/cw_r0Y4Gic9bn
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 MARTIAN - Martian Mining
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.
Proces lze vyzkoušet s hotovým řešením Přidané upřesňující poznámky
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á
—-
Ukázky typických postupů a úloh.
Svoje výkony zapisujte samostatně do tabulky 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.
S využitím publikace Antti Laaksonen: Competitive Programmer’s Handbook, s několika komentáři. Originál: ke stažení.
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
Všechny cesty:
další vizualizace
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/
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.
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.
Některé základní výpočty
Počítání průsečíků
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, 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 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.
Příklady:
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.
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.