Zadání jsou řazena libovolně a jsou nekomentována, zadání je většinou samo krátké a přehledné.

• 218 - Moth Eradication .
• 10078 - The Art Gallery .
• 10678 - The Grazing Cow .
• 10691 - Subway .
• 11345 - Rectangles .
• 11355 - Cool Points .
• 102. GX Light Pipeline Inc .
• 149. Fencing in the Sheep .
• 187. Flat broken lines .
• 228. Shamans .
• 2056. Rectangular Polygon .
• 2901. One Geometry Problem .
• 3195. Doors and Penguins .
• 4061. Polygon .
• 4676 - Geometry Problem .

Zadání jsou pro jednoduchost řazena v klesajícím pořadí podle délky textu zadání.

• 579 - Clock Hands počítání úhlů
• 184 - Laser Lines rovnice přímky
• 11596 - Convex Orthogonal Polygon pravoúhlá manhattanská konvexita
• 4987. Goal for Raúl tečna ke kružnici
• 11646 - Athletics Track obvod obdélníka a kružnice
• 11639 - Guard the Land obsahy obdélníků
• 3678. Cattle Bruisers kvadratická (ne)rovnice
• 11702 - Meltdown vzdálenost bodu od úsečky
• 634 - Polygon bod uvnitř mnohoúhelníka, základní poučení zde: http://en.wikipedia.org/wiki/Point_in_polygon
• 11648 - Divide The Land plocha čtyřúhelníka
• 10387 - Billiard odstraňte stěny tak, že vydláždíte rovinu kopiemi stolu
• 4200. Hamster flight vrh šikmý, vzorečky zde: http://en.wikipedia.org/wiki/Projectile_motion
• 11579 - Triangle Trouble trojúhelníková nerovnost a např. Heronův vzorec
• 1431. Projections Of A Polygon vzdálenosti bodů od přímky
• 356 - Square Pegs And Round Holes souřadnice bodů na kružnici
• 11401 - Triangle Counting pouze trojúhelníková nerovnost

Sphere Online Judge

• The Shortest Path (Graphs) - Find shortest paths between pairs of cities.
  
• Feynman (Classical) - Find the number of squares in a NxN grid.
  
• A Game with Numbers (Games) - An easy problem from the game theory, yet it is not needed to solve this problem.
  
• Longest Path in a Tree (Graphs) - Well-known problem of finding the diameter of a tree.
  
• Is it a tree (Graphs) - Determine, whether the graph on the input is a tree.
  
• Marbles (Combinatorics) - Find out the number of ways to choose marbles given the requirements.
  
• Fibonnaci Sum (Maths) - Finding sum of consecutive terms in Fibonacci sequence in the given range.
  
• Penney Game (Classical) - Finding the number of occurences of particular coin toss sequences in a 40 tosses long sequence.
  
• Count on Cantor (Classical) - Telling what is the n-th rational number in the “Cantor's sequence”.
• Pouring Water (Classical) - Determine the least number of steps to acquire a given amount of water using 2 vessels.
• Labyrinth (Graphs) - The same as the problem - Longest Path in a Tree - but it is not as simple as that - you need to parse the input and build the tree.

2151 - Telescope
2219 - Domino Puzzle
2332 - Cube
2490 - Clock Synchronisation
2522 - Chocolate
2699 - Diamonds

Pěkná motivační úloha na úvod: Kings on the Chessboard
Řešení: kings_bruteforce.c, kings_dp.c, kings_graphs.c

1. Pro bojácné:
   • Crazy tea party (Hint: Tužka a Papír :)) - Ukázkové řešení v jazyce C
2. Pro mírně statečnější:
   • Factorial (Hint: Prvočíselný rozklad. Co tvoří 0 v zápisu čísla?) - Ukázkové řešení v jazyce C
   • Alphacode (Hint: Fibonacci?! Jednoduché DP: co takhle si pamatovat počet dekódovaní pro každý prefix zprávy a využít je pro vypočítání delších prefixů.) - Ukázkové řešení v jazyce C
3. Pro drakobijce:
   • Little Tiger vs. Deep Monkey (Hint: Malý rozsah součtů skóre! Subset Sum Problem. Pozor na rozsah hodnot standardních datových typů!) - Ukázkové řešení v jazyce C

V aktuální soutěži Vás čeká výběr úloh z dynamické programování. Úlohy tentokrát budete řešit pro odevzdávací systémy SPOJ a UVA.

DP on Trees:

• Three-coloring of binary trees
• Vertex Cover
• Trees Again
• UVA/Facing Problem With Trees

DP on Sequences:

• Black or White
• Catch Fish
• Aibohphobia
• Adjacent Bit Counts
• UVA/Wavio Sequence
• UVA/Menu

DP on Arrays:

• Farmer Sepp
• Finding Seats
• UVA/Paths through the Hourglass
• UVA/Buying Coke

Tiling Grids DP:

• Tiling a Grid With Dominoes
• Filchs Dilemna
• LATGACH3 (POZOR! Pro N == 0 je odpověď 1 )
• UVA/Colored Tiles
• UVA/Tiling

Základní a přifařené maličkosti a dovednosti – Je užitečné být familiární s většinou témat:

A. mathematics
B. data-structures
C. dynamic-programming
D. basic-graph-algorithms
E. shortest-path-algorithms
F. computational-geometry (Stačí konvexní obálka a zametací přímka)
G. combinatorial-games (Jako zajímavost na konci semestru)

Dynamické programování

Některé referenční implementace
Stanford ACM team

Přibližně návodná ukázka struktury prezentace: Voda v rourách
dp

Vyberte si libovolnou úlohu z některého okruhu, a řešte.

1. Regionals 2006 - Asia - Beijing
2. Regionals 2006 :: Asia - Dhaka

Postupně okruhy podle potřeby přibydou…