Seminář | Datum (hodiny) | Náplň | Úlohy/odkazy |
---|---|---|---|
1. | 20.2. (4) | úvod, seznámení, nácvik soutěže | Regionální kolo v Praze 2007 Regionální kolo v Praze 2011 |
2. | 27.2. (2) | Prezentují | Úloha |
1. Papoušek, Cvrček | Phone cell Nesnadné na rychlé vysvětlení! | ||
2. Tušla, Špatný | The Grille, jde o max. rychlost! Neřadit ! | ||
3. Drbohlav, Žaitlík | Rectangular polygons Porovnej implementace! | ||
3. | 6.3. (4) | Minisoutěž | Regionals 2007 - Southwestern Europe Regionals 2003 - North America - East Central NA |
4. | 13.3. (2) | Prezentují | Úloha |
1. Létal, Dendis | Prester John | ||
2. Topor, Furtuna | The Bridges of Kölsberg Jako NSP! (LCS in English) | ||
3. Chamra, Hořeňovský | EKG sequence Složitost log(log(n)). | ||
5. | 20.3. (4) | Minisoutěž | Regionals 2004 - North America - Mid-Central USA Regionals 2009 - Africa/Middle East - Africa and Arab Komentáře k zadáním viz níže zde na stránce. |
6. | 27.3. (2) | Prezentují | Úloha |
1. Kalivoda, Chvojka | Air Strike | ||
2. Matějka, Lantora | Hop --- Don't Walk! | ||
3. … | … | ||
7. | 3.4. (4) | Minisoutěž | Regionals 2005 - North America - Rocky Mountain Regionals 2007 - North America - Rocky Mountain Komentáře k zadáním viz níže zde na stránce. |
8. | 10.4. (2) | Prezentují | Úloha |
1. Špatný, Tušla | 3821 - Tree Grafting | ||
2. Furtuna, Topor | 3344 - Suit Distribution | ||
3. Chamra, Hořeňovský | 3341 - Smallest Difference | ||
9. | 17.4. (4) | Minisoutěž | Regionals 2005 - Africa/Middle East - Arab and North Africa Regionals 2008 - North America - Southeast USA |
10. | 24.4 (2) | Prezentují | Úloha |
1. Dendis, Létal | Dluží | ||
2. Lantora, Matějka | Dluží | ||
3. Cvrček, Papoušek | Odpadli | ||
11. | 29.4. (4) | Minisoutěž | Regionals 2001 - Europe - Southeastern Regionals 2001 - Europe - Southwestern |
12. | 8.5. (-) | Odpadá | … |
13. | 15.5 (4) | Minisoutěž Podle dohody | Regionals 2006 - Africa/Middle East - Arab and North Africa Regionals 2002 - Europe - Southwestern |
14. | 22.5. (2) | Podle potřeby Podle dohody | Úloha pro znalé: Playing With Stones |
… | LS 2014 | Průběžný stav | Tabulka |
Seznamovací kolo v 1. semináři
Projděte zadání úloh dvou uvedených regionálních kol ACM soutěže a ke každému navrhněte alespoň rámcový postup řešení, nebo jeho návrh, stačí dva až tři řádky textu, případně s odkazem na vhodný standardní algoritmus apod. Pokud vám úloha připadá, že je aktuálně mimo vaše řešitelské možnosti, poznamenejte si to také. Tentokrát ještě nekódujte, jde o seznámení s prostředím a charakterem úloh, věnujte čas na co nejlepší rozmyšlení svých návrhů řešení.
Seminář 20. 3.
Poznámky k soutěži Regionals 2004 - North America - Mid-Central USA
3053 - Primary X-Subfactor Series Není tu zřejmá žádná číselně-teoretická “chytrost”, takže nejspíše pomůže hrubá síla v podobě rekurzivního zkracování daného číselného řetězce.
3054 - Triangle Cuts - Ze čtyř trojůhelníků máme složit předepsaný jeden trojúhelník, to jest dejme ty čtyři k sobě a otáčejme každým z nich. Až budou přesně lícovat, vznikne ten předepsaný. Stačí pracovat s úhly a připravit si cyklus pro 24 permutace 4 trojúhelníků.
3055 - Symmetric Order Změňte pořadí 1, 2, 3, 4, 5, 6, .., n na pořadí 1, 3, 5…, n, …., 6, 4, 2.
3056 - Flow Layout Vyplňte obdélník jinými obdélníky, ale v předepsaném pořadí, takže uloha se zužuje na jeden cyklus for s cca 4 parametry: Výšky, šířky, aktuální výšky a aktuální šířky.
3057 - Permutation Code Výpočet pomocí opakované aplikace xor: Je nutno prokousat se zadáním a pak ho překlopit do kódu. Také je vhodné využít fakt, že (a xor b) xor b = a.
3058 - Ink Blots Redukce na rovinný graf. Každý průsečík dvou kružnic bude uzel, z oblouků mezi nimi budou úsečky a to budou hrany grafu. Počet všech bílých stěn = počet všech stěn - počet šedých stěn. Pro počet stěn rovinného grafu platí famózní Eulerova formule: Hran + 2 = Stěn + Uzlů.
3059 - Speed Limit Fyzikální kinematika, postupné součty. Cyklus for se bude hodit. Relativně přístupná úloha vhodná jako povzbuzení pro začátečníky.
Poznámky k soutěži Regionals 2009 - Africa/Middle East - Africa and Arab
Seminář 3. 4.
Poznámky k soutěži Regionals 2005 - North America - Rocky Mountain
3336 - Tire Dimensions Tuto úlohu neřešte, doba, kdy pro vás byla vhodná, je dávno pryč.
3337 - Random Walk Zkuste řešení v čase Theta(n * log(n)). Seřaďte vektory ne podle jejich souřadnic, ale podle …
3338 - Paint Mix Něco z elementární pravděpodobnosti. Násobení se tu může hodit.
3339 - Open and Close Programujte grafické operace s obrázky. Více práce, ale zato jen mechanické.
3340 - Hour Glass Sestavte vhodný orientovaný graf a v něm hledejte nejkratší cestu. Co budou uzly grafu?
3341 - Smallest Difference Základní kombinatorika, ale nutno postupovat pečlivě. Ostřejší řešitelé zkusí výsledky kompletně předpočítat, možností je jen 511.
3342 - Faulty Odometer Vypadá to jako devítková soustava, ale není to devítková soustava. Nebo ano? Nebo ne? Kdo poradí?
3343 - Last Digits Obyčejné počítání modulo, ale s velkými čísly, většími než např. Googolplex, ale zas ne o moc ve s rovnání např. s Grahamovým číslem. V Knuthově šipkové notaci nejvýše 100 ↑↑ 100.
3344 - Suit Distribution Rozdávání karet. Tohle je spíše odvození vhodné formulky než dlouhé programování.
Poznámky k soutěži Regionals 2007 - North America - Rocky Mountain
Problem A: Tree Grafting - Think about it recursivelly. The computation should not change dramatically by the tree conversion.
Problem C: Server Relocation - Paths in graphs. Keep in mind the floating-point precision!
Problem D: Coin Toss - Basic probability theory, not much to be said.
Problem E: Vacation Rentals - Paths in graphs.
Problem F: Baseball - Easy, painful, and prone to presentation errors. In case you opt for this one, be sure you read the problem description carefully!
Problem G: Team Work - Small input values! If you do not come out with something really clever, brute force it :)!
Problem I: Elementary Additions - Warm-up (for some painful) exercise, for its simplicity almost not being considered for grading.
WARNING: The following problems are not graded because they are too easy to be considered seriously.
Problem B: Look and Say
Problem H: Wavelet Compression
Poznámky k soutěži Regionals 2005 - Africa/Middle East - Arab and North Africa
Poznámky k soutěži Regionals 2008 - North America - Southeast USA
Z cvičných důvodů pro zájemce zůstává tento druhý soubor úloh nekomentovaný.
Poznámky k soutěži Regionals 2001 - Europe - Southeastern
2273 - Optimal Polynom
Min sum(a_i*K^i), K given. Recursion with pruning start at max degree, maybe some additional math helps.
2274 - Soldiers Min no of bubblesort swaps in array of 0 and 1. O(n).
2275 - Secret Numbers A knows x*y, B knows x+y, find x, y, elementary math, divisibility.
2276 - Typography Cheapest path in directed weighted graph seem to be a DAG, standard.
2277 - Permutation Characteristic vector of permutation: chi(i) = sgn(p[i]-p[i+1]), find number of all permutations with the same characteristic vector as the input perm. Probably recursive generation?
2278 - Find a number Given list S of int, k > 0, find p within 10% of m, m is biggest sum of some subset of S, m ⇐ k.
2279 - Counterfeit Coins Find a bogus coin, set of weigthing results is given, other coins are all the same weight. Complexity O(|coins| *no of weightings)??
2280 - Computer Game Standard text search, implementation Q: which alg is both easy to write AND fast?
Poznámky k soutěži Regionals 2001 - Europe - Southwestern
2425 - Mice and Maze Plain BFS?
2426 - Multiple Morse Matches Morse code to text using dictionary. Consider recursion?
2427 - Maya Calendar elementary arithmetic, calendar computations.
2428 - Water Shortage Sort floors and tops of water containers, will it help?
2429 - Puzzle Unknown graph is a polygon with non crossing diagonals, reconstruct it from list of edges only. O(|E|).
2430 - Reliable Programs Add minimum number of edges to directed graph so that from each node there are at least two independent paths to a fixed given vertex. Complexity?
2431 - Binary Stirling Numbers Parity of Stirling numbers, recursion to DP table.
2432 - Project File Dependencies Topological order of DAG.
2433 - No Change a[i] (i <6) given, express X as sum of k[i]*a[i] where k[i] > k[i] if a[i] > a[j], all k[i] have to be found, all are integers > 0, consider recursion.
Contest: Regionals 2006 - Africa/Middle East - Arab and North Africa
Velice jednoduché úlohy, které nepotřebují komentář. Algoritmicky a teoreticky zajímavé úlohy jsou pouze dvě, a to Johnny Hates Number Theory a A-to-Z. Kde u druhé jmenované hrozí nebezpečí “nekvalitních testovacích dat” (viz. žlutý marker u úlohy).
Regionals 2002 - Europe - Southwestern
2667 - Solitaire BFS in possibly large graph, consider coding game board by 64bit int or some similar trick.
2679 - Left Labyrinths Simulate walk through the labyrinth, seems to require no graph search.
2680 - Crazy Search You may try to employ a dictionary automaton, Theta(N*|text|).
2663 - Intervals Greedy approach, sort intervals by left endpoints and scan from left to right.
2662 - Family DAG processing, only be careful with probabilities.
2668 - Timetable Dijkstra can be modified to process the time intervals between the vertices.
2684 - Word Puzzles Text search once more, reverse words and search in 4 directions, use dictionary automaton?
2685 - Water Treatment Plants Simple DP, no more comment should be necessary.
2666 - Servers Looks like some variant of BFS from each vertex.