Místo a čas konání

Místo: T2:C2-84, čas: čtvrtek od 16:15. Rozvrh FEL

TABULKA -- Celkový stav

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ěží) (aktuálně neaktivní – uvidíme, zda se rozběhne)

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í

Vyzkoušejte si:

Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady “začínající” nezískají body.
Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady.

Svoje výkony zapisujte samostatně do tabulky
Výkony v minisoutěži I,
po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz.

Začínající zkusí

(Upozornění: Úlohy níže jsou řazeny abecedně podle svých názvů, což nesouvisí s jejich tématikou, obtížností nebo jinými parametry.)

1. 102 - Ecological Bin Packing
2. 121 - Pipe Fitters
3. 10038 - Jolly Jumpers
4. 10783 - Odd Sum
5. 11044 - Searching for Nessy
6. BUSYMAN - I AM VERY BUSY
7. GERGOVIA - Wine trading in Gergovia
8. HOTELS - Hotels Along the Croatian Coast
9. PERMUT2 - Ambiguous Permutations
10. SHP - Shuffling Problem

pokročilí nebo začínající zkusí

1. 307 - Sticks
2. 254 - Towers of Hanoi
3. 10049 - Self-describing Sequence
4. 11572 - Unique Snowflakes
5. AE1B - Tables
6. AGGRCOW - Aggressive cows
7. EMTY2 - Can You Make It Empty 2
8. FACEFRND - Friends of Friends
9. HANGOVER - Hangover
10. RRSCHED - Round-Robin Scheduling

Komentáře k minulým úlohám.

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

Doporučené úvodní přehledové a úctyhodné publikace, asi nejpřístupněji napsané:

• Laaksonen: Competitive Programmer’s Handbook
• Mareš, Valla: Průvodce labyrintem algoritmů

Jednotlivé metody:

• Základní všechno možné průchodem 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

• Násobení Matic: https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/
• Řezání tyče: https://www.geeksforgeeks.org/cutting-a-rod-dp-13/
• Nejdelší společná podposloupnost (LCS): https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/
• Online výpočet LCS: https://www.cs.usfca.edu/~galles/visualization/DPLCS.html
• Úloha batohu 0/1: https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/
• Úloha batohu neomezená: https://www.geeksforgeeks.org/unbounded-knapsack-repetition-items-allowed/

• batoh01
• LCS Nejdelsi spolecna podposloupnost
• nasobeni matic

Úlohy pro rozmyšlení

147 - Dollars (2D Tab)
10066 - The Twin Towers (LCS)
11432 - Busy Programmer
PT07X - Vertex Cover
M3TILE - LATGACH3
SQRBR - Square Brackets
116 - Unidirectional TSP
11137 - Ingenuous Cubrency

https://www.geeksforgeeks.org/painting-fence-algorithm/

https://leetcode.com/problems/perfect-squares/

Svoje výkony zapisujte samostatně do tabulky Výkony v minisoutěži II,
po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz.

Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady “začínající” nezískají body.
Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady.

Začínající zkusí

1. 437 - The Tower of Babylon
2. 825 - Walking on the Safe Side
3. 10285 - Longest Run on a Snowboard
4. 10334 - Ray Through Glasses
5. 10564 - Paths through the Hourglass
6. 10599 - Robots(II)
7. 10862 - Connect the Cable Wires
8. 11407 - Squares
9. BYTESM2 - Philosophers Stone
10. DIEHARD - DIE HARD

pokročilí nebo začínající zkusí

1. 839 - Not so Mobile
2. 882 - The Mailbox Manufacturers
3. 10036 - Divisibility
4. 10559 - Blocks
5. 10913 - Walking on a Grid
6. 11003 - Boxes
7. 11654 - Arithmetic Subsequence
8. ABA12C - Buying Apples!
9. AE2A - Dice
10. MENU - Menu

Především BFS, DFS, Dijkstra, odkazy viz níže.

Nejkratší a nejdelší cesty:

• nejkratší a nejdelší cesty -- celkový přehled
• nejkratší a nejdelší cesty v DAG (Prakticky jde o DP.)

Dijkstra v O(n^2)

Cesty v stromech (nejdelší, nejkratší i jiné) bývají řešitelné pomocí DP,
to jest zakořeněním stromu a aplikací postorder průchodu stromem.

• https://www.geeksforgeeks.org/dynamic-programming-trees-set-1/

Aplikace prohledávání do hloubky:

• Napřed ukázka DFS za běhu
• statický přehled
• 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

Negativní cykly:

• Bellman-Ford

Cesty mezi všemi páry uzlů:

• Floyd-Warshall
• Floyd-Warshall algorithm example

Další vizualizace

Dalších 200+ ukázek a úloh:

• Graph Data Structure And Algorithms

Svoje výkony zapisujte samostatně do tabulky Výkony v minisoutěži III,
po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz.

Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady “začínající” nezískají body.
Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady.

Začínající zkusí

1. 784 - Maze Exploration
2. 821 - Page Hopping
3. 11049 - Basic wall maze
4. 11396 - Claw Decomposition
5. 12582 - Wedding of Sultan
6. ACPC10D - Tri graphs
7. ALL IZZ WELL
8. BENEFACT - The Benefactor
9. BITMAP - Bitmap
10. ELEVTRBL - Elevator Trouble

pokročilí nebo začínající zkusí

1. 985 - Round and Round Maze
2. 1198 - The Geodetic Set Problem
3. 11833 - Route Change
4. 12661 - Funny Car Racing
5. 11686 - Pick up sticks
6. 11770 - Lighting Away
7. CAM5 - prayatna PR
8. CERC07K - Key Task
9. SAMER08A - Almost Shortest Path
10. WATER - Water among Cubes

• 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á)
• Sčítání čísel (aritmeticko-geometrická posloupnost)
• Čí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
• Příklad nezbytného předpočítání Arrays/CTU Open 2022

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

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

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

Svoje výkony zapisujte samostatně do tabulky Výkony v minisoutěži IV,
po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz.

Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady “začínající” nezískají body.
Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady.

Začínající zkusí

1. 543 - Goldbach's Conjecture
2. 993 - Product of digits
3. 10229 - Modular Fibonacci
4. 10533 - Digit Primes
5. 11388 - GCD LCM
6. BALLSUM - Ball sum
7. GUANGGUN - 111…1 Squared
8. MARBLES - Marbles
9. MB1 - PP numbers
10. UCV2013A - Counting Ids

pokročilí nebo začínající zkusí

1. 343 - What Base Is This?
2. 884 - Factorial Factors
3. 914 - Jumping Champion
4. 10820 - Send a Table
5. 11296 - Counting Solutions to an Integral Equation
6. 11347 - Multifactorials
7. 11609 - Teams
8. BINSTIRL - Binary Stirling Numbers
9. SUMMATION - SUMMATION
10. 11038 - How Many O's? (náhrada za nefunkční ZCR níže)
11. ZCR - Zen And His Crush (vyhodnocení nefunguje, řešení pošlete na berezovs@fel.cvut.cz)

Determinant matice, většinou stačí 2×2.

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

Počítání průsečíků Soustava lin. rovnic, Cramerovo pravidlo

Jednoduchá aplikace 438 - The Circumference of the Circle, 10335 - Ray Inside a Polygon

Poloha bodu a polygonu (Hack: místo paprsku může postačit dostatečně dlouhá úsečka)

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 (ICPC Live Archive | Regionals 2017 | Europe-Northwestern), solution idea

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

Kreslítko GeoGebra online https://www.geogebra.org/classic (http://www.geogebra.org/ ??) (začni variantou “classic”).

Zkuste samostatně:

10263 - Railway
10180 - Rope Crisis in Ropeland!

Svoje výkony zapisujte samostatně do tabulky Výkony v minisoutěži V,
po skončení minisoutěže v 19:30, posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz.

Posluchači, kteří již dříve ACM seminář absolvovali, se soustředí především na sadu pokročilou níže, za úlohy ze sady “začínající” nezískají body.
Naopak ti, kteří jsou na ACM poprvé, mohou řešit úlohy z obou sad, body získají za každou vyřešenou úlohu z kterékoli sady.

Začínající zkusí

1. 184 - Laser Lines
2. 737 - Gleaming the Cubes
3. 10060 - A hole to catch a man
4. 10078 - The Art Gallery
5. 11096 - Nails
6. 11207 - The easiest way
7. 11232 - Cylinder
8. 11834 - Elevator
9. EQBOX - Equipment Box
10. VMILI - Military Story

pokročilí nebo začínající zkusí

1. 920 - Sunny Mountains
2. 10577 - Bounding box
3. 10585 - Center of symmetry
4. 11355 - Cool Points
5. 11343 - Isolated Segments
6. 11473 - Campus Roads
7. ADAPICK - Ada and Cucumber
8. GEOPROB - One Geometry Problem
9. GOALFR - Goal for Raúl
10. HAMSTER1 - Hamster flight

• Interní opáčko -- 18. přednáška z LGR
• Všeobecné poučení o hrách a Nimu (výtah, česky)
• Přehled na MIT
• 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
• Zkuste si nim online: Jefferson Lab, Archimedes Lab

Příklady:

• Bachet's Game
• Chomp
• Euclid's Game
• The Game
• Integer Game
• Matrix 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.