Search
Místo a čas konání
KN:E-311, čtvrtek od 16:15, střídavě 2 a 4 hodiny týdně, viz rozpis níže. Parita týdnů v rozvrhu v KOSu nemusí být pro ACM relevantní.
Pracovní text
Steven S. Skiena, Miguel A. Revilla: Programming Challenges link (záložní link)
Všecny úlohy z knihy na UVA Judge: Root :: Programming Challenges (Skiena & Revilla)
Úlohy pro začínající a mírně pokročilé
Do příště (8.10.) promyslete řešení úloh z kap 1. až 4. z knihy (odkazy jsou nahoře), promyslete jich co nejvíce. Kromě toho pokud možno naprogramujte a úspěšně odevzdejte úlohy uvedené níže, příště si je okomentujeme. Pokud se vám nebude dařit, je to také dobré znamení, poznamenejte si (do komentáře v kódu) co skřípe, ať to pak můžeme na semináři řešit.
Úlohy pro ostatní
Rozmyslete si řešení úloh, většinou se snaží vybočovat ze zajetých kolejí aniž jsou příliš náročné:
Základní trénink BFS pro potřebné 924 - Spreading The News
Komentáře k příkladům Kap. 8. Rozmyslete, řešte Ad Bicoloring A graph is bicolorable if and only if it is bipartite. Also, a graph is bipartite if and only if all its cycles have even length. Method: Runn BFS from any node A. It must hold that all neighbours of any node with even distance from A (= color 1) have odd distance form A (= color 2).
Ad Wheels Do not build the graph explicitely.
Ad Tourist Guide Find path with maximum capacity. Capacity of the path is equal to the minimum of capacities of edges on this path. Modify Dijkstra accordingly - always expand search tree along the cheapest edge.
Ad Slash maze The hint 9.7.9.4 (page 216) says it all.
Ad Edit Step Ladders Longest path in DAG, do not build the graph explicitely.
Ad Tower of cubes Longest path in DAG, split each cube (which can be rotated) into six cubes (which cannot be rotated). Follow the hint 9.7.9.6.
Ad Dusk Till Dawn Answer 'Yes' to the hint 9.7.9.7.
Ad Hanoi Troubles Find it out yourself!
Další základní téma Kap. 8. nepokryté Tree diameter Start at any node A, find most distant node B. Then start in B and find most distant node C to it. Distance AC migh be generally larger than distance AB. The distance BC is guaranteed to mi maximum in the tree, it is its diameter. Faster: Create dummy node D, connect to it all tree leaves and run BFS from D, the one or two nodes with max distance form D is/are the tree center, this max distance is also the tree radius. The diameter = 2*radius + center cardinality - 1.
10459 - The Tree Root
10308 - Roads in the North
Pro pokročilé a trénující
Rozmyslete a formulujte postup u co nejvíce úloh, alespoň tří. Implementujte jednu nebo více.
Virtual Friends Almost Union-Find Rotate to root Flight Planning Pre, in and post Tree Reconstruction How Many Trees? Critical Links
Kap. 10 v knize, rozbor jejích jednotlivých úloh.
Úlohy na UVA
Prváci : Libovolná úloha z kap. 2.-4.
Váš den narození modulo 8 udává pořadové číslo úlohy (0., 1., …, 7. shora) kterou rozeberte. Stejně postupujte s měsícem narození, abyste získali číslo druhé úlohy, k rozboru. Pokud se rovná prvnímu, přičtěte pět, modulujte 8.
Online trénink na soutěž CTU Open: http://a2oj.com/Contest.jsp?ID=21847
Výklad, grafová reprezentace, na co si dát v základní grafové manipulaci pozor.
Studujte také další návody ze Stanfordu.
Minisoutěž: "Graph Problems Competition" on Ahmed-Aly.
Proběhla demostrace řešení několika jednodušších a pár pokročilejších úloh, které se typicky řešeší pomocí DFS/BFS/Dijkstrovým algoritmem. Důležité ponaučení - všechny úlohy se, redukují na prohledávání stavového prostoru - implicitní graf, ve kterém vrcholy reprezentují stav světa a hrany (mohou být vážené) představují možné přechody z jednoho stavu do druhého. Také jsme si ukázali několik řešení úlohy spreadsheet, která byla zadána minule.
Do minisoutěže úlohy, link: http://a2oj.com/Contest.jsp?ID=22461
Samostatné záložní linky na jednotlivé úlohy, použij napřed odkaz výše.
Dynamické programování - viz. kapitola 11 v Programming Challenges a přednáška o DP z minulých let: Dynamické programování.
Dynamické programování - rozcvička před minisoutěží. Úlohy: http://www.spoj.com/problems/ANARC05H/en/ http://www.spoj.com/problems/ANARC07G/en/ http://www.spoj.com/problems/BABTWR/ http://www.spoj.com/problems/CRSCNTRY/ http://www.spoj.com/problems/FPOLICE/ http://www.spoj.com/problems/GNYR09F/ http://www.spoj.com/problems/JEDNAKOS/en/ http://www.spoj.com/problems/MMAXPER/en/ http://www.spoj.com/problems/PARTY/ http://www.spoj.com/problems/PT07X/ Odevzdávejte svá řešení přímo na serveru SPOJ.
Unidirectional TSP 116 437 - The Tower of Babylon 1292 - Strategic game Distinct subsequences 10069 Longest common subsequence 10405 Bar codes 10721 Simple hashing 10912 Boxes 11003
Odevzdávejte svá řešení přímo na serveru UVA.
Počty prvočíselné a kombinatorické.
Některé odkazy související s úlohami
Catalanova čísla https://en.wikipedia.org/wiki/Catalan_number
Kombinační čísla http://arantxa.ii.uam.es/~ssantini/writing/notes/s667_binomial.pdf http://www.zweigmedia.com/RealWorld/tutstats/bincoeffs.html
Modulární mocnění https://discuss.codechef.com/questions/20451/a-tutorial-on-fast-modulo-multiplication-exponential-squaring https://en.wikipedia.org/wiki/Modular_exponentiation
Euklidův algoritmus (největší společný dělitel) http://mathworld.wolfram.com/EuclideanAlgorithm.html
Prvočísla http://www.geeksforgeeks.org/sieve-of-eratosthenes/
Simple Number Game Alice and Bob play the following game. They choose a number N to play with. The runs are as follows:
Assuming both play optimally, who wins the game?
Yet Another Number Game Alice and Bob play the following game. They choose a number N to play with. The rules are as follows :
Number Game Revisited Alice and Bob play the following game. They choose a number N to play with. The runs are as follows:
List of the problems for today:
Dnešní cvičení bude o intervalových stromech, viz. kuchařka KSP, range minimum query (navíc LCA, HL-dekompozice).
Příklad netriviální úlohy, která je krásnou ukázkou aplikace Fenwickova stromu: e_num_of_invs.py
Pro zájemce dodatečná témata
11028 - Sum of Product
10624 - Super Number
ANDROUND - AND Rounds
Vyberte si libovolnou úlohu z některého okruhu, a řešte.
1. Regionals 2006 - Asia - Beijing 2. Regionals 2006 :: Asia - Dhaka
Navrhujte podle potřeby další okruhy …