Pokročilé programovací soustředění

Vede
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: Rozcvičky .

Středa 23.9. odpoledne

Práce s online vyhodnocovacím serverem

Navštivte Sphere Online Judge a zaregistrujete se. Seznam počátečních trénovacích úloh je zde: List of basics problems. Z nich vybíráme:


Č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: Grafy a stromy, Reprezentace grafu, Grafy

Úlohy : Kolo a 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 : 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: Průchod grafu

Úlohy : Průchod do šířky, navrhněte postup řešení pro CERC07K - Key Task nebo 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: Těžké problémy


Pondělí 28.9. dopoledne i odpoledne
Úterý 29.9. dopoledne i odpoledne

Dijkstrův algoritmus jako aplikace prioritní fronty:

10048 - Audiophobia

10099 - The Tourist Guide


Středa 30.9. dopoledne i odpoledne

Zdroje poučení

Jakub Černý: Základní grafové algoritmy, KAM MFF, 2010, online publikace.

Steven S. Skiena, Miguel A. Revilla: Programming Challenges (záložní link)

'Programátorské kuchařky z MFF UK'' kuchařky.

C++ priority queues

Java PriorityQueue


Zdroje úloh

  • Archiv úloh z regionálních i světových kol soutěží ACM Programming Contest ACM-ICPC Live Archive
  • Codechef obsahuje k nahlédnutí zdrojové kódy úspěšných řešitelů.
  • 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.

Nadstavba

Účast v ACM ICPC Maratonu: 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ň 2×2.

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.

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.

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

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 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 N = 100, N = 1000, N = 10000, N = 20000. Kontrola výsledků zde.

Trojúhelník

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.

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.

courses/a4b36acm2/2015_zs/main/lps.txt · Last modified: 2018/10/03 03:51 (external edit)