ACM Contest Training 2009 - ...

Nächste Regional: http://2009.nwerc.eu/
ACM-ICPC Registrierung

Online Platform: ACM Uva Online Judge

Common Mistakes in Online and Real-time Contests
Competition Strategies
ACM Programming Contest 2008 Teilnahme unseres Teams, nächstes Regional: http://2009.nwerc.eu/

Electronic Board: acm.uva.es/board/

Kopfkommentar

Teams
Team 1
Team 2
Team 3
Dennis Wilfert      2Bang09, Col09, Bra09, NWERC09 Axel Fiedler    FAU09NWERC09
Felix Dietrich        Bang09, Col09RegWa1, Bra09, NWERC09 Gunnar Hage      ?  Peter Schnitzler   FAU09
Evgeni Pavlidis     Swerc08, FAU09, NWERC09 Andreas Kunft     ? Christoph Miesel   FAU09, 2Bang09, Col09


Meetings

Datum, Raum, Anwesend
 Agenda

25.


21.04.2010

- Antwort DAS 2010 -  Reviewers
- Aktuelle Version des Papers
- Tafelbild


24.


6.04.2010, 18:00 -
FD

- paper MCS Code einfügen: neue Version
- Sudoku-Parallel:  Parallel Sudoku Solver Erlang, Parallel Generation, Parallel Programming, Sudoku Message Passing, Sudoku and Graph Theory, Code-Head,
                            mehrere Links, Parallel SAT.., Scalability, Sudoku in Mathematica, Parallel Sudoku, F#.NET Journal, Sudoku on FPGA, Sudoku C#,
- Schritte: Generierung Sudokus, Parallele Implementierung F#,  Sudoku -> SAT -> SAT Solver  ->  Sudoku, Statistics
- MCS, NI, EX für MCS Paper: Visualisierung Applikation Mathematica, .NET
- Tafelbild


23.


 26.03.2010, 14:00-18:00
FD, EP

- paper MCS, DAS 2010, eingereicht: Version 31 März
- Graphiken, Korrekturen
- Sudoku mit F#, Scala.., einige nützliche Links: Wikipedia, Alg 1, Alg 2, Dancing Links 12, Solver, BachAbschlArbeit2007, Mathepedia Topic, DiplArb 2006
- ACM-Training, "Challenges" aus ACM-Fach-Seite: Tafelbild


22.


11.03.2010, 10:30-15:30
DW, FD


- Monte-Carlo vs. Numerical Integration - Experimente&Graphiken
- Paper-Format ?
- auszufüllen: Concurrency & Monte-Carlo - Referenzen,
- Sudoku & N-Damen in F# diskutiert
- Scala-Programme ?


21.



02.03.2010, 10:30-13:30
R3.019+R3.036
FD, DW, EP


Tafelbild 1, Tafelbild2
-  neue Monte-Carlo Experimente und Graphiken
-  Papers diskutiert
-  TODO: Papers PACT 2009 lesen, weitere Links von EMail heute lesen, Nebenläufigkeit und Monte-Carlo allgemein hizufügen
-  Dennis+Evgeni: Scala-Programme
-  Felix: F#-Programme


20.


23.02.2010, 14:00, R.3.024
DW


- Paper "Monte-Carlo Simulations..." diskutiert
- Scala...


Alternativer Titel für Monte-Carlo: "Modelling the Probability of Deadlocks in a Multithreading Process"


19.


17.02.2010, 13:00, Mensa
FD

- Paper "Monte-Carlo Simulations..." diskutiert
- weitere Arbeit: "Multi Paradigm Programming with F# and Scala"...
- ...


18.



10.02.2010, 13:00, R 3.036
FD

- weitere MC-Experiments
- Abbildungen & Referenzen in Paper
-...


17.
 
 8.02.2010, 15:30, R  3.026
FD
 
 
 - Erstellen einer wissenschaftlichen Arbeit für eine internationale Konferenz (e.g. für  DAS 2010 oder MS 2010)

 - Themen besprechen:
     a.  Modelling and Monte-Carlo Simulation for a parallelisation Problem (?)  Tafelbild
     b.  New Mathematica Features in Examples: Built-In Parallel Computing  (?)  Tafelbild
     c.  Comparative Survey for the Multiparadigm Programming Languages F# and Scala (?) Tafelbild


- Monte-Carlo Simulationen: JoiningWithFriend - FWP-Fach 09/10Monte-Carlo Simulation Basics, Definition von answers.com,
- Ähnliche Probleme in UVa: Probability (11346), So you waht to be a 2^n -aire? (10900)

- Mathematica: new Features in Mathematica 7
- Buchempfehlung für Fractale:  Fractals everywhere, M. F. Barnsley
   Einge Quellen zu Fraktale:  The Random Iteration AlgorithmFractals&Semifractals, A Formal Treatement of Deterministic Fractals,
                                            Philosophie der Fraktale







16.

  3.11.2009, 10:00, R 3.036

   Tafelbild


15.

 2.11.2009, 15:15, R 3.036

   Tafelbild



14.


  22.10.2009, 10:00, R 3.020

1. Diskussion...

2.  09acmTraining22_10.pdf

3.  Tafelbild


4.  Nächster Online-Wettbewerb über UVa: 24.10, 13:00 (Dhaka Regional)



13.

  
 
1. Diskussion 6-ter MiniContest: Prime Ring Problem (524), 23 out of 5 (10344), The Closest Pair Problem (10245),  Convex Hull (11626),
                                                               The Twin Towers (10066),
History Grading (111)

2. The Cat in the Hat (107)

3. F. Dietrich
: Ones (10127),  No Problem (11608), Teams (11609), Optimal Array Multiplication Sequence (348), Pascal Triangle of Death (485),  LC-Display (706),

4. Gunnar Hage: 
23 out of 5 (10344)

5. Nächster Online-Wettbewerb über UVa: 17.10, 10:00 (CUPCAM 2009)


12.
  
    3
.10.2009, 10:30,
R 3.026
 
1. Common Mistakes in Online and Real-time Contests
     Competition Strategies


2.  ! Online-Contest über UVa !:
       Nordic Collegiate Programming Contest NCPC 2009, 11:00

3. NCPC-Seite

4. NCPC 2008: die Probleme, die Hinweise, die Ergebnisse

5.
NCPC 2007: die Probleme, die Hinweise, die Ergebnisse


11.


   23.09.2009, 10:00, R 3.026

1. Wie wiele aus 10 in 4 Std.?  08acmTraining23_09.pdf

2. Tafelbild1, Tafelbild2

3. Newton-Verfahren  (für 10341), Erweiteter euklidischer Algorithmus (für 10104)

4. Gelöste Probleme:
Euclid Problem (10104),  Simply Emirp (10235),  Password Search (902),  Solve It (10341)

5.
Nächster Online-Wettbewerb über UVa: 27.09.09 (Sonntag), 19:00 Uhr (Waterloo ACM Programming Contest Fall 1 2009)


10.



   21.09.2009, 10:00, R 3.026

1.
Teilnahme Brazilian National Contest 2009, 19.09.2009
  
    Felix Dietrich:       Platz    44/145,  4/8 gelöste Probleme: 
Alarm Clock (11677), Cards Exchange (11678), Sub-prime (11679), Laser Sculpture (11683)
    Dennis Wilfert:      Platz    49/145,  4/8 gelöste Probleme: 
Alarm Clock (11677), Cards Exchange (11678), Sub-prime (11679), Laser Sculpture (11683)
 
2. Dynamische Programmierung:  
History Grading (111), 
                                                  
Coin Change (674), Dollars (147),  Let Me Count The Ways (357)
                                                  Super Lucky Numbers (10722)  !!! merke die Varianten, siehe TafelbildAM

                                                   ??? 
Bits (11645)
                        
3. Algorithmische Geometrie:       
The Closest Pair Problem (10245),
                                                  ???  Cops and Robbers (361)


4. Math:                                      Logarithms (11666)

5.
Tafelbild1, Tafelbild2Tafelbild3

6. Challenge:  ??? Tower for Cellular Telephony (11681)

7.
Nächster Online-Wettbewerb über UVa: 27.09.09, 19:00 Uhr (Waterloo ACM Programming Contest Fall 1 2009)



9.

  17.09.2009, 10:00, R 3.026

 
1. Dynamische Programmierung..

2.
Algorithmische Geometrie..

3. Diskussion: 
Convex Hull Finding (681),
                      
Intersecting Lines (378),
                      
Optimal Array Multiplication Sequence (348),


4. Notebook       draft01DW  
                         draft01FD

5. Diskussion: 
SWERC 2008die Problemedie Hinweise, die Ergebnisse

         FAUSS09

6. Tafelbild1, Tafelbild2Tafelbild3

7.  Teamnamen?

8. 
Nächster Online-Wettbewerb über UVa: 19.09.09, 22:00 Uhr (Brazilian National Contest 2009)



8.

 14.09.2009, 10:00, R 3.026


1. Dynamische Programmierung:   Produkt einer Matrizenfolge - Optimal Array Multiplication Sequence (348), Matrix Chain Multiplication (442)
                                                   Minimale Triangulierung eines konvexen Polygons -

2. Algorithmische Geometrie: Nächstes Paar, Convexe Hülle

3. Notebook

4. Teamnamen

5. Tafelbild

6.
Nächster Online-Wettbewerb über UVa: 19.09.09, 22:00 Uhr (Brazilian National Contest 2009)


7.


  7.09.2009, 10:00, R 3.026

1. Dynamische Programmierung: LIS/LDS, LCS, Coin Change, Edit-Distance, Matrizenfolge

2. Algorithmische Geometrie: Nächstes Paar, Convexe Hülle

3. Notebook

4. Teilnahme XXIII Colombian Programming Contest, 05.09.2009
    Christoph Miesel:  Platz   71  /  163,  2 gelöste Probleme: Informants (11659), Burger Time? (11661)
    Felix Dietrich:       Platz    69  / 163,  2 gelöste Probleme: Look-and-Say Sequences (11660),
Burger Time? (11661)
    Dennis Wilfert:      Platz    78  / 163,  2 gelöste Probleme: 
Look-and-Say Sequences (11660), Burger Time? (11661)

5.  Diskussion,
Dennis Wilfert & Felix DietrichIntersection (191)
6.  Diskussion, 
Felix Dietrich: Automatic Correction of Misspellings (11048)
7. 
Diskussion,  Christoph Miesel: Informants (11659)

8. Tafelbild
 
9.
Nächster Online-Wettbewerb über UVa: Sonntag!, 13.09.09, 15:00 Uhr  (Regional Warmup)


6.

    3.09.2009, 9:30, R 3.026

1. Dynamische Programmierung: ...

2. Diskussion 5-ter MiniContest:
Find the Ways! (10219), The Sultan's Successor (167), Getting in Line (216), e-Coins (10306), Intersection (191),
                                                
All Walks of length "n" from the first node (677)

3. Notebook !

4.
!Challenges!:
         Bits (11645),   - siehe
Super Lucky Numbers (10722) in der AM-Seite: Tafelbild + Programme!
         Triangles (585),

         Again Palindrome (10617), Make Palindrome (10453)

5.
Mini-Contest: 06acmTraining3_09.pdf

6. Tafelbild

7.
Nächster Online-Wettbewerb über UVa: 5.09.09, 21:00 Uhr


5.

    31.08.09, 9:30, R 3.026
    


1.
Christoph Miesel: Teilnahme Another Internet Bangladeshi Contest, 22.08, Platz 131 / 239, 2 gelöste Probleme
        Athletics Track! (11646), Mirror Clock (11650)


2. Diskussion 4-ter MiniContest: Lights inside a 3d Grid (11605), Atoms (11606), No Problem (11608), Teams (11609),
                                                Reverse Prime (11610), Sultan and Khairun Shundori (11612)

3. Backtracking: 
8 Queens Chess Problem (750), The Sultan's Successor (167), Getting in Line (216),

4.
Mini-Contest: 05acmTraining31_08.pdf

5. Dynamische Programmierung: LIS/LDS, LCS , Coin Change
                         
NUS_DP,   Kap 8 - Java-Buch

6. Tafelbild

7.
Nächster Online-Wettbewerb über UVa: 5.09.09 !!!



4.


   11.08.09, 9:30, R 3.026
 
1. Diskussion 3-ter MiniContest: Automatic Correction of Misspellings (11048),  Basic wall maze (11049), Dihedral groups (11051),
                                                Wine trading in Gergovia (11054), Homogeneous squares (11055), Killing Aliens in Borg Maze (10307)

2.  Backtracking-Einführung, Nachfolger-Algorithmus für Binärwörtern (Teilmengen), Permutationen

3. 
Vorstellung UVa-Toolkit, Methods to Solve, ..

4.  Analyse Wettbewerbe:  NWERC 2008, NWERC 2007

5.  Analyse Wettbewerbe: SWERC 2008, ACM meets FAU

6. 
Mini-Contest: 04acmTraining11_08.pdf

7.  Tafelbild 1, Tafelbild 2, Tafelbild 3, Tafelbild 4

8.  Nächster Online-Wettbewerb über UVa: 22.08.09, 11:00  !!!


3.

   10.08.09, 9:30, R 3.026

1.  Buch-Empfehlung:  Programming Challenges, die Programme

2.  Mini-Contest:
03acmTraining10_08.pdf

3.  Diskussion 1-ter MiniContest: Another loterry (11628), Ballot Evaluation (11629), Dark roads (11631), Generate random nubmers (11634), Hotel booking (11635)

4.  Diskussion 2-ter MiniContest: Annoying painting tool (11230),  Black and white painting (11231), Cylinder (11232),
                                               Expressions (11234), Grocery store (11236)

5. 
Nächster Online-Wettbewerb über UVa: 22.08.09, 11:00  !!!

6.  TafelBild


2.

   4.08.09, 9:30, R 3.026




1. Felix Dietrich: Teilnahme Internet Bangladeshi Contest, 1.08, Platz 72 / 323, 3 gelöste Probleme
        Hello World! (11636), Temperature Monitoring (11638), Guard the Land (11639)
       
        + gelöste Probleme:  3n+1 Problem (100),   Ecological Bin Packing (102)

1. 
Ulm Local Contest 2007: http://www.informatik.uni-ulm.de/acm/Locals/2007/html/index.html
2.
TafelBild

3.
Mini-Contest: 02acmTraining4_08.pdf

4. Nächster Online-Wettbewerb über UVa: 22.08.09, 11:00

5. Übung: Grocery-Store (11236)  mit Brute-Force lösen, dann 2.te Variante als Vorberechnung in einem String/Array ausgeben


1.

   30.07.09, 9:30, R 3.020

C. Miesel
E. Pavlidis
D. Wilfert
F. Dietrich


1.  Teamnamen
2.  Wettbewerb Online über UVa, 1.08.09, 11:00
3.  Ulm Local Contest 2009: http://www.informatik.uni-ulm.de/acm/Locals/2009/html/index.html
      (11628 - 11635 in Online Judge)
4.  Training-Termine, nächster: Dienstag 4.08, R3.020
5. 
Für Notebook: schnelle Potenzierung + Formel aus 11149 -> Forum
6.  !Challenges!:
        
Triangles (585), Again Palindrome (10617), Make Palindrome (10453)
7.  Kommunikation über google.groups ?
8.  Dennis W. - ZPA-Anmeldung FWP-Fach
9.  Evgeni P., Christoph M., Peter S. und Axel F.: Berichte FAU-Contest ?
10. Persönliches Notebook sequenziell basteln
11. Elligibility Tree: http://cm.baylor.edu/ICPCWiki/attach/Regional%20Rules/eligibilitydecisiontree.pdf
12. Christoph Miesel --> petition for eligibility
13. Felix Dietrich: Vorstellung Lösungen für
Abundance and Perfect Numbers (10914), Power of Matrix (11149), Series of Powers (11190)
14. Mini-Contest: 01acmTraining30_07.pdf



Themen




Graphen:

  - kürzeste Wege (Floyd-Warshall)

  - Tiefen- und Breitensuche

  - topologische Sortierung

  - minimaler Spannbaum

-

[2] S.  251
[3]




[Floyd-Warshall]


[BFS]  [DFS]




[Topologische Sortierung]



[Flooding-Algorithmus]



[Minimal Spannbaum]
[Kruskal] [Prim]


[Bipartite Graphen2
[Matching]
[Maximum Weighted Matching]
....


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)



Nested Dolls (11368), The dog task (670), Crime Wave - The Sequel (10746), Sorting Slides (663), Bob Laptop and Eddie Desktop Barlow (10072), Gopher II (10080),
The Problem with the Problem Setter (10092), Misterious Mountain (10122), Antenna Placement (10349), Rooks (10615),
Gopher Strategy (10804), My T-Shirt suits me (11045), Nuts and Bolts (11138), Factors and Multiples (11159), Weird Fence (11262),
Golden Tiger Claw (11383), Clever Naming Patterns (11418), SAM I AM (11419), Maximizing the ICPC (11439)

Dynamische Programmierung



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

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


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)


Sorting

[2] S. 344, 346


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)


Backtracking


[2] S. 403
[1] 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), Another n-Queen Problem (11195), Sum-up the Primes (10419), 23 out of 5 (10344), Equidivisions (11110), Take the Land (10074), Tree Summing (112), Meta-Loopless Sorts (110), Krypton Factor (129), Bandwidth (140), Anagram Checker (148), Stamps (165), Transportation (301), Lotto (441), The Boggle Game (604), Don't Get Rooked (639), The Hamming Distance Problem (729), Crypt  Kicker (843), Little Bishops (861), Ordering (872), Garden of Eden (10001), How Big Is It (10012), Ouroboros Snake (10040), No Tipping (10123), Doublels (10150), Servicing Stations (10160), Euro Cup 2000 (10186),



Literatur  
1.  Doina Logofătu, Grundlegende Algorithmen mit Java, Vieweg Verlag, ISBN 978-3-8348-0369-6, 2008. (online in Campus)
2.  Doina Logofătu, Algorithmen und Problemlösungen mit C++, Vieweg Verlag, ISBN 978-3-8348-0126-5, 2006. (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.
Programming Challenges, die Programme

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