Ausgewählte Probleme aus dem ACM Programming Contest

Mittwochs, 13:30 - 15:00 und 15:15 - 16:45, Raum R3.026Modul-Beschreibung
Dozentin: Doina Logofătu  ^

Die Vorlesung verwendet C, C++ oder Java als Programmiersprache.
Der Kurs folgt dem Buch
Algorithmen und Problemlösungen mit C++ (einige Themen findet man auch in [2]).
Dieses Lehrbuch zur Vorlesung ("Kursbuch") findet man in unserer Bibliothek (auch Online im Campus).

Online Platform: ACM Uva Online Judge

Common Mistakes in Online and Real-time Contests
Competition Strategies

Bericht NWERC-Teilnahme

Electronic Board: acm.uva.es/board/

Kopfkommentar

Team

Accepted

gelöste Probleme

Dennis Wilfert
NWERC Urkunde
33
[10424][10044][10392][10397][10147][10048][10099][200] [11722] [111][164][264][526][880][10920][11703][11716] [437]
[369][10183][10303] [352][679][103] [615] [493][808] [567]
[NWERC09_A][NWERC09_C][NWERC09_H]
[NWERC_I][NWERC_J]
Christoph Hausmann
OContest_19_12
21
[11172][10370][102][11063[10344][160]  [382][10311] [167][989] [674][497] [10722][10192] [10465][10338][10007]
[534][941][11734]
[NWERC09_A]
Kevin Kratzer
20
[11172][10370][102]  [382][612][10344] [750][167] [216][294][10405][10722] [437] [485][11645] [530] [615]
[784][10305]
[NWERC_I]
Felix Dietrich
NWERC Urkunde
17
[706][10038][10810][138][438][136][371][10245][11378][11722] [11346] [10378] [10219] [10056][694]
[NWERC_D][NWERC_I]
Stefan Gohlke
15
[11172] [543][686]  [10104][960][412] [750] [147] [111] [102][10183][10038] [10000] [10127] [439]
Bernd Mayr
2
[10038][113]
Jan Petersen
2
[543][686]

Kursablauf

SW *
KW *
Thema
Vorlesung
Praktikum
1


OnlineJudge-Einführung
Infoveranstaltung


Vorlesung01

The 3n+1 Problem (100), Stacking Boxes (103)

Booklet Printing (637), The House of Santa Claus (291)


2


Warm-Up


Tafelbild

Relational Operator (11172), Love Calculator (10424), Perfection (382), B2-Sequence (11063), Above Average (10370), Jolly Jumpers (10038), All You Need Is Love! (10193), LCD Display (706), Ecological Bin Packing (102), Power of Cryptography (113)


3


- Teiler, Teilbarkeit
- Primzahlen, Fundamentalsatz der Arithmetik, 
- ggT, kgV,
- Goldbachsche Vermutung

[2] S. 81

- Anzahl Teiler
- schnelles Potenzieren

Tafelbild

Factors and Factorials (160),
Perfection (382), Divisors (294), Prime Cuts (406), Pi (412),
Goldbach's Conjecture (543), Prime Factors (583),  Gaussian Primes (960), Twin Primes (10394), Circular (967), Count DePrimes (11408),  GCD (11417), Largest Prime Divisor (11466), Euclid Problem (10104), Goldbach Conjecture II (686), Simply Emirp (10235), Goldbach and Euler (10311), Prime Time (10200), Less Prime (10852), You can say 11 (10929), Factovisors (10139), Summation of Four Primes (10168), Prime Distance (10140), Divison (725), Count the factors (10699), GCD+LCM (11317), Factoring Large Numbers (10392), Digit Primes (10533), Semi-prime H-Numbers (11105), Next Same-Factored (11099), Mr. Azad and His Son!!!!! (10490), Factorizing Large Integers (11476)




Tafelbild


4

Backtracking






Sorting

[2] S. 403
[1] S. 357

Tafelbild

Tafelbild

All Squares (155), The Sultan's Successor (167), Getting in Line (216),  The House of Santa Claus (291), Word-Search Wonder (422),
Prime Ring Problem (524), Addition Chains (529), The Settlers of Catan (539), Jugs (571), CD (624), Su Doku (989), LED Test (416), The Tower of Babylon (437), Sum It Up (574), Bundling Newspapers (598), 8 Queens Chess Problem (750),  Not so Mobile (839), Another n-Queen Problem (11195), Sum-up the Primes (10419), 23 out of 5 (10344), Equidivisions (11110), Take the Land (10074)


Dancing Digits (11198), ShellSort (10152), DNA Sorting (612), Flip Sort (10327), Stacks of Flapjacks (120), Age Sort (11462), Vito's Family (10041), Sort! Sort!! and Sort!!! (11321), Ultra QuickSort (10810), Blind Sorting (11714)

5

Dynamische Programmierung: Counting Change, Longest Inc-/Decreasing Sequence, LCS, Matrix Chain Multiplication

[2] S. 403
[1] S. 231
NUS_DP
2-DP

Tafelbild Super Lucky Numbers (älter)

Tafelbild1  Tafelbild2  Tafelbild3

Longest Common Subsequence (10405), Unidirectional TSP (116), Optimal Array Multiplication Sequence (348),
Matrix Chain Multiplication (442), Let Me Count The Ways (357), Dollars (147), Coin Change (674), Histroy Grading (111), String Computer (164), Budget Travel (222), Testing the CATCHER (231), Strategic Defense Initiative (497), Jill Rides Again (507), String Distance and Transform Process (526), Compromise (531), Triangles (585), Self Numbers (640),  Optimal Array Multiplication Sequence (348), Walking on the Safe Side (825), Largest Submatrix (836), Vacation (10192), Longest Run on a Snowboard (10285), e-Coins (10306), Homer Simpson (10465), Sumsets (10125), Travelling Salesman (10702), Again Palindrome (10617), Make Palindrome (10453), Complete Tree Labeling (10247), The Unreal Tournament (10207), Facing Problem with Trees (10643), Super Lucky Numbers (10722), Bits (11645)




NWERC 2009



ProblemSet

Solution Outlines

Standings


A - An Industrial Spy 
B - Common Subexpression Elimination
C - Divisible Subsequences
D - Fractal
E - Mountain Road
F - Moving to Nuremberg
G - Room Assignments
H - Settlers of Catan
I -   Simple Polygon
J -  Wormholes

Ähnlich: zu D ->  Fractal (11253)



6



Wahrscheinlichkeitstheorie






Kombinatorik: Prinzip der Inklusion und Exklusion, Schubfachprinzip, Permutationen, Variationen, Kombinationen, Binomial- und Multinomialkoeffizienten




Gemischt

Tafelbild
11722JoinWithFriend.pdf

[Wahrscheinlichkeitstheorie]

Tafelbild1  Tafelbild2  Tafelbild3


Tafelbild1  Tafelbild2 
Tafelbild3  Tafelbild4
Tafelbild5  Tafelbild6

Tafelbild7

[2] S. 153, 189
Combinatorics

Tafelbild

Tafelbild1  Tafelbild2
Tafelbild3  Tafelbild4



France '98 (542), Burger (557), Coupons (10288), Urn-ball Probabilities! (10169), What is the Probability? (10056), Probability (11346),
Joining With Friend (11722)




Count of Trees (10007), Pascal Triangle of Death (485), Combinations (369), Multinomial Coefficients (911), Ones (10127), Binomial Showdown (530), How Many Fibs (10183), Find the Ways! (10219),
How Many Trees? (10303), Permutations (941), Permutation (11525), Triangle Counting (11401), Permutation Arrays (482), Mischievous Children (10338), Combinatorial Expression (10329), Combination! Once Again (10532), Combinatorial Summation (10694), No Rectangles (135), ID Codes (146),
Critical Mass (580), The partition of a cake (527), Arif in Dhaka (First Love Part 2) (10294), Counting RNA Sequences (11197), Counting (10198), Determine The Combination (10776), LCM Cardinality (10892), The Hamming Distance Problem (729), The Last Non-zero Digit. (10212), Expressions (10157), How Many Pieces of Land? (10213), Coin Toss (10328), Ray Through Glasses (10334), Say NO to Memorization (10634), Extrapolation using a Difference Table (326), How Many? (986), Expression Bracketing (10312), Coin Toss (10328), Cubes (10601), How Many Points of Intersection? (10790), Tri Triling (10918), A Graph Problem (11069), Necklace (11255), Tiling Dominoes (11270), Mixing Invitations (11282), Sultan's Chandelier (11240), Counting Chaos (11309),



Digital Fortress (11716), sqrt log sin (11703), Big Number of Teams will solve This (11734)

7


Graphen:

  - kürzeste Wege (Floyd-Warshall)

  - Tiefen- und Breitensuche

  - topologische Sortierung

  - minimaler Spannbaum

[2] S.  251

Tafelbild

Tafelbild1 Tafelbild2
Tafelbild3

[Floyd-Warshall]


[BFS]  [DFS]



[Topologische Sortierung]



[Flooding-Algorithmus]



[Minimal Spannbaum]
[Kruskal] [Prim]


Tafelbild1 Tafelbild2

Tafelbild

Tafelbild






Tree Summing (112), The Postal Worker Rings Once (117), Trees on the level (122), Graph Coloring (193), Tree Recovery (536), Allways on the run (590), Mapping the Route (614), Is it a Tree? (615), The die is cast (657),  Dropping Balls (679), Longest Paths (10000), Bicoloring (10004), All Roads Lead Where? (10009), Wheres's Waldorf? (10010),
Robot Motion (10116), Roads in the North (10308), Ecosystem (626), Numbering Paths (125), Climbing Trees (115), Count the Faces (10178), Virtual Friends (11503)


Frogger (534), Heavy Cargo (544), Risk (567),
Audiophobia (10048), The Tourist Guide (10099), Identifying Concurrent Events (334),  MPI Maelstrom (423), Arbitrage II (436), Page Hopping (821),

Shipping Routes (383), Software Allocation (259), Knight Moves (439), All Walks of length "n" from the first node (677),  We Ship Cheap (762),  Dungeon Master (532), Word Transformation (429), Vertex (280), Traveling Politician (10543), A Node Too Far (336),  Always in the Run (590),  The Net (627), Erdös Numers (10044),


Rare Order (200), Ordering Tasks (10305)



Arbitrage II (436), Wetlands of Florida (469),
The Seasonal War (352), The PATH (601), Grid Colouring (785), Il Giocco dell'X (260), Oil Deposits (572), Monkeys in a Regular Forest (776), Contour Painting (782), Maze Exploration (784),


Frogger (534), Freckles (10034), Highways (10147), Connect the Campus (10397), Killing Alliens in Borg Maze (10307)





Tafelbild


  Präsentationen 21.01: Bilderzip-Archiv
                                         Stefan Gohlke,
                                         Christoph Hausmann,
                                         Kevin Kratzer  Handout


8



Algorithmische Geometrie
[1] S. 219
[Computational Geometry]


Polygon Clipping


Smallest enclosing circle
SCUD Busters (109), Polygons (137), Orchard Trees (143), Intersection (191), Convex Hull Finding (681), Moth Eradication (218),  Intersecting Lines (378), Globetrotter (535), Water Falls (833), Convex Hull (11626), The Closest Pair Problem (10245), Bey Battle (11378), The Skyline Problem (105), Pipe Fitters (121), Bumpy Objects (132), Mouse Clicks (142), All Squares (155), Laser Lines (184), Lining Up (270), Pipe (303), Cops and Robbers (361),  Intersecting Lines (378), Overlapping Rectangles (460), Points in Figures: Rectangles (476), Points in Figures: Rectangles and Circles (477), Points in Figures: Rectangles, Circles and Triangles (477), Polygon (634),
Gleaming the Cubes (737), Intersecting Line Segments (866), Overlapping Air Control Zone (904), Sunny Mountains (920), Rectangle by the Ocean (922), Horizon Line (972), Center of Masses (10002), Packing polygons (10005), Chainsaw Massacre (10043), Useless Tile Packers (10065), The Art Gallery (10078), Hotter Colder (10084),
Chinese Ink (11665), The Incredible Hull (596), Points (11072), Nails (11096)

Packing polygons (10005), Tower for Cellular Telephony (11681)
9


Zahlen, Zahlen, Zahlen







Brute Force




Mengen, Relationen

[2] S. 132,












[2] S. 59

Ugly Numbers (136), Humble Numbers (443), Happy Numbers (944),
Quirksome Squares (256), Kaprekar Numbers (974), Fibonacci Numbers (10579),
Charmichael Numbers (10006), Bangla Numbers (10101),  Self Numbers (640), Smith Numbers (10042), Super Divisible Numbers (995), Cyclic Numbers (942), Selfdescribing Sequence (10049), Ackermann (371), Taxicab Numbers (962), Factorial Factors (884), Farey Sequence (10408), Magic Numbers (471), Pyramid Number (11522),
Perfect Cubes (386), Complex Numbers (10378), Street Numbers (138), Perfect Pth Powers (10622), Couple-Bachelor-Spinster Numbers (10174), Pairsumonious Numbers (10202), Automorphic Numbers (10433), Persistent Numbers (10527), Almost Prime Numbers (10539), Happy Number (10591), Super Number (10624), Fibinary Numbers (763), Spiral of Numbers (903), Rational Spiral (493), How Many 0's? (11038), Abundance and Perfect Numbers (10914), Square Numbers (11461), Spiral Tap (10920),
Bay Battle (11378), Collatz Series (694)


Ecological Bin Packing (102), Band Width (140), Finding Rectangles (638)


The Departament of Redundancy Departament (484), Count on Cantor (264),  Cantor Fractions (880),

10


Zeichenketten



[2] S. 25

 

Pig Latin (492), What's The Frequency, Kenneth? (499), The Decoder (458), Marvelous Mazes (445), Encoder and Decoder (444), Rotating Sentences (490), Kindergraten Counting Game (494), Unix ls (400), Password Search (902), Cript Kicker II (850), Palindromic Subsequence (11404), O: dah, dah, dah! (11223), Magic Square Palindromes (11221), Palindromes (401), Word Scramble (483), TEX Quotes (272), WERTYU (10082), Decode the Mad man (10222), Soundex (10260), Haiku Review (576), Automatic Poetry (10361), Love Calculator (10424), Tell me the frequencies! (10062), Prime Frequency (10789), Prime Words (10924), Longest Palindrome (11151), Group Reverse (11192), Babelfish (10282), Glas Beads (719), Formula 1 (11056), Decoding the Message (11220), Deli Deli (11233), Again Palindrome (10617), Make Palindrome (10453), Andy's
First Dictionary (10815), Find the Telephone (10921), String Factoring (11022), LCD Display (706), Bank (Not Quite O.C.R.) (433),  I Love Strings! (10679), The Vigenere Cipher (856)

---------------------------------------------------------------------------------------------------------------------------------------------------------------
Plätze 1, 2, 3 für bisherige: Schönstes Problem ? Schönstes Programm? Leichtestes/schwierigstes Problem? Schlechtestes Programm?

11

Verschiedene Formeln









Ebene Geometrie,
[2] S. 139


Square Root Algorithms








Is this the easiest problem? (11479), Box of Bricks (591), Fermat vs. Pythagoras (106), Johanna and the Odd Numbers (913), The Cat in the Hat (107), Pizza Cutting (10079), Product of Digits (993), H(n) (11526), How Old are You? (11219),
What Day is It? (602), Clock Hands (579), The Circumference of the Circle (438), Continued Fractions (834), Above Average (10370), Polynomial Shutdown (392), Error Correction (541), The Collatz Sequence (694), Square Root (10023), Primary Arithmetic (10035), Triangular Vertices (209), Bee Breeding (808), The Trip (10137), Summation of Polynomials (10302), Odd Sum (10783), Big Chocolate (10970), How Far? (10466), Beat the Spread! (10812), Cos(NA) (11170), Colourful Flowers (11152), Peter's Smoke (10346), Solve It (10341), The Land of Justice (10499), Simple Equations (11565), Last Digit (10162), What is the Median? (10107), Powers Et. Al (10515), f(91) (10696), Power of Matrix (11149), Series of Powers (11190), Polynomial Coefficients (10105), Solving Systems of Linear Equations (10109), B2-Sequence (11063), Can You Solve It? (10642), Play with Floor and Ceil (10673), Conic Distance (10495), Cats with or without Hats (10493),  Series of Pi (10736), Poly the Pollynomial (498), Riemann vs. Mertens (10738), Quotient Polynomial (10719), Diagonal (10784), Again Prime? No time (10780), Back to Intermediate Math (10773), Recover Factorial (10856), 2 the 9s (10922), Fractions Again?! (10976), Leap Year or Not Leap Yaer and... (10070), Complex, difficult and complicated (11042), Very Funny, Mr. Feynman! (11120), Multifactorials (11347)


12

Basisumwandlung





Simulation

[2] S. 128, 308

What Base is This? (343), Roman Digititis (344), Roman Numerals (185), Fibonaccimal Base (948), The Bases are Loaded (353), Basically Speaking (389), Cowculations (377),
Kibbles "n" Bits "n" Bits "n" Bits (446), The Return of the Roman Empire (759), Skew Binary (575), To Carry or not to Carry (10469), Ternary (11185), Base -2 (11121), Base64 Decoding (10343), The Stern-Brocot Number System (10077), All You Need Is Love! (10193), Simple Base Conversion (10473), Prime Land (516), Fi-binary Number (11089), Power Signs (11166), The Fun Number System (10705), Cheapest Base (11005), Squares III (636)


The Blocks Problem (101), Simulation Wizardry (114), Rock-Paper-Scissors Tournament (10903), Graphical Editor (10267), Check The Check (10196), Minesweeper (10189), Interpreter (10033), Jolly Jumpers (10038),
13

Große Zahlen, Modulo











Variable Range Related


Greedy

[2] S. 104, 302

[Big Num]




[Gamma_Funktion
(für 10323)]





[2] S. 283
[Greedy]


Integer Inquiry (424), Factorial Frequencies (324), Big Mod (374), Modular Fibonacci (10229),
I Love Big Numbers! (10220), Factoring Large Numbers (10392), Software CRC (128), Fibonacci Freeze (495), 500! (623), Ocean Deep! Make it shallow! (10176), Very Easy !!! (10523), Product (10106), Super long sums (10013), Factorial! You Must be Kidding!!! (10323), Zeros and Ones (10324), Big Big Real Numbers (10464), Complete Tree Labeling (10247), The Priest Mathematician (10254), Guess the Number! (10275), Towers of Hanoi (254), Arithmetic Operations with Large Integers (288), Palindorms <---> smordnilaP (290), Overflow (465), Numerically Speaking (619), Adding Reversed Numbers (713), Exponentiation (748), Fibinary Numbers (763), Maximum Sub-sequence Product (787), The Mosquito Killer Mosquitos (10108), Expressions (10157), World Cup Noise (10450), If We Where A Child Again (10494), !! Really Strange !! (10519), Opening Doors (10606), Simplifying Fractions (10814), Connect the Cable Wires (10862), Krakovia (10925), The Ghost of Programmers (10992), Uncle Jack (11115), Help My Brother (II) (11161), Matches (11375), Integer Transmission EXTREME (11438), Who said crisis? (11448),


Hashmat the Brave Warrior (10055), All in All (10340)


Station Balance (410),  Balancing Bank Accounts (538), Minimal Coverage (10020), The Grand Dinner (10249), All in All (10340), Packets (311), Shoemaker's Problem (10026), Advertisment (10148), Editor Nottobad (10602), Work Reduction (10670), Ants (10714)

* SW = "Semesterwoche", KW = "Kalenderwoche"

Literatur
 
1.  Doina Logofătu, Algorithmen und Problemlösungen mit C++, Vieweg Verlag, ISBN 978-3-8348-0126-5, 2006. (online in Campus)
2.  Doina Logofătu, Grundlegende Algorithmen mit Java, Vieweg Verlag, ISBN 978-3-8348-0369-6, 2008. (online in Campus)
3.  Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen - Eine Einführung, 2. Auflage, Oldenbourg Wissenschaftsverlag, München 2007, ISBN 978-3-486-58262-8.
  - Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. MIT Press, Boston 2001, 2002, 2003, 2005
     ISBN 0-262-53196-8. (engl. Orig.-Fass.)
4.
Online Platform: ACM Uva Online Judge
5. ProblemSolve Toolkit: http://www.uvatoolkit.com/problemssolve.php
6. World of Seven
7. Art of Programming Contest
8. Programming Challenges: http://www.programming-challenges.com
9. ICPC Live Archive: http://acmicpc-live-archive.uva.es/nuevoportal/


Weiteres
5.  Timus Online Judge
6.  Hinweise für Neueinsteiger
7.  Topcoder: ein weiterer Programmierwettbewerb, der nicht nur Studenten offen steht