…

V průběhu praktických cvičení (sudé výukové týdny) svá řešení budete odevzdávat do A2 Online Judge. Prosíme, vytvořte si každý svůj vlastní účet sledováním následujícího linku: Sign Up. Vzhledem k tomu, že A2 Online Judge je pouze tzv. agregátor výsledků, musíte si vytvořit účty v příslušných judgích, které skutečně ověřují správnost vašich řešení, a to: Sphere Online Judge, UVa Online Judge a ACM-ICPC Live Archive.

Aby A2OJ věděl o odevzdaných úlohách, musíte vyplnit ve svém profilu ID, které jste si vytvořili či vám bylo přiděleno u výše uvedených judgů. Zde je shrnut postup, jak se k nim dostat:

1. Neuvěřitelné, ale login je vaše ID.

1. V hlavním menu po přihlášení ťukněte na [My Account]
2. Ve vašem profilu na řádku Online Judge ID: je Vaše UVA ID.

• Odevzdejte libovolnou úlohu (klidně prázný soubor).
• Přejděte na stránku Live Archive: Posledních 50 Odevzdání
• Najděte řádku přislušící vaší odevzdané úloze a klikněte na své uživatelské jméno.
• V parametrech URL naleznete své userid.

Po vytvoření účtů se můžete registrovat do soutěže na A2 Online Judge, odkaz většinou bývá nahoře v tabulce u aktuálního data nebo si soutěž vyhledejte samostatně na A2oj.

Návodník na řešení

Ukázky typických postupů a úloh.

• Základní všechno možné průchodem DAG
• Ukázka kódu -- manipulace s DAG
• Ukázka řešení -- Voda v rourách
• LIS - nejdelší rostoucí podposloupnost v čase O(N log N)
• LIS na GeeksforGeeks
• Ukázka kódu -- manipulace s DAG

• 900 - Brick Wall Patterns
• 10081 - Tight Words
• FARIDA - Princess Farida
• 10334 - Ray Through Glasses
• MMAXPER, Rectangles Perimeter - max upper envelope length
• Many Paths, One Destination
• Subsequence Problem
• Tower of Babylon
• Wachovia Bank
• Catch Fish
• Bribe the Prisoners
• Black or White

• 10261 - Ferry Loading
• The Islands
• Chocolate Box
• Two Ends
• Menu
• Fibonacci Words

Nejdelší společná podposloupnost (LIS - Longest Common Subsequence)
Výklad na GeeksForGeeks

Úlohy
UVA -- 10192 - Vacation
UVA -- 10066 - The Twin Towers
SPOJ -- AIBOHP - Aibohphobia
SPOJ -- ADFRUITS - Advanced Fruits

Problém batohu (Knapsack Problem)
Ukázka 0-1 varianty na GeeksForGeeks
Ukázka neomezené varianty na GeeksForGeeks

Úlohy
UVA -- 562 - Dividing coins
UVA -- 990 - Diving for Gold
UVA -- 10819 - Trouble of 13-Dots
SPOJ -- PIGBANK - Piggy-Bank

Čtěte průvodce: Průvodce labyrintem algoritmů

Nejkratší a nejdelší cesty:

• nejkratší a nejdelší cesty -- celkový přehled
• nejkratší a nejdelší cesty v DAG

Aplikace prohledávání do hloubky:

• topsort by DFS
• Detekce cyklu v grafu
• Nalezení topologického uspořádání vrcholů v grafu
• Identifikace mostů. (*_*_*)
• Identifikace artikulací (*_*_*)
• Detekce bloků, tj. 2-souvislých komponent
• Nalezení silně souvislých komponent

Poznámky k minimálním kostrám

Všechny cesty:

• Bellman-Ford
• Floyd-Warshall
• Floyd-Warshall algorithm example

další vizualizace

• 10410 - Tree Reconstruction
• 10672 - Marbles on a tree
• 10985 - Rings'n'Ropes
• 11396 - Claw Decomposition
• 11393 - Tri-Isomorphism
• 11545 - Avoiding Jungle in the Dark
• 11987 - Almost Union-Find

• Habalova kombinatorická skripta!
• Prvočísla, Eratosthenovo síto a kód
• Čísla různých druhu:
  • Kombinační
  • Fibonacciho
  • Catalanova , na Mathworld
  • OEIS Vynikající všeobecná referenční příručka The On-Line Encyclopedia of Integer Sequences
• Rychlé mocnění
  • https://www.geeksforgeeks.org/exponential-squaring-fast-modulo-multiplication/
  • https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/

Ilustrační úlohy

• 993 - Product of digits
• 10375 - Choose and divide
• 10235 - Simply Emirp
• 11287 - Pseudoprime Numbers

Úlohy mírně navíc:

• 294 - Divisors
• 10079 - Pizza Cutting
• 10299 - Relatives
• 10820 - Send a Table
• 11246 - K-Multiple Free set

Některé základní výpočty

Počítání průsečíků

Reminder: Trigonometric identities

Pick's_theorem http://jwilson.coe.uga.edu/emat6680fa05/schultz/6690/pick/pick_main.htm

Všeobecný přehled na MFF (Programátorské kuchařky) http://ksp.mff.cuni.cz/tasks/24/cook5.html

Polygon area example: https://www.mathsisfun.com/geometry/area-irregular-polygons.html, code: http://www.codeproject.com/Articles/13467/A-JavaScript-Implementation-of-the-Surveyor-s-Form

Sweep line example Touching rectangles

Graham Scan demo: http://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/ah/GrahamScan.html (enable java?)
code: http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
Stanford examples: http://web.stanford.edu/class/cs97si/ (Namely: http://web.stanford.edu/class/cs97si/09-computational-geometry.pdf )

Sweep line rotates:, http://www.spoj.com/problems/CERC07C/ (*_*_*) komentář

Rotate points instead of lines 8258 - Glyph Recognition ( solution idea)

Množství komentovaných základních kódů https://www.geeksforgeeks.org/geometric-algorithms/

Kreslítko GeoGebra online http://www.geogebra.org/

Seznamy geometrických kreslítek https://en.wikipedia.org/wiki/List_of_interactive_geometry_software#2D_programs, http://mathforum.org/geometry/geometry.software.html

Něco navíc:

• 155 - All Squares
• 858 - Berry Picking
• 10005 - Packing polygons
• 10245 - The Closest Pair Problem
• 10316 - Airline Hub

• Všeobecné poučení o hrách a Nimu (výtah, česky)
• TopCoder - The Basic Introduction into Games
• Jádro grafu
• Teorie her na CMU - Combinatorial Game Theory,Even More Games
• Kombinatorické hry - krátká ilustrace pdf.
• Nimbers (Sprague-Grundyho čísla) - ukázková úloha ( Socializing Game around Pizza, kód? )

Příklady:

• Bachet's Game
• Chomp
• Euclid's Game
• The Game
• Integer Game
• Matrix Game
• Game
• TRIVIADOR
• Playing With Stones
• M&M Game
• A Game with Numbers
• Play with a Tree: How to tackle a problem of this sort was not covered in the lecture, but if you are interested, see Ferguson's Game Theory (lecture 6, specifically, the colon and fusion principles).
• Black and White Nim: Difficult, yet intriguing problem.

Něco navíc:

• 10111 - Find the Winning Move
• 11311 - Exclusively Edible
• 11534 - Say Goodbye to Tic-Tac-Toe

Úlohy do minisoutěže:

1. 116 - Unidirectional TSP
2. 121 - Pipe Fitters
3. 201 - Squares
4. 254 - Towers of Hanoi
5. 839 - Not so Mobile
6. 861 - Little Bishops
7. 10305 - Ordering Tasks
8. 10696 - f91
9. 10704 - Traffic!
10. 10862 - Connect the Cable Wires
11. 10954 - Add All
12. 11049 - Basic wall maze
13. 11195 - Another n-Queen
14. 11232 - Cylinder
15. 11995 - I Can Guess the Data Structure!