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)


Shrnutí osnov a rozvrh

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

Seminář 1.

Ú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é:

Seminář 2.

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

Seminář 3.

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

Seminář 4.

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.

Seminář 5.

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.

Seminář 6.

Seminář 7.

Dynamické programování - viz. kapitola 11 v Programming Challenges a přednáška o DP z minulých let: Dynamické programování.

Seminář 8.

Seminář 10.

Seminar 11: Combinatorial Game Theory

Warm Up Games

Simple Number Game

Alice and Bob play the following game. They choose a number N to play with. The runs are as follows:

  1. Alice plays first and the two players alternate.
  2. In his/her turn, a player can subtract from N number 1, 2, or 3, but it must be smaller than N. The number thus obtained is the new N.
  3. The person who cannot make a move in his/her turn loses the game.

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 :

  1. Alice plays first, and the two players alternate.
  2. In his/her turn, a player can subtract from N any proper divisor (not equal to N) of N. The number thus obtained is the new N.
  3. The person who cannot make a move in his/her turn loses the game.

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:

  1. Bob plays first and the two players alternate.
  2. In his/her turn, a player can subtract from N any prime number (including 1) less than N. The number thus obtained is the new N.
  3. The person who cannot make a move in his/her turn loses the game.

Assuming both play optimally, who wins the game?

References

Seminar 12: Combinatorial Game Theory

List of the problems for today:

Seminář 13: Intervalové stromy

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

Seminář 14: Intervaly a intervalové stromy

Okruhy pro domácí úlohy

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 …

courses/a4b36acm2/2015_zs/seminare.txt · Last modified: 2018/02/21 22:30 (external edit)