Ranged Minimum Query

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

1. Seinfeld (easy)
   • Hraní se závorkami.
2. Tiles of Tetris, NOT! (easy)
   • Elementarní teorie čísel.
3. Not So Flat After All (easy)
   • Elementarní teorie čísel podruhé.
4. Probability One (cakewalk)
   • No comment…
5. Hop — Don't Walk! (medium)
   • Hledání ve stavovém prostoru.
6. Air Strike (medium)
   • Optimalni rozdeleni polomeru kruznic aby pokryly co nejvice bodu.
7. Stock Chase (easy)
   • No comment, podruhé…
8. Land Division (medium)
   • Rozdělení obdélníku na pruhy, tak aby distribuce bodů v pruhu byla blízká rovnoměrné.
9. Kind of a Blur (hard)
   • Rekonstrukce bitmapy z průměrovaných pixelů.

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

1. The Earth is Flat!
   • Elementary parsing. Recursion.
2. The Double HeLiX
   • Realize that the points of intersections are uniquely defined (sequences are increasing). This suggest some greedy strategy might work.
3. Alpha of Degree k
   • Variation of the game “slovní fotbal”. Imagine a graph over words where an (oriented) edge leads between two words iff one is “continuation” of the other according to defined alpha relation. The weight of the edge could be the degree of the alpha. Then, the task reduces to finding a path of length L from the starting word s to end word t, where the weigth of the edges on the path is at least as high as given k. The problem is that the idea should be more clever than that since building the graph could be too much time consuming.
4. Sort that Queue
   • Hard. Small input, possibly solvable by effective representation of the system as states and finding shortest path in it.
5. Still Johnny Can't Add
   • Overdetermined system of linear equation.
6. Newton's Apple
   • This is a well defined problem of finding whether two given rooted trees are isomorhpic. Try to figure out the details of this proposed algorithm: Traverse the tree (starting from the root) using DFS. When returning from a leaf return “[?]”, replace ? with the node's label. When you gather all “codes” of a node's sub-trees, sort them lexicographically and append the codes to make one long code denoted C, return the code for the current node as “[?C]”, where again ? is replaced with the node's label. When you compute the codes for both trees, it holds that the trees are isomorpic iff their codes are identical. This algorithm works for a general rooted trees, not only binary. The code of the 3 isomorphic trees in the example is: “[A[B[C][D[E]]][F[G]]]”, the one that is different has the code: “[A[B[C[E]][D]][F[G]]]” (clearly different).
7. The Euclidian Clock
   • Elementary geometry: calculate an area of a circular sector.
8. Chop Ahoy! Revisited!
   • The big constraints suggests a recursive solution.
9. What's your Logo?
   • Have you ever heard of this Euler's formula?
10. It's All About Three
    • All input numbers are less than a million, try to figure out an augmented version of the sieve of Eratosthenes that can solve this.

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.

Regionals 2002 - Latin America - South America
Regionals 2005 - Europe - Southwestern
Regionals 2007 - Europe - Northwestern
Regionals 2004 - South Pacific
Regionals 2010 - Asia - Amritapuri