Ausgewählte Probleme aus dem ACM Programming Contest

Donnerstags, 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
Electronic Board: acm.uva.es/board/
Bitte nicht vergessen!: Kopfkommentar


Bericht NWERC-TeilnahmeACM-Teilnahme Infos

NEU:  Konferenz-Teilnahme DAS 2010 Rumänien, 26-31. Mai 2010: Bilder, Bericht Felix
NEU:  HM Teams belegen Plätze 20, 24 und 33 beim German Collegiate Programming Contest 2010, 12. Juni 2010: Bericht, Bilder, Aufgaben, Solutions Outline, Abschlusstabelle

North Western European Regional Contest, Bremen, November 19-21, 2010


Team

Accepted

gelöste Probleme

Barny Porcio
Urkunde GCPC 2010 Michael Haus
25
[11172] [10235][585][557][11703][102][10189][457][706][11608][10200][11610][10023][10013][674][612][750][989]
[11804][11805][10465][825][231][640][497]

Teilnahme A Contest from BUBT, Bangladesh
(Platz 103/174)

Präsentation: .odp, .pdf

Robert Reichart
21
[382][10424][11636][11417][11063][11716][113][591][10079][10970][11219][10696][10346][541][422][291][11152][579]
[10405][10784][10922]

Präsentation: .ppt, .pdf

Viktoriya Ryabova
18
[11172][11734][568][10104][382][10424][10783][10370][10699][543][686][10035][406][10070][10327][11462][10810][216]

Präsentation: .pptx, .pdf

Ekaterina Savkina
12
[11172][11734][10929][11479][10970][10812][913][10038][10070][524][147][674]

Präsentation: .pdf

Christoph Miesel
Urkunde GCPC 2010 Michael Haus

11

[11715][11661][10773][11787][574][209][808][111][100][11805][11799]

Teilnahme  Smartmatic CONNECT IV (Platz 72/96)
Teilnahme  VIII Programming Olympiads in Murcia (http://dis.um.es/contest) (Platz 54/94)
Teilnahme A Contest from BUBT, Bangladesh (Platz 141/174)
Teilnahme 
A Contest from Dinajpur, Bangladesh (Platz 115/189)
Teilnahme  One more National Programming Contest 2010, 4.09.2010  (Platz 62/167)


Yulia Vnukova
2
[11172][10370]



Paper 10th International Conference on Development and Application Systems
DAS 2010PDF
Paper 21st IASTED International Conference on Modelling and Simulation MS 2010PDF

Felix Dietrich
Urkunde GCPC 2010 Michael Haus
8
WA: 2
[10193][10370][10106][11609][414][417][10883][324]
WA: [11373][11476]

Evgeni Pavlidis

Urkunde GCPC 2010 Michael Haus

84

[374] [967][821][820][585][583][575][568][550][489][488][408][350][294][160][11099][10879][108][10617][10453]
[10392][10300][10110][10071]

Teilnahme National Programming Contest of Bangladesh at SUST (Platz 54/121)

[694][537][445][201][11785][11784][11780][11777][11774][11105][10780][10533][10394][10010]

[596][422][409][361][340][299][167][155][152][120][11792][11790][11786][11782][11659][11626][11461][10815]
[10490][10474][10420][10405][10038][10035][10018][10004]

[719][531][400][191][156][123][11775][11317][10344][960][836][10811][10306][10074]

[941][11645][10722][10622][10140]

Yellow Pyramid
IF 2B
Michael Haus
Martin Lambeck
Siegfried Ippisch
Urkunde GCPC 2010 Michael Haus
Urkunde GCPC 2010 Michael Haus Urkunde GCPC 2010 Michael Haus

67


Blatt 1, 10.06.   ->  [10104][10235][10139][10622][637][138][902][10341][438][706]
[382][100][11734][11659][11172][11703][138][100][11635]

Blatt 2, 28.07.   ->  [107][10042][10044][948][10419][11346][200][439][536][10307]
[534][544][11236][113]

Blatt 3, 11.08.   ->  [10140][10219][10199][10842][334][11369][10369][10130][10496][10491]
[485][369][530][10007][10303][147][357][674]

Blatt 4, 18.08    ->  [10930][10883][10510][11090][11122][338][11072][11096][653][673][190]
[10405]

Teilnahme  One more National Programming Contest 2010, 4.09.2010  (Plätze 39,90/167)
[11821][11824][11827]
Teilnahme Brazilian National Contest 2010, 18.09.2010  (Plätze 37,54/114)
[11830][11831][11835][11838][11839]

Blatt 5, 08.09    ->  [11813][11814][11815][11816][11817][10311][10394][11525][11074][10566][811][10557][11087][11691]



Kursablauf

SW *
KW *
Thema
Vorlesung
Praktikum

1


OnlineJudge-Einführung
Infoveranstaltung





Warm-Up


Vorlesung01





Tafelbild 18.03

Beispiele:
The 3n+1 Problem (100), Stacking Boxes (103)
Booklet Printing (637), The House of Santa Claus (291)



Relational Operator (11172), Big Number of Teams will solve This (11734),  Informants (11659), Love Calculator (10424), Perfection (382), B2-Sequence (11063), Above Average (10370), Jolly Jumpers (10038), All You Need Is Love! (10193), LC-Display (706), Ecological Bin Packing (102), Power of Cryptography (113), Digital Fortress (11716), sqrt log sin (11703), Big Mod (374), Product (10106), Super long sums (10013), Minesweeper (10189), No Problem (11608), Hello World! (11636),
Burger Time? (11661), Back to High School Physics (10071), Ecological Premium (10300),  Triangle Wave (488), Hangman Judge (489), Linear Cellular Automata (457), Marvelous Mazes (445)


2


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

[1] S. 81

- Anzahl Teiler
- schnelles Potenzieren

Tafelbilder 25.03:
1  2  3


Light, more light (10110), Multiplying by Rotation (550),  Just the Facts (568), Uniform Generator (408), Pseudo-Random Numbers (350), How many zero's and how many digits? (10061), Code Refactoring (10879), 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), Doom's Day (11774),
Again Prime? No time (10780), Factorial Frequences (324), Perfect P-th Powers (10622)



Nächster UVa-Wettbewerb:
National Programming Contest of Bangladesh at SUST, Sa. 17.04.2010, 10:00 Uhr
           




3


Verschiedene Formeln

Ebene Geometrie,
[1] S. 137


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), 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), Artificial Intelligence? (537),Squares (201), Hypercube (11785), Escape (11784), Miles 2 Km (11780), Automate the Grades (11777), Where's Waldorf? (10010), Car (11715),
Numeral Hieroglyphs (
11787), Machined Surfaces (414), Word Index (417), Excuses, Excuses! (409), Master-Mind Hints (340), Train Swapping (299),
Tree's a Crowd (152), Krochanska is Here! (11792), Murcia's Skyline (11790), Global Raining at Bididbus (11786), Square Numbers (11461),
Grocery Store (11236), Andy's first dictionary (10815), List of Conquests (10420), Reverse and Add (10018), What's Chryptanalysis? (10008), Bicoloring (10004),
Glas Beads (719), UNIX ls (400), Intersection (191), Anagrams (156), Searching Quickly (123), Supermean (10883), Permutations (941), Argentina (11804),
Bafana, Bafana (11805), Horror Dash (11799), Puzzle (227), Circle Through Three Points (190), Long Multiplication (338), The Bases are Loaded (355),
Square Pegs and Round Holes (356), Inscribed Circles in Isosceles Triangles (375), Fifth Bank of Swamp Company (426), Swamp County Roofs (428),
Population Explosion (447), Majoring in Scales (449), Anagrams (454), Periodic Strings (455), Overlapping Rectangles (460), Mirror, Mirror (466),
Key to Success (468),
Boogle Blitz (487), Parantheses Balance (673), Jack and Jill (697), Index (698), Triangular Museum (744), Biorhythms (756),
Interpreter (10033), Chainsaw Massacre (10043),


Nächster UVa-Wettbewerb: Smartmatic CONNECT IV, Sa. 24.04.2010, 17:30 Uhr


4



Backtracking






Sorting

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


Tafelbild 4.06

Tafelbild 7.06


All Squares (155), The Sultan's Successors (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), Where is Marble? (10474)

Nächster UVa-Wettbewerb: VIII Programming Olympiads in Murcia (http://dis.um.es/contest), Sa. 15.05.2010, 7:30 Uhr


5



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



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

Tafelbild 8.06

Tafelbild 10.06

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), Maximum Sum (108),
Optimal Cut (11782), Unique Story (11775), Up to the Ante (10811)

Nächster UVa-Wettbewerb:  A Contest from Dinajpur, Bangladesh, Sa. 26.05.2010, 10:00 Uhr
                                        
A Contest from BUBT, Bangladesh,      So. 27.05.2010, 10:00 Uhr



6




HM Teams belegen Plätze 20, 24 und 33 beim German Collegiate Programming Contest 2010:  Bilder

Aufgaben,
Erklärungen,
Abschlusstabelle
die Probleme zum Testen





7


...

Graphen

Bases
...

Tafelbilder 11.06:
1  2  3  4
5  6  7

Tafelbilder 17.06:
1  2 


Zeichenketten
...

Page Hopping (821), Internet Bandwidth (820),

Skew Binary (575),



Password Search (902),


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



8


Graphen:

  - kürzeste Wege (Floyd-Warshall)

  - Tiefen- und Breitensuche

  - topologische Sortierung

  - minimaler Spannbaum

[2] S.  251

[Floyd-Warshall]


[BFS]  [DFS]


[Topologische Sortierung]


[Flooding-Algorithmus]


[Minimal Spannbaum]
[Kruskal] [Prim]

Dijkstra-Algorithmus



 


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), Following Orders (124), Ordering (872)



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)

Ubiquitous Religions (10583), Antifloyd (10987), ACM Contest and Blackout (10600), Is There a Second Way Left? (10462), Lift Hopping (10801),
Sending Email (10986), Cockroach Excape Networks (10805), Buy or Build (3505), War (10158), The Toll! Revisited (10537),

The Gossipy Gossipers Gossip Gossips (10850), The Rock (10381), Return of the Jedi (10224), Easter Eggs (10857), A Node Too Far (336),
Graph Connectivity (459), Hamiltonian Cycle (775), Graph Construction (10720), Dijkstra, Dijkstra (10806),



9



Wahrscheinlichkeitstheorie






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








[Wahrscheinlichkeitstheorie]






[2] S. 153, 189
Combinatorics




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




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),
Teams (11609),
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),



 
Training -

  Sommer 2010


Tafelbilder 4.08:

1  2  3  4  5  6

Tafelbilder 11.08:
1  2  3  4  5

Tafelbilder 18.08:
1  2  3  4

Tafelbilder 1.09:

1  2  3

Tafelbilder 8.09:
1  2  3

 

 
- Links Uni-Erlangen:  ..., SS 2007SS 2008SS 2009, SS2010
- Teilnahme  One more National Programming Contest 2010 (Platz 39, 90/167)



10



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),  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), Polygon Intersections (805),
Offset Polygons (877), Stack of Cylinders (915), Sunny Mountains (920), Nice Milch (10117), Polygon Intersection (10321), Cicles in Hexagon ;-) (10353),





Challenges





Hotel booking (11635),
Happy Birthday (11373),
Nested Dolls (11368),
e-Coins (10306),
Lights inside a 3d Grid (11605), Atoms (11606), Teams (11609), Reverse Prime (11610), Sultan and Khairun Shundori (11612),
Cops and Robbers (361), Convex Hull (11626), Chinese Ink (11665), The Incredible Hull (596),
Triangles (585),
Burger (557),
Again Palindrome (10617),
Make Palindrome (10453),
Next Same-Factored (11099)


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

Literatur
 
1.  Doina Logofătu, Algorithmen und Problemlösungen mit C++, Vieweg Verlag, ISBN 978-3-8348-0763-2, 2010. (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/
10. 
Common Mistakes in Online and Real-time Contests
11. 
Competition Strategies

Weiteres
12.  Timus Online Judge
13.  Hinweise für Neueinsteiger
14.  Topcoder: ein weiterer Programmierwettbewerb, der nicht nur Studenten offen steht

Java
15. 
Java™ Platform, Standard Edition 6 API Specification, Online Referenz: http://java.sun.com/javase/6/docs/api/, Sun Microsystems, Inc, 2006.