Užitečný server A2OJ je mimo provoz, oceníme každý nápad na jeho alespoň částečnou funkční náhradu.

Průběžný stav

Online dálková forma předmětu

(Starsi orientacni tabulka zde.)

V průběhu praktických cvičení a také při domácí aktivitě svá řešení budete odevzdávat do serverů

• Online Judge (dříve “UVa Online Judge”)
• Sphere Online Judge (neboli “SPOJ”)
• Live Archive (Úlohy z ACM soutěží)

Na každém z těchto serverů si zřiďte konto, pokud ho tam ještě nemáte.

Návodník na řešení

Proces lze vyzkoušet s hotovým řešením

Úlohy pro první seminář

1. 705 - Slash Maze
2. 10020 - Minimal coverage
3. 10132 - File Fragmentation
4. 10161 - Ant on a Chessboard
5. 11491 - Erasing and Winning
6. 11518 - Dominos 2
7. 11549 - Calculator Conundrum
8. 11572 - Unique Snowflakes
9. 12545 - Bits Equalizer
10. ADDREV - Adding Reversed Numbers
11. AE1B - Tables
12. AMR10G - Christmas Play
13. CANDY - Candy I
14. EMTY2 - Can You Make It Empty 2
15. FACEFRND - Friends of Friends
16. GERGOVIA - Wine trading in Gergovia
17. HANGOVER - Hangover
18. PERMUT2 - Ambiguous Permutations
19. SNGINT - Encode Integer
20. TOE1 - Tic-Tac-Toe ( I )

Plus trochu více:

21. 3595 - Linear Pachinko
22. 2061 - The Triangle Game

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

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

Řezání tyče
Cutting a rod

Ú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

Úlohy na dnešní minisoutěž

• https://www.spoj.com/problems/ACMAKER
• https://www.spoj.com/problems/ACODE
• https://www.spoj.com/problems/DCEPC501
• https://www.spoj.com/problems/MARTIAN
• https://www.spoj.com/problems/MIXTURES
• https://www.spoj.com/problems/ROCK
• https://www.spoj.com/problems/SCUBADIV
• https://www.spoj.com/problems/STONE2
• https://www.spoj.com/problems/TRIP
• https://www.spoj.com/problems/TWENDS

Semináře odpadají kvůli karanténě. Doporučenou náhradní činností je samostané řešení zbývajících úloh z 1. a 3. semináře. K nim je níže přídána další skupina úloh na DP. Řešení úloh doma mimo seminář je standardně hodnoceno 1 bodem za každou úspěšně vyřešenou úlohu.

• 1351 - String Compression
• 10029 - Edit Step Ladders
• 10069 - Distinct Subsequences
• 10934 - Dropping water balloons
• 11258 - String Partition
• 11420 - Chest of Drawers
• 11552 - Fewest Flops
• 11617 - An Odd Love
• 11790 - Murcia's Skyline

S využitím publikace Antti Laaksonen: Competitive Programmer’s Handbook, s několika komentáři.
Originál: ke stažení.

Nejkratší a nejdelší cesty:

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

Aplikace prohledávání do hloubky:

• Napřed vůbec DFS
• 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

• 125 - Numbering Paths
• 532 - Dungeon Master
• 534 - Frogger
• 558 - Wormholes
• 567 - Risk
• 572 - Oil Deposits
• 658 - It's not a Bug, it's a Feature!
• 10305 - Ordering Tasks
• 10459 - The Tree Root
• 10596 - Morning Walk
• 10608 - Friends
• 10672 - Marbles on a tree
• 10701 - Pre, in and post
• 10985 - Rings'n'Ropes
• 11686 - Pick up sticks
• SAMER08A - Almost Shortest Path

Minisoutěž proběhne od 16:15 do 20:15. (Jako vždy, kdo chce skončit dříve, může.)

Bodové hodnocení standardní – každá vyřešená úloha se počítá jako prezenčně vyřešená za 3 body.

Ulohy z Online (UVa) Judge je mozno v ramci minisouteze odevzdavat take behem patku 3.4. (do 24:00). Pritom pravidla bodovani jsou:

A. Pokud na berezovs@fel.cvut.cz do 21:00 ve ctvrtek poslete kod odevzdany do serveru pred 20:15 a upraveny kod bude akceptovan behem patku 3.4., bude reseni hodnoceno 3 body. Podminkou je dodatecne zaslani finalniho akceptovaneho kodu na stejnou adresu.

B. Kazdy dalsi kod akceptovany behem patku 3.4. bude hodnocen 2 body.

1. Zapisujte svoje výkony samostatně do Výsledkové tabulky.

2. Po ukončení pošlete otisky obrazovky serveru se záznamem Vašich vyřešených úloh na berezovs@fel.cvut.cz.

3. Úlohy k řešení

1. 1205 - Color a Tree
2. 10004 - Bicoloring
3. 10047 - The Monocycle
4. 10051 - Tower of Cubes
5. 10054 - The Necklace
6. 10067 - Playing with Wheels
7. 10099 - The Tourist Guide
8. 10369 - Arctic Network
9. 11561 - Getting Gold
10. 11573 - Ocean Currents
11. 11624 - Fire!
12. 315 - Network
13. 10276 - Hanoi Tower Troubles Again!
14. 10510 - Cactus

Úlohy 12., 13., 14. byly vybrány spíše pro náročnější řešitele .

Pokud neběží Online (UVA) judge, zkuste SPOJ:

• 15. https://www.spoj.com/problems/ELEVTRBL/
• 16. https://www.spoj.com/problems/CAM5/
• 17. https://www.spoj.com/problems/PT07Z/
• 18. https://www.spoj.com/problems/MICEMAZE/
• 19. https://www.spoj.com/problems/ANARC08G/
• 20. https://www.spoj.com/problems/WORDS1/
• 21. https://www.spoj.com/problems/SUBMERGE/

Minisoutěž proběhne od 16:15 do 20:15. (Jako vždy, kdo chce skončit dříve, může.)

1. Zapisujte svoje výkony samostatně do Výsledkové tabulky.

2. Po ukončení pošlete otisky obrazovky serveru se záznamem Vašich vyřešených úloh na berezovs@fel.cvut.cz.

3. Úlohy k řešení

1. 200 - Rare Order
2. 260 - Il Gioco dell'X
3. 610 - Street Directions
4. 784 - Maze Exploration
5. 10243 - Fire! Fire!! Fire!!!
6. 10278 - Fire Station
7. 10308 - Roads in the North
8. 10702 - Travelling Salesman
9. 11456 - Trainsorting
10. 11631 - Dark roads
11. 11709 - Trust groups
12. 11733 - Airports
13. 11770 - Lighting Away

• Habalova kombinatorická skripta!
• Z těchto skript tahák
• Prvočísla, Eratosthenovo síto a kód
• Modulární aritmetika (Převážně stejná jako ta běžná)
• Čí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/
• * 10213 - How Many Pieces of Land ? Eulerova formule V+F = E+2

Vyzkoušejte si:

• http://www.spoj.com/problems/AMR11E/
• http://www.spoj.com/problems/APS/
• http://www.spoj.com/problems/LCMSUM/
• https://www.spoj.com/problems/PTIME/
• 11408 - Count DePrimes

Další odkazy související s úlohami

Catalanova čísla
https://en.wikipedia.org/wiki/Catalan_number

Kombinační čísla
http://arantxa.ii.uam.es/~ssantini/writing/notes/s667_binomial.pdf
http://www.zweigmedia.com/RealWorld/tutstats/bincoeffs.html

Modulární mocnění
https://discuss.codechef.com/questions/20451/a-tutorial-on-fast-modulo-multiplication-exponential-squaring
https://en.wikipedia.org/wiki/Modular_exponentiation

Euklidův algoritmus (největší společný dělitel)
http://mathworld.wolfram.com/EuclideanAlgorithm.html

Prvočísla
http://www.geeksforgeeks.org/sieve-of-eratosthenes/

Minisoutěž proběhne od 16:15 do 20:15. (Jako vždy, kdo chce skončit dříve, může.)

1. Zapisujte svoje výkony samostatně do Výsledkové tabulky.

2. Po ukončení pošlete otisky obrazovky serveru se záznamem Vašich vyřešených úloh na berezovs@fel.cvut.cz.

3. Úlohy k řešení

1. 10110 - Light, more light
2. 10139 - Factovisors
3. 10229 - Modular Fibonacci
4. 10375 - Choose and divide
5. 10790 - How Many Points of Intersection?
6. 11069 - A Graph Problem
7. 11388 - GCD LCM
8. 11428 - Cubes
9. DIVSUM - Divisor Summation
10. FCDC - Factorial Modulo
11. HS08PAUL - A conjecture of Paul Erdos
12. LCMSUM - LCM Sum
13. MB1 - PP numbers
14. TREE1 - Tree
15. UCV2013A - Counting Ids

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

Very Brute force Binary Search: https://onlinejudge.org/external/105/10566.pdf

Sweep line example Touching rectangles

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

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 )

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

Minisoutěž proběhne od 16:15 do 20:15. (Jako vždy, kdo chce skončit dříve, může.)

1. Zapisujte svoje výkony samostatně do Výsledkové tabulky.

2. Po ukončení pošlete otisky obrazovky serveru se záznamem Vašich vyřešených úloh na berezovs@fel.cvut.cz.

3. Úlohy k řešení

1. ADAPICK - Ada and Cucumber
2. ANARC09F - Air Strike
3. BLMIRANA - Mayonnaise Arrow
4. BSHEEP - Build the Fence
5. CATTLEB - Cattle Bruisers
6. CHASE - A Chase In WonderLand
7. CONDUIT - I Conduit
8. DOORSPEN - Doors and Penguins
9. EQBOX - Equipment Box
10. GEOM - Geometry and a Square
11. GEOPROB - One Geometry Problem
12. GOALFR - Goal for Raúl
13. HAMSTER1 - Hamster flight
14. LEAF - Leaf
15. RROOT - REAL ROOTS

• 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? )
• Fibonacciho Nim

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.