Na první seminář použijte v brute vygenerovaný odkaz na BBB konferenci

https://cw.felk.cvut.cz/brute/student/bbb/cw_nUYiAZZosh

Rozhraní A2OJ nefungovalo, udělali jsme offline google tabulku s výkony jednotlivců,
pokud jste je ještě nezapsali, tak zapište svoje vykony sem.

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

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, klikněte na odkaz nahoře v prvním řádku tabulky.

• 299 - Train Swapping
• 579 - Clock Hands
• 10132 - File Fragmentation
• 10387 - Billiard
• 11520 - Fill the Square
• AE00 - Rectangles
• AE1B - Tables
• AMR10G - Christmas Play
• BYTESE2 - The Great Ball
• SHP - Shuffling Problem
• TEST - Life, the Universe, and Everythin

Online: Připojte se do konference:https://cw.felk.cvut.cz/brute/student/bbb/cw_zvuhVQ3J5w

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.

Vyberte si sadu podle svého zaměření, můžete také mixovat úlohy z obou sad:

Sada pro začínající

1. 120 - Stacks of Flapjacks
2. 189 - Mobile Casanova
3. 11150 - Cola
4. 11572 - Unique Snowflakes
5. ATOMS - Atoms in the Lab
6. BUSYMAN - I AM VERY BUSY
7. CRAN02 - Roommate Agreement
8. EXPEDI - Expedition
9. FCTRL - Factorial
10. GOO - Game Of Ones

Sada pro pokročilce

1. 307 - Sticks
2. 254 - Towers of Hanoi
3. 10012 - How Big Is It?
4. 10049 - Self-describing Sequence
5. 11039 - Building designing
6. 10079 - Pizza Cutting
7. ABCD - Colours A, B, C, D
8. AGGRCOW - Aggressive cows
9. BTCK - A problem of Backtracking
10. https://www.spoj.com/problems/SNGINT/SNGINT - Encode Integer

Online1: Připojte se do konference: https://cw.felk.cvut.cz/brute/bbb.php?join=cw_pc9e6Bo1az

Online2: Pokud by se nedařilo v Online1, v brute je na 16:10 naplánována záložní konference v předmětu ACM_ALL (pozor, nikoli ACM1 - ACM5). Brute mi hlásí, že odmítá posílat pozvánku komukoli na tuto konferenci v době jejího začátku (??). Zkuste adresu https://cw.felk.cvut.cz/brute/student/bbb/cw_7JCHpDhqMS.

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

Online: Připojte se do konference: https://cw.felk.cvut.cz/brute/student/bbb/cw_iiBLJ6px5n

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.

Vyberte si sadu podle svého zaměření, můžete také mixovat úlohy z obou sad:

Sada pro začínající

1. 147 - Dollars
2. 10036 - Divisibility
3. 10313 - Pay the Price
4. 10721- Bar codes
5. 10912 - Simple Minded Hashing
6. 10943 - How do you add?
7. 11137 - Ingenuous Cubrency
8. 11240 - Antimonotonicity
9. 11407 - Squares
10. SQRBR - Square Brackets

Sada pro pokročilce

1. 231 - Testing the CATCHER
2. 882 - The Mailbox Manufacturers
3. 10066 - The Twin Towers
4. 10559 - Blocks
5. 10910 - Marks Distribution
6. 10913 - Walking on a Grid
7. 11003 - Boxes
8. 11654 - Arithmetic Subsequence
9. ANARC07G - Let go to the movies
10. PT07X - Vertex Cover

Spojen výjimečně s následujícím seminářem. A jinak:

• 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
• Voda v rourach

Svoje výkony zapisujte samostatně do tabulky Výkony v minisoutěži III,

Kvůli časovému posunu bude 3 body hodnocena každá úloha odevzdaná do večera (23.59.) pátku 30.10: Posílejte otisky obrazovek z jednotlivých serverů s registrací vašich úspěchů na berezovs@fel.cvut.cz.

Vyberte si sadu podle svého zaměření, můžete také mixovat úlohy z obou sad:

Sada pro začínající

1. 10261 - Ferry Loading
2. 10280 - Old Wine Into New Bottles
3. 10626 - Buying Coke
4. 11069 - A Graph Problem
5. 11258 - String Partition
6. 11569 - Lovely Hint
7. BYTESM2 - Philosophers Stone
8. FOODIE - FOODIE
9. PIGBANK - Piggy-Bank
10. SQRBR - Square Brackets

Sada pro pokročilce

1. 839 - Not so Mobile
2. 995 - Super Divisible Numbers
3. 11081 - Strings
4. 11617 - An Odd Love
5. 11691 - Allergy Test
6. AE2A - Dice
7. ABA12C - Buying Apples!
8. GNYR09F - Adjacent Bit Counts
9. JEDNAKOS - JEDNAKOST
10. MENU - Menu

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

Dijkstra v O(n^2)

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

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.

Vyberte si sadu podle svého zaměření, můžete také mixovat úlohy z obou sad:

Sada pro začínající

1. 103 - Stacking Boxes
2. 572 - Oil Deposits
3. 784 - Maze Exploration
4. 10201 - Adventures in Moving - Part IV
5. 10259 - Hippity Hopscotch
6. 11049 - Basic wall maze
7. 11331 - The Joys of Farming
8. 11396 - Claw Decomposition
9. 11573 - Ocean Currents
10. LABYR1 - Labyrinth

Sada pro pokročilce

1. 315 - Network
2. 985 - Round and Round Maze
3. 10397 - Connect the Campus
4. 10047 - The Monocycle
5. 10510 - Cactus
6. 10672 - Marbles on a tree
7. 10704 - Traffic!
8. 11545 - Avoiding Jungle in the Dark
9. 11770 - Lighting Away
10. SAMER08A - Almost Shortest Path

• 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

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 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.

Vyberte si sadu podle svého zaměření, můžete také mixovat úlohy z obou sad:

Sada pro začínající

1. 369 - Combinations
2. 543 - Goldbach's Conjecture
3. 991 - Safe Salutations
4. 10533 - Digit Primes
5. 10699 - Count the factors
6. 11371 - Number Theory for Newbies
7. DIVSUM - Divisor Summation
8. GUANGGUN - 111…1 Squared
9. MB1 - PP numbers
10. MMFLPDIV - Least prime divisor

Sada pro pokročilce

1. 10006 - Carmichael Numbers
2. 10098 - Generating Fast
3. 10127 - Ones
4. 10277 - Boastin' Red Socks
5. 10491 - Cows and Cars
6. 10759 - Dice Throwing
7. 11344 - The Huge One
8. APS - Amazing Prime Sequence
9. BINSTIRL - Binary Stirling Numbers
10. CUBEFR - Cube Free Numbers

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 https://www.geogebra.org/graphing?lang=en (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

Svoje výkony zapisujte samostatně do tabulky Výkony v minisoutěži VI,

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.

Vyberte si sadu podle svého zaměření, můžete také mixovat úlohy z obou sad:

Sada pro začínající

• 438 - The Circumference of the Circle
• 10297 - Beavergnaw
• 10406 - Cutting tabletops
• 10451 - Ancient Village Sports
• 11068 - An Easy Task
• 11152 - Colourful Flowers
• 11232 - Cylinder
• 11355 - Cool Points
• 11473 - Campus Roads
• 11479 - Is this the easiest problem?

Sada pro pokročilce

• 313 - Intervals
• 811 - The Fortified Forest
• 920 - Sunny Mountains
• 10005 - Packing polygons
• 10012 - How Big Is It?
• 10112 - Myacm Triangles
• 10691 - Subway
• 11343 - Isolated Segments
• 11507 - Bender B. Rodríguez Problem
• 11796 - Dog Distance

• 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

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.

Svoje výkony zapisujte samostatně do tabulky Výkony v minisoutěži VII,

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.

Tentokrát jen jediná sada, s nejrůznějšími náměty :

1. 105 - The Skyline Problem
2. 124 - Following Orders
3. 167 - The Sultan's Successors
4. 209 - Triangular Vertices
5. 264 - Count on Cantor
6. 839 - Not so Mobile
7. 847 - A Multiplication Game
8. 10014 - Simple calculations
9. 10382 - Watering Grass
10. 10862 - Connect the Cable Wires
11. 11567 - Moliu Number Generator
12. 11818 - Game --- Mouse and Cheese
13. CHICAGO - 106 miles to Chicago
14. EIGHTS - Triple Fat Ladies
15. PA06ANT - Ant
16. RRSCHED - Round-Robin Scheduling