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)
Seminář | Datum (hodiny) | Náplň | Úlohy/odkazy |
---|---|---|---|
1. | 1.10. (2) | Servery, konta, odevzdání cvičné úlohy | viz pod tabulkou |
2. | 8.10. (4) | Kap. 9, průchody grafem, příprava soutěžících na CTU Open, rozcvičky začátečníků | viz pod tabulkou |
3. | 15.10. (2) | Struktura a nácvik prezentací | Ukázka: Voda v rourách |
4. | 22.10. (4) | Minisoutěž I | |
5. | 29.10. (2) | Kap. 11, DP základy i pokročilejší | |
6. | 5.11. (4) | Pokračování DP plus Kap. 10. grafy | |
7. | 12.11. (2) | Kap. 5. a 6. Návrat k aritmetice a kombinatorice | |
8. | 19.11. (4) | Minisoutěž II | |
9. | 26.11. (2) | Kap. 7. teorie čísel | |
10. | 3.12. (4) | Kap. 12. a 14. Výpočetní geometrie, mřížky | |
11. | 10.12. (2) | Nezařazená témata, singulární úlohy | |
12. | 17.12. (4) | Minisoutěž III | |
13. | 7.1. (2) | Opakování a doplnění restů | |
14. | 14.1. (4) | Individuální zakončení semestru | |
CELKEM | LS 2015 | Průběžný stav | Tabulka |
Ú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.
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.
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 :
Assuming both play optimally, who wins the game?
Number Game Revisited
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?
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
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 …