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.

Rozvrh

Seminář Datum
(hodiny)
Náplň Úlohy/odkazy
viz také pod tabulkou
1. 25.2. (4) Servery, konta, ukázkové úlohy a témata, cvičná odevzdání Výsledky na A2OJ
2. 3.3 (2) Průchody grafem,
3. 10.3. (4) Minisoutěž I Výsledky na A2OJ
4. 17.3. (2) DP I
5. 24.3. (4) Minisoutěž II Výsledky na A2OJ
6. 31.3. (2) Pokračování DP plus grafy
7. 7.4. (4) Minisoutěž III Výsledky na A2OJ
8. 14.4. (2) Aritmetika a kombinatorika, teorie čísel
9. 21.4 (4) Minisoutěž IV Výsledky na A2OJ
10. 28.4. (5) Minisoutěž V Trénink s FIT a MFF
Nácvik soutěže v týmech

Výsledky na A2OJ
11. 5.5. (2) Komentáře k úlohám z tréninku, singulární úlohy, doplnění starších témat
12. 12.5 (2) Výpočetní geometrie, mřížky
13. 19.5. (4) Minisoutěž VI Výsledky na A2OJ
14. 26.5. (2) Opakování a doplnění restů
CELKEM LS 2015 Průběžný stav Tabulka

Seminář 1.

Motivační úloha

Pěkná motivační úloha na úvod: Kings on the Chessboard, řešení: kings_bruteforce.c, kings_dp.c, kings_graphs.c

Ahmed Aly Online Judge

V průběhu praktických cvičení (sudé výukové týdny) svá řešení budete odevzdávat do A2 Online Judge. Prosíme, vytvořte si každý svůj vlastní účet sledováním následujícího linku: Sign Up. Vzhledem k tomu, že A2 Online Judge je pouze tzv. agregátor výsledků, musíte si vytvořit účty v příslušných judgích, které skutečně ověřují správnost vašich řešení, a to: Sphere Online Judge, UVa Online Judge a ACM-ICPC Live Archive.

Aby A2OJ věděl o odevzdaných úlohách, musíte vyplnit ve svém profilu ID, které jste si vytvořili či vám bylo přiděleno u výše uvedených judgů. Zde je shrnut postup, jak se k nim dostat:

Sphere Online Judge (SPOJ)

  1. Neuvěřitelné, ale login je vaše ID.

UVA Online Judge

  1. Odevzdejte libovolnou úlohu.
  2. Přejděte na následující stránku.
  3. Sledujte odkaz u své odevzdané úlohy ve sloupci “user”.
  4. Konec URL výsledné stránky obsahuje vaše UVA ID (URL: …&userid=[UVA_ID])

ACM-ICPC Online Judge

  • Postup je stejný jako u UVA Online Judge.

Test odevzdávacího systému

Po vytvoření účtů se můžete registrovat do soutěže na A2 Online Judge, klikněte zde.

Výběr úloh pro otestování odevzdávacího systému:

  1. Pro bojácné:
  2. Pro mírně statečnější:
  3. Pro drakobijce:

Seminář 2.

1. Používejte k ladění uDebug. Odkaz nahoře napravo v úloze UVA nebop ICPC Archive.

2. Mějte soupis vzorečků.

Dnes nás čeká povídání o grafových algoritmech.

Úlohy pro zamyšlení:

Seminář 3.

Minisoutěž v programování - téma: Grafové algoritmy. Registrace do soutěže - ACM_S16E02 (Standings)

658 - It's not a Bug, it's a Feature! - Source-Target Shortest Path (Consider input sizes! - what is a node and what is an edge?)

10985 - Rings'n'Ropes - All-Pairs Shortest Path (How is the task related to the graph diameter?)

10608 - Friends Largest Connected Component (Union-Find) (Can be solved without building the graph in the memory.)

10305 - Ordering Tasks - Topological Sort (DFS)

567 - Risk - Source-Target Shortest Path (BFS)

10596 - Morning Walk - Graph Connectivity and Degree Check (How is the problem related to the Euler trail problem?)

534 - Frogger - Shortest Path (tricky) (Can you modify the Dijkstra algorithm somehow?)

532 - Dungeon Master - Shortest Path (BFS)

10459 - The Tree Root - Tree Center and Diameter (Think of a solution in linear time wrt the number of nodes.)

10701 - Pre, in and post - (Pre/In)-Order to Post-Order Conversion

Seminář 4. DP

Seminář 5

Seminář 6 DP a DAG

Seminář 7

Minisoutěž v programování - téma: Dynamické programování. Registrace do soutěže - ACM_S16E03 (Standings)

Seminář 8

Seminář 9

Minisoutěž v programování - téma: Aritmetika, Kombinatorika a Teorie čísel. Registrace do soutěže - ACM_S16E05 (Standings)

Seminář 10

Seminář 11

Diskuse k tréninku SWERC 2014:

Odkazy k řešení úloh:

Algoritmy pro Maximální Párování v Bipartitních Grafech:

Seminář 12

Seminář 13

Minisoutěž v programování - téma: Výpočetní Geometrie a Párování v Grafech. Registrace do soutěže - ACM_S16E06 (Standings)

Úlohy z minisoutěže a k tréninku:

105 - The Skyline Problem
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=41

270 - Lining Up
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=206

313 - Intervals
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=249

737 - Gleaming the Cubes
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=9&page=show_problem&problem=678

833 - Water Falls
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=774

920 - Sunny Mountains
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=861

10088 - Trees on My Island
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1029

11030 - Predator II
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=22&page=show_problem&problem=1971

11579 - Triangle Trouble
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2626

11626 - Convex Hull
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2673

11704 - Caper pizza
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=117&page=show_problem&problem=2751

11648 - Divide The Land
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2695

Seminář 14

courses/a4b36acm1/2016_ls/seminare.txt · Last modified: 2018/10/03 03:51 (external edit)