Výsledky mimo a2oj

https://docs.google.com/spreadsheets/d/1wVWH31wBLCZieYniuBHBZRmYA69n8963iGUDRNyZNxs/edit?usp=sharing

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:

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

1. V hlavním menu po přihlášení ťukněte na [My Account]
2. Ve vašem profilu na řádku Online Judge ID: je Vaše UVA ID.

• Odevzdejte libovolnou úlohu (klidně prázný soubor).
• Přejděte na stránku Live Archive: Posledních 50 Odevzdání
• Najděte řádku přislušící vaší odevzdané úloze a klikněte na své uživatelské jméno.
• V parametrech URL naleznete své userid.

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

Návodník na řešení

malá kategorizace grafových úloh

Dot product - Skalární součin

V první části semináře si zopakujeme standardní grafové úlohy řešitelné pomocí algoritmu prohledávání do hloubky, a to zejména ulohy:

• Detekce cyklu v grafu
• Nalezení topologického uspořádání vrcholů v grafu
• Identifikace mostů. (*_*_*)
• Identifikace artikulací (*_*_*)
• Detekce bloků, tj. 2-souvislých komponent
• Nalezení silně souvislých komponent

Dále:

Tabulky grafových úloh a složitostí

Poznámky k minimálním kostrám

Floyd-Warshall algorithm example

Bellman-Ford algorithm demo

Náměty pro pokročilejší řešitele:

Přehledy – Maximální tok a párování

Geeksforgeeks - Ford-Fulkerson Max flow

Geeksforgeeks - Maximum bipartite matching

Stanford Code

Úlohy

TAXI

MATCHING

COCONUTS

4333 - Paper Presentation

11045 - My T-shirt suits me

Ulohy na nejkratsi cesty a min. kostry:

• 10369 - Arctic Network - upraveny Kruskal ci dfs + binarni puleni
• 10246 - Asterix and Obelix - Floyd-Warshall + post-processing
• 10269 - Adventure of Super Mario - netrivialni Dijsktra
• 104 - Arbitrage - klasicka uloha na detekci negativniho/positivniho cyklu

A na dfs a spol:

• 315 - Network Artikulace
• 796 - Critical Links Mosty
• 610 - Street Directions Mosty
• 11504 - Dominos Silně souvislé komponenty
• 10510 - Cactus Silně souvislé komponenty

Reference:

• Kruskaluv algoritmus
• Floyd-Warshalluv algoritmus
• Dijkstruv algoritmus
• Bellman-Forduv algoritmus
• DFS pro hledani artikulaci
• DFS pro hledani mostu
• DFS pro hledani silne souvislych komponent

Přehledy a pár jednodušších úloh.

• Ukázky klasických úloh TT&MB
• Voda v rourách
• Základní všechno možné průchodem DAG
• nejdelší rostoucí podposloupnost v čase O(N log N)

Ukázky k vyzkoušení si:

• 900 - Brick Wall Patterns
• 10081 - Tight Words
• FARIDA - Princess Farida
• 10334 - Ray Through Glasses
• MMAXPER, Rectangles Perimeter - max upper envelope length
• Many Paths, One Destination
• Subsequence Problem
• Tower of Babylon
• Wachovia Bank
• Catch Fish
• Bribe the Prisoners
• Black or White

Ukázka kódu -- manipulace s DAG

Ad FFT:

Přehled a výklad: - FFT: Kap. 17. na stránkách T.Vally, Pruvodce_labyrintem_algoritmu- celá kniha

• MUL - Fast Multiplication
• POLYMUL - Polynomial Multiplication
• MAXMATCH - Maximum Self-Matching
• 12879 - Golf Bot
• 1718 - Tile Cutting
• 1733 - Design New Capital

Odkazy na materiály:

• Habalova kombinatorická skripta!
  • 369 - Combinations
  • 10329 - Combinatorial Expression
  • 10375 - Choose and divide
• 10213 - How Many Pieces of Land ? Eulerova formule V+F = E+2
• Prvočísla, Eratosthenovo síto a kód
  • 11408 - Count DePrimes
  • 11347 - Multifactorials
• Výpočet multiplikativní inverse
  • Rozšířený Euclidův algoritmus
  • ... A ještě přehledněji!!
  • Malá Fermatova věta
• Eulerova věta a funkce (1, 2, 3)
• Čínská věta o zbytcích
• Čísla všeho druhu:
  • Kombinační
  • Fibonacciho
  • Catalanova
    • 10303 - How Many Trees?
  • Motzkinova
  • Úloha spojující poslední dva jmenované druhy: Game Count
• Řešení lineárních rekurentních rovnic s konstantními koeficienty
  • Úloha: Chefs new Pet

Vyzkoušejte si:

• http://www.spoj.com/problems/AMR11E/
• http://www.spoj.com/problems/APS/
• http://www.spoj.com/problems/LCMSUM/

Pokročilí:

Segmentové stromy (pro někoho částečné opakování)

Popsány pěkně v průvodci, kap. 4.5. (není dlouhá )

Také v kuchařce KSP: Intervalové stromy.

Rozšířené ukázky: https://cw.fel.cvut.cz/wiki/courses/a4b36acm/2017_ls/seminare#seminar_10segmentove_stromy_pokrocili

Úlohy k vyzkoušení:

• QUERYIT - SLIS
• NDS - Increasing numbers
• GSS1 - Can you answer these queries I
• GSS3 - Can you answer these queries III
• 11235 - Frequent values

Řetězcové (hledací v řetězcích) úlohy pro pokročilce a klidně i základníky:

• 455 - Periodic Strings
• 902 - Password Search
• 10679 - I Love Strings!!
• 11019 - Matrix Matcher
• FILRTEST - File Recover Testing
• NHAY - A Needle in the Haystack
• PERIOD - Period
• SUB_PROB - Substring Problem

KMP code: http://www-igm.univ-mlv.fr/~lecroq/string/node8.html

Aho-Corasick code: http://www.geeksforgeeks.org/aho-corasick-algorithm-pattern-searching/

Materiály pro dnešní cvičení: kombinatoricke_hry