Modul "Ausgewählte Probleme aus dem ACM Programming Contest"

(Selected Problems of the ACM Programming Contest)

Mittwochs, 15:15 - 16:45 und 17:00 - 18:30, Raum R1.009AModul-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

Training ACM Nürnberg & Co: 15 Okt, 16 Okt, 22 Okt, 23 Okt, 29 Okt, 30 Okt, 12 Nov, 13 Nov, 26 Nov3 Dez, 10 Dez

#
Name
Verdikt
versuchte/gelöste Probleme
1
Evgeni Pavlidis
AC: 42
[102] [103] [111] [113] [116] [128] [136] [138] [147] [264] [291] [324] [348] [357] [371] [374] [382] [392] [401] [412] [442] [443] [482] [483] [492] [499] [507] [524] [530] [543] [579] [591] [637] [674] [750] [941] [974] [989] [993] [10007] [10127] [11417]
2
Peter Schnitzler AC: 23, WA: 1
[100] [106] [113] [138] [191] [344] [439] [445] [484] [495] [543] [567] [591] [10030] [10055] [10219] [10340] [10419] [10469] [10523] [11401] [11479]     [193]
3
Gunnar Hage AC: 15,  WA: 3, TLE: 1
[100] [136] [138] [264] [442] [485] [534] [640] [759] [10004] [10079] [10338] [10789] [11219] [11221]     [294] [469] [785]     [944]
4
Till Fischer
AC: 15, WA: 1, TLE: 2
[100] [113] [400] [424] [494] [530] [576] [10007] [10106] [10127] [10303] [10361] [10370] [10783] [11417]     [492]     [101] [10013]
5
Tobias Fuchs AC: 15
[336] [371] [423] [458] [499] [538] [543] [544] [591] [686] [694] [10048] [10147] [10235] [10394]
6
Christoph Neuroth

7
Isabella von Sivers



Kursablauf

SW *
KW *
Thema
Vorlesung
Praktikum
1
40
OnlineJudge-Einführung


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

2
41
Infoveranstaltung
Vorlesung01
Booklet Printing (637),
The House of Santa Claus (291)

3
42
- Teiler, Teilbarkeit
- Primzahlen, Fundamentalsatz der Arithmetik, 
- ggT, kgV,
- Goldbachsche Vermutung
[1] S. 81
- Anzahl Teiler
- schnelles Potenzieren

Power of Cryptography (113), Factors and Factorials (160),
Perfection (382), Divisors (294), Prime Cuts (406), Pi (412),
Goldbach's Conjecture (543), Prime Factors (583), Prime Land (516),
Gaussian Primes (960), Twin Primes (10394), Circular (967), Count DePrimes (11408),  GCD (11417),
Largest Prime Divisor (11466), Euclid Problem (10104), Goldbach Conjecture II (686), Sum-up the Primes (10419), Simply Emirp (10235), Goldbach and Euler (10311), Prime Time (10200)

4
43
Zahlen, Zahlen, Zahlen







Brute Force
[1] S. 132,

Ugly Numbers (136), Humble Numbers (443), Happy Numbers (944),
Quirksome Squares (256), Kaprekar Numbers (974), Fibonacci Numbers (10579),
Charmichael Numbers (10006), Bangla Numbers (10101), Erdös Numers (10044),  Self Numbers (640), Smith Numbers (10042), Super Divisible Numbers (995), Cyclic Numbers (942), Selfdescribing Sequence (10049), Ackermann (371), Taxicab Numbers (962), Factorial Factors (884),


Ecological Bin Packing (102), Band Width (140), Finding Rectangles (638)
5
44
Diophantische Gleichungen - die Pell'sche Gleichung


Graphen:

  - kürzeste Wege (Floyd-Warshall)

  - Tiefen- und Breitensuche

  - topologische Sortierung

  - minimaler Spannbaum
[1] S. 88, 113


[1] S.  251




[Floyd-Warshall]


[BFS]  [DFS]




[Topologische Sortierung]



[Flooding-Algorithmus]



[Minimal Spannbaum]
[Kruskal] [Prim]

Street Numbers (138)

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)

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),


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)

6
45
Verschiedene Formeln







Wahrscheinlichkeittheorie





Algorithmische Geometrie



Greedy
Ebene Geometrie,
[1] S. 139






[Wahrscheinlichkeitstheorie]




[1] S. 219
[Computational Geometry]




[1] S. 283
[Greedy]
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), Perfect Cubes (386), 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 Arithmetc (10035), Triangular Vertices (209), Bee Breeding (809), The Trip (10137), Summation of Polynomials (10302), Odd Sum (10783), Big Chocolate (10970), Complex Numbers (10378), How Far? (10466)


France '98 (542), Burger (557), Coupons (10288)




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),



Station Balance (410),  Balancing Bank Accounts (538), Minimal Coverage (10020), The Grand Dinner (10249), All in All (10340),
7
46
Basisumwandlung




Simulation

[1] 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)

The Blocks Problem (101), Simulation Wizardry (114)
8
47
Große Zahlen, Modulo





Variable Range Related

[1] S. 104, 302

[Big Num]

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),


Hashmat the Brave Warrior (10055), All in All (10340)
9
48
Mengen, Relationen, Cantor-Diagonalisierung [1] S. 59

The Departament of Redundancy Departament (484), Count of Cantor (264)

10
49
Kombinatorik: Prinzip der Inklusion und Exklusion, Schubfachprinzip, Permutationen, Variationen, Kombinationen, Binomial- und Multinomialkoeffizienten
[1] S. 153, 189

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)

11
50
Zeichenketten [1] S. 25

Pig Latin (492), What's The Frequency, Kenneth? (499), The Decoder (458), Marvelous Mazes (445), Encoder and Decoder (444), Rotating Sequences (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), The Decoder (458), WERTYU (10082), Decode the Man man (10222), Soundex (10260), Haiku Review (576), Automatic Poetry (10361), Love Calculator (10424), Tell me the frequencies! (10062), Prime Frequency (10789)


12
51
Dynamische Programmierung: Counting Change, Longest Inc-/Decreasing Sequence, LCS, Matrix Chain Multiplication
[1] S. 403
[2] S. 231
NUS_DP

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)

13
52, 53
Backtraking [1] S. 403
[2] S. 357

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),


* 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

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