===== Pokročilé programovací soustředění ===== == Vede == [[mailto:berezovs@fel.cvut.cz| Marko Genyk-Berezovskyj ]]\\ == Přišli == Jakub Sláma, Josef Krška, Šimon Mandlík, Martin Němec, Emmanuil Vaganov, Charlotte Panušková, Dominik Hoftych, Lev Kolomazov, Artem Gribanov, Igor Ekisev. ---- == Středa 23.9. dopoledne == Seznámení, rozvičky po prázdninách: [[courses:a4b36acm:x_lps_ulohy|Rozcvičky]] . == Středa 23.9. odpoledne == Práce s online vyhodnocovacím serverem Navštivte [[http://www.spoj.com/|Sphere Online Judge]] a zaregistrujete se. Seznam počátečních trénovacích úloh je zde: [[http://www.spoj.com/problems/basics/|List of basics problems]]. Z nich vybíráme: * [[http://www.spoj.com/problems/TESTINT/|TESTINT - Test 1 ]] * [[http://www.spoj.com/problems/CPTTRN7/|CPTTRN7 - Character Patterns (Act 7)]] * [[http://www.spoj.com/problems/HS12MBR/|HS12MBR - Minimum Bounding Rectangle]] ---- == Čtvrtek 24.9. dopoledne == Přednáška: Grafy a jejich reprezentace. Převod z jedné reprezentace do jiné, ověřování jednoduchých vlastností grafu (Max a min stupeň, test zda je graf úplný, kružnicí, cestou). Poznatky: * Uzel, hrana, stupeň uzlu, Graf orientovaný, neorientovaný, vážený, úplný, souvislý, hustý, rovinný, strom, kružnice, náhodný. * Úlohy "stejnosti", vzdálenosti, nejkratší cesty, nejlevnější cesty, obchodního cestujícího, koster, párování. * Matice sousednosti, spojová reprezentace. * Anglické termíny, anglické identifikatory, anglické komentáře v kódu. Referenční texty: [[http://kam.mff.cuni.cz/~kuba/ka/grafy_a_stromy.pdf|Grafy a stromy]], [[http://kam.mff.cuni.cz/~kuba/ka/reprezentace_grafu.pdf|Reprezentace grafu]], [[http://ksp.mff.cuni.cz/encyklopedie/kucharky/programatorske-kucharky/05-grafy.pdf|Grafy]] Úlohy :[[courses:a4b36acm:x_lps_ulohy#Kolo| Kolo]] a [[courses:a4b36acm:x_lps_ulohy#Trojúhelník| Trojúhelník]]. == Čtvrtek 24.9. odpoledne == Přednáška: Kořenové stromy, průchody stromem, rekurzivní zpracování stromů. Poznatky: * Jednoduchá reprezentace v poli * Extrémně krátký kód * Výraznější učící křivka Úloha :[[courses:a4b36acm:x_lps_ulohy#Binární strom| Binární strom]] ---- == Pátek 25.9. dopoledne == Přednáška: Fronta a zásobník a jejich využití při prohledávání grafu (tzv. BFS a DFS). Referenční text: [[http://kam.mff.cuni.cz/~kuba/ka/pruchod.pdf|Průchod grafu]] Úlohy :[[courses:a4b36acm:x_lps_ulohy#Průchod do šířky| Průchod do šířky]], navrhněte postup řešení pro [[http://www.spoj.com/problems/CERC07K/|CERC07K - Key Task]] nebo [[http://www.spoj.com/problems/MAKEMAZE/|MAKEMAZE - VALIDATE THE MAZE]] (a zkuste odevzdat kód), == Pátek 25.9. odpoledne == Přednáška: Přehled dalších grafových úloh (nejkratší cesty, souvislost grafu) a jejich složitost, resp. praktická upočítatelnost. Referenční text: [[http://ksp.mff.cuni.cz/encyklopedie/kucharky/programatorske-kucharky/17-tezke-problemy.pdf| Těžké problémy]] ---- == Pondělí 28.9. dopoledne i odpoledne == Půlmaraton: Prohledávání [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=116&page=show_problem&problem=1549|10608 - Friends]] [[http://www.spoj.com/problems/PT07Y/|PT07Y - Is it a tree]] [[http://www.spoj.com/problems/PT07Z/|PT07Z - Longest path in a tree]] [[http://www.spoj.com/problems/CAM5/|CAM5 - prayatna PR]] , [[http://www.spoj.com/problems/ALLIZWEL/|ALLIZWEL - ALL IZZ WELL]] , [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=543&page=show_problem&problem=2671|11624 - Fire!]] , [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=37&page=show_problem&problem=945|10004 - Bicoloring]] , [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2306|11331 - The Joys of Farming]] , [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=599&page=show_problem&problem=646|705 - Slash Maze]] , [[http://www.spoj.com/problems/LABYR1/|LABYR1 - Labyrinth]] ,,,[[http://www.spoj.com/problems/GCPC11J/|GCPC11J - Time to live]] Directed Acyclic Graph (DAG) a topologické uspořádání: [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=78&page=show_problem&problem=2733|11686 - Pick up sticks]] [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=37&page=show_problem&problem=992|10051 - Tower of Cubes]] [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=37&page=show_problem&problem=970|10029 - Edit Step Ladders]] ---- == Úterý 29.9. dopoledne i odpoledne == Dijkstrův algoritmus jako aplikace prioritní fronty: [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=116&page=show_problem&problem=989|10048 - Audiophobia]] [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=37&page=show_problem&problem=1040|10099 - The Tourist Guide]] ---- == Středa 30.9. dopoledne i odpoledne == Backtrack: [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=36&page=show_problem&problem=802|861 - Little Bishops]] [[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2614|11567 - Moliu Number Generator]] ---- ==== Zdroje poučení ==== Jakub Černý:[[http://kam.mff.cuni.cz/~kuba/ka/| Základní grafové algoritmy]], KAM MFF, 2010, online publikace.\\ Steven S. Skiena, Miguel A. Revilla: [[http://acm.cs.buap.mx/downloads/Programming_Challenges.pdf|Programming Challenges]] ([[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.173.8499&rep=rep1&type=pdf|záložní link]])\\ 'Programátorské kuchařky z MFF UK'' [[http://ksp.mff.cuni.cz/study/cooks/cookbook.html| kuchařky.]] \\ [[http://comsci.liu.edu/~jrodriguez/cs631sp08/c++priorityqueue.html|C++ priority queues]] [[http://javapapers.com/java/java-priorityqueue/|Java PriorityQueue]] ---- ==== Zdroje úloh ==== * Archiv úloh z regionálních i světových kol soutěží ACM Programming Contest [[https://icpcarchive.ecs.baylor.edu/|ACM-ICPC Live Archive]] * Soutěžní stránky ACM na FEL: [[http://contest.felk.cvut.cz/|ACM International Collegiate Programming Contest]] * University of Valladolid: [[http://uva.onlinejudge.org/| UVA Online Judge]], UVA Toolkit [[http://uvatoolkit.com/problemssolve.php|Tématické členění vybraných úloh z UVA ]] * SPOJ [[http://www.spoj.com/|Sphere Online Judge]] Přes 13000 úloh všech úrovní, [[http://vnoi.info/index.php?option=com_voj&task=classify&site=spoj|Tématické členění vybraných úloh z SPOJ 1]] a [[http://problemclassifier.appspot.com/|Tématické členění vybraných úloh z SPOJ 2]] * [[http://www.codechef.com/|Codechef]] obsahuje k nahlédnutí zdrojové kódy úspěšných řešitelů. * [[http://codeforces.com/|Codeforces]] * [[http://projecteuler.net/problems| Project Euler]] Proslulý zdroj matematičtěji zaměřených úloh, přinejmenším první stovku z nich lze doporučit každému zájemci o efektivní programováni. * Korespondenční semináře z programování (KSP), [[http://ksp.mff.cuni.cz/ |MFF UK Praha]], [[https://www.ksp.sk/|MFF UK Bratislava]], [[http://ganymed.math.muni.cz/ks/|MU Brno]]. * Úlohy ze [[http://mo.mff.cuni.cz/p/|středoškolských programovacích olympiád ]]. ==== Nadstavba ==== Účast v ACM ICPC Maratonu: [[https://icpc.baylor.edu/regionals/finder/maraton-2015| link]] ---- ====== Rozcvičky ====== **1.** Napište přeložte a spusťte Hello world. **2.** Spočtěte počet slov v textovém souboru, slova jsou oddělená mezerami, soubor jinak obsahuje jen malá písmena a, b, c. , z. Vypište slova v abecedním pořadí. **3.** V dané posloupnosti čísel najděte taková, která jsou součtem všech jim předcházejících čísel v posloupnosti. Příklad. Vstup 8 1 1 4 6 2 3 17 34 Výstup 1 6 17 34 **4.** Ve čtvercové 0/1 matici velikosti NxN určete, jestli jedničky tvoří vyplněný čtverec velikosti alespoň 2x2. **5.** Ve čtvercové 0/1 matici určete počet všech úseček. Úsečka je souvislá vodorovná nebo svislá posloupnost jedniček s délkou alespoň 2, kterou nelze dále prodloužit. Úsečky se mohou různě dotýkat i protínat. Vstup je v souboru in.txt, první řádek obsahuje velikost matice N, na dalších N řádcích vstupu je N řádků matice, každý obsahuje N znaků 0/1 oddělených mezerami. Maximální velkost N je 1000. Na výstup (stačí na konzoli) vypište počet úseček. Příklad Vstup 7 0 0 0 1 1 0 0 1 1 1 1 0 0 1 0 1 1 1 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 1 0 1 0 Výstup 9 0 0 1 1 0 0 1 ====== Převod reprezentace 1. ====== Načtěte ze vstupu (konzole nebo soubor) matici sousednosti grafu reprezentaci grafu a vypište seznam hran grafu. První řádek vstupu obsahuje pouze hodnotu N - počet uzlů grafu, následuje N řádků s maticí sousedností, hodnoty na řádcích jsou odděleny mezerami. Uzly grafu číslujte od 0, každý uzel má číslo odpovídající jeho indexu v matici sousednosti. {{ :courses:a4b36acm:prevod1.jpg?200|}} Příklad Vstup 6 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 Výstup 0 3 1 2 1 3 1 4 2 5 3 4 4 5 ====== Převod reprezentace 2. ====== Načtěte ze vstupu (konzole nebo soubor) seznam hran grafu a vypište jeho matici sousednosti a jeho spojovou reprezentaci. Uzly jsou číslovány od 0 do N-1, kde N je počet uzlů grafu. Na vstupu je nejprve řádek s hodnotami N a M oddělenými mezerou, N je počet uzlů a M je počet hran grafu. Poté následuje M řádků představujících jednotlivé hrany v libovolném pořadí. Na řádku jsou oddělená mezerou čísla koncových uzlů hrany. Matici sousednosti vypisujte bez uvádění počtu uzlů. Ve spojové reprezentaci uveďte na každém řádku jeden uzel - nejprve jeho číslo a poté za pomlčkou seznam čísel jeho sousedů v libovolném pořadí oddělených mezerou. {{ :courses:a4b36acm:prevod2.jpg?200|}} Příklad Vstup 6 7 4 3 3 5 0 1 1 2 2 0 2 3 3 1 Výstup 0 1 1 0 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 5 - 3 4 - 3 3 - 5 4 2 1 2 - 3 1 0 1 - 3 2 0 0 - 2 1 ====== Kolo ====== {{ :courses:a4b36acm:w8.jpg?100|}} Určete, jestli je zadaný graf kolo. Kolo je kružnice s jedním přidaným uzlem uvnitř, ze kterého vedou hrany (paprsky) do všech ostatních uzlů grafu. Viz [[http://mathworld.wolfram.com/WheelGraph.html|příklady]]. Graf na vstupu má nejvýše N = 20000 uzlů a je zadán seznamem hran. První řádek vstupu obsahuje číslo N, dále následuje 2N-2 řádků, každý představuje jednu hranu. Na řádku jsou uvedena čísla koncových uzlů hrany oddělená mezerou. Uzly jsou číslovány 1..N. Na výstupu je jediný řádek s řetězcem ANO resp. NE, pokud zadaný graf je resp. není kolem. Příklad 1. Vstup 6 1 2 2 3 3 4 4 5 5 6 6 1 6 2 6 3 6 4 1 5 Výstup ANO Příklad 2. Vstup 5 5 4 4 3 3 2 2 1 1 5 1 4 1 3 2 4 Výstup NE Další vstupní testovací data pro {{:courses:a4b36acm:data100.txt| N = 100}}, {{:courses:a4b36acm:data1000.txt| N = 1000}}, {{:courses:a4b36acm:data10000.txt| N = 10000}}, {{:courses:a4b36acm:data20000.txt| N = 20000}}. Kontrola výsledků {{:courses:a4b36acm:sol.txt| zde}}. ====== Trojúhelník ====== {{ :courses:a4b36acm:ttriangl.jpg?100|}} Trojúhelník v grafu je každá trojice uzlů (x, y, z), která je navzájem propojená hranami (x, y), (y, z), (x, z). Určete, jestli daný graf obsahuje trojúhelník. Graf na vstupu má nejvýše 10 uzlů a je zadán maticí sousedností. První řádek obsahuje jedno číslo N, dalších N řádků obsahuje matici sousednosti, hodnoty v matici jsou odděleny mezerou. Na výstupu je jediný řádek s řetězcem ANO resp. NE, pokud zadaný graf obsahuje resp. neobsahuje trojúhelník. Příklad 1. Vstup 4 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 Výstup ANO Příklad 2. Vstup 5 0 0 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 Výstup NE ====== Binární strom ====== V daném binárním stromu, jehož každý uzel má určitou hodnotu, zjistěte několik věcí: * Počet listů * Součet hodnot ve všech listech * Součet hodnot v listech s největší hloubkou * Maximální možný součet hodnot na cestě z kořene do některého listu Předpokládáme, že strom má N uzlů číslovaných od 0 do N-1. Strom je zadán výčtem uzlů a jejich následníků takto: Na prvním řádku vstupu je hodnota N a číslo kořene oddělené mezerou. Každý z dalších N řádků představuje jeden uzel stromu ve formátu //číslo uzlu, hodnota uzlu, číslo levého potomka, číslo pravého potomka//. Hodnoty jsou odděleny mezerami, neexistující potomek je označen číslem -1. Na výstupu jsou postupně na jednotlivých řádcích hledané hodnoty. {{ :courses:a4b36acm:strom1.jpg?400|}} Příklad Vstup 11 3 0 20 -1 -1 1 10 0 2 2 30 -1 -1 3 5 1 9 4 40 -1 -1 5 80 4 7 6 50 -1 -1 7 90 6 8 8 60 -1 -1 9 99 5 10 10 70 -1 -1 Výstup 6 270 110 359 Příklad Vstup 10 0 0 30 1 2 1 20 3 4 2 90 7 9 3 40 -1 -1 4 30 8 -1 5 40 -1 -1 6 30 -1 -1 7 10 -1 -1 8 10 5 6 9 20 -1 -1 Výstup 5 140 70 140 Malý ukázkový rekurzivní kód v Javě: package lps; import java.util.Scanner; public class BinTree { static int N; static int root; static int nil = -1; static int [] Val; static int [] L; static int [] R; public static void main(String[] args) { loadFromStd(); print(root); System.out.printf("sum values %d\n", sumvals(root)); System.out.printf("no of leaves %d\n", noOfLeaves(root)); printIdent(root, 0); } static void loadFromStd() { Scanner input = new Scanner( System.in ); N = input.nextInt(); Val = new int [N]; L = new int [N]; R = new int [N]; root = input.nextInt(); int curr; for(int i = 0; i < N; i++) { curr = input.nextInt(); Val[curr] = input.nextInt(); L[curr] = input.nextInt(); R[curr] = input.nextInt(); } } static int sumvals(int node) { if (node == nil) return 0; return Val[node] + sumvals(L[node]) + sumvals(R[node]); } static int noOfLeaves(int node) { if (L[node] == nil && R[node] == nil) return 1; return noOfLeaves(L[node]) + noOfLeaves(R[node]); } static void print(int node) { if (node == nil) return; System.out.printf("%d %d %d %d\n", node, Val[node], L[node], R[node]); print(L[node]); print(R[node]); } static void printIdent(int node, int depth) { if (node == nil) return; printIdent(R[node], depth+4); for(int i = 0; i < depth; i++) System.out.printf(" "); System.out.printf("[%d %d]\n", node, Val[node]); //printIdent(R[node], depth+4); printIdent(L[node], depth+4); } } ====== Průchod do šířky ====== V grafech uvedených na této stránce určete vzdálenost z uzlu 0 do všech ostatních uzlů. Opakovaným voláním BFS určete vzdálenosti mezi každou dvojicí uzlů v těchto grafech.