International Collegiate Programming Contest

First Round: University of Ulm Local Contest

1. Überblick

Vom 02.-04.11.2001 findet der ACM Northwestern European Regional Programming Contest in Darmstadt statt, an dem Universitäten aus Deutschland, Dänemark, Finnland, Schweden, Norwegen, Island, Großbritannien, Irland, Belgien, Luxemburg und den Niederlanden teilnehmen werden. Die Uni Ulm, die sich seit 1996 sechsmal hintereinander fuer die WM qualifizierte, sucht auch dieses Jahr wieder 12 Top-Programmierer, aus denen dann unsere drei Teams gebildet werden.
Deswegen wird am Freitag, den 06. Juli 2001 ein universitätsinterner Programmierwettbewerb stattfinden, bei dem sich die besten zwölf qualifizieren werden.

Teilnehmen können alle Studenten der Universität Ulm, die das Diplom noch nicht abgeschlossen haben und noch bis Ende 2001 in Ulm bleiben werden.
Insbesondere sind Studenten der ersten beiden Semester eingeladen, am Wettbewerb teilzunehmen (es kostet nichts - ist aber nicht umsonst, traut Euch :-)

Austragungsort	O 27, Linux-Pool
Datum und Uhrzeit	Freitag, 06. Juli 2001, 13:15 Uhr
Wettbewerbsdauer	5 Stunden
Betriebssystem	Linux
erlaubte Programmiersprachen	ANSI C, C++, Java, (Free) Pascal, Haskell
verwendete Compiler	gcc, g++, javac, ppc386, ghc
verwendbare Texteditoren	textedit, emacs, xemacs, nedit oder vi (je nach Wunsch)
erlaubte Hilfsmittel	Bücher, Skripte, Listings, Man Pages (man, xman)
verbotene Hilfsmittel	Taschenrechner, Disketten, Laptop, Handy, FTP, Telnet, WWW, E-Mail

Im Prinzip werden wir den Regional Contest so genau wie möglich simulieren. Der Hauptunterschied ist, daß der Ulmer Wettbewerb ein Einzelwettbewerb sein wird.
Aus den 12 Bestplazierten werden drei Viererteams gebildet. Wer mit wem dann in welches Team geht, dürfen diese 12 unter sich selbst ausmachen. Falls keine Wünsche geäußert werden, gilt folgende Aufteilung als Default:

Plätze 1-3 => Team 1
Plätze 4-6 => Team 2
Plätze 7-9 => Team 3
Plätze 10-12 => Ersatzleute für Team 1, 2 und 3

2. Aufgaben

Bereich	Beispielprobleme
Backtracking	8-Damen-Problem Springertour auf Schachbrett
Graphenprobleme	Kürzeste Route zwischen 2 Städten finden, wobei eine Landkarte gegeben ist Testen, ob ein gegebener gerichteter Graph einen Zyklus enthält
Computational Geometry	Bestimmen, ob sich zwei gegebene Strecken schneiden oder nicht Konvexe Hülle eines Polygons bestimmen
Dynamisches Programmieren	Optimale Klammerung einer Kette von Matrixmultiplikationen A1 * A2 * ... * An, so dass die Anzahl der elementaren Multiplikationen minimiert wird
Zahlentheorie	Summe aller echten Teiler einer gegebenen Zahl berechnen Alle Primzahlen p mit a <= p <= b ausgeben
Parser/Compilerbau	Eingabe: ein arithmetischer Ausdruck als String Ausgabe: das Resultat dieses Ausdrucks Beispiel: Eingabe: "4+3*(7-2)", Ausgabe: 19

Schaut Euch am besten mal die Aufgaben vom letzten Jahr an.

3. Ablauf des Wettbewerbs

Meldung	Bedeutung
Accepted	Programm ist als korrekt akzeptiert. Gratuliere.
Wrong Answer	Programm liefert falsche Antwort
Presentation Error	Algorithmus ist im Prinzip richtig, aber Ausgabe entspricht nicht der gegebenen Spezifikation
Time-Limit exceeded	Algorithmus ist zu langsam, d.h. Ausführungszeit für Beispieleingabe >> 60 sec
Run-Time Error	Programm stürzt ab
Compile-Time Error	Programm läßt sich nicht compilieren

Man hat beliebig viele Versuche, bis man eine "Accepted"-Meldung erhält. Allerdings bekommt man für jeden Fehlversuch 20 Strafminuten zur benötigten Programmierzeit addiert. Achtung: Das heißt nicht, das man dann nach 4:40 h aufhören muss. Man darf auf jeden Fall 5 Stunden lang programmieren. Es wird dann aber so gewertet, als hätte man 5:20 h gebraucht.

4. Wertung

5. Preise

6. Tips zur Vorbereitung

Hier sind ein paar Seiten, die wir (das ACM-Team 1996) während unserer Vorbereitung auf den SWERC 1996 in Zürich erstellt haben:

• Musterimplementierung einer Priority Queue
• Pfadinformationsprobleme
• Breitensuche
• Backtracking
• Starke Zusammenhangskomponenten
• Tips & Tricks mit C

• ISO Pascal ist nicht zu verwechseln mit Turbo Pascal (oder deren Nachfolgern Borland Pascal und Delphi). Der Compiler ist etwas gewöhnungsbedürftig, einige Konstrukte die man aus Turbo Pascal kennt gibt es in ISO Pascal nicht und es gibt keine Funktion zum formatierten Einlesen (vgl. C: "scanf"), was manche Sachen problematisch macht. Man kann sich damit durchschlagen, aber nur, wenn man mit der ISO-Spezifikation vertraut ist.
• C ist die bisher im Local Contest am meisten verwendete Sprache.
• C++ hat jedoch einige Vorteile: es fördert die Deklaration von lokalen Variablen (was Fehler vermeiden kann) und es hat einige zusätzliche Bibliotheken (u.a. die Standard Template Library STL, die komplexe Datenstrukturen und Algorithmen bereitstellt).
  Im Training auf die Finals 2000 haben alle fünf Ulmer Teilnehmer ausschließlich C++ verwendet (mit mehr oder weniger Erweiterungen von C).
• Java bietet mehr Bibliotheken als C++, manche Sachen sind aber wegen der Kapselung in Klassen etwas umständlicher zu realisieren.

7. Empfohlene Literatur zur Vorbereitung und im Wettbewerb

Rivest, Leiserson, Cormen: "Introduction to Algorithms"

Skripte zu den Vorlesungen "Algorithmen" und "Algorithmen 2" von Prof. Dr. Uwe Schöning. (erhältlich im Sekretariat für Theoretische Informatik)

Sedgewick, R.: "Algorithmen"

Handbücher des RRZN Hannover für C, C++, Java, Pascal (erhältlich im Universitätsrechenzentrum, O 26 für je 5-8 DM)

Bronstein, Semendjajew, et al.: "Taschenbuch der Mathematik" (oder andere Formelsammlungen)

8. Fragen