International Collegiate Programming Contest

First Round: University of Ulm Local Contest

1. Überblick

Die Association of Computing Machinery (ACM), die größte Informatikervereinigung der Welt, veranstaltet jährlich eine Programmierweltmeisterschaft für Studenten. Hierzu werden zunächst lokale, dann regionale Wettbewerbe ausgetragen. Die besten der Welt treffen schließlich bei den World Finals im März 2001 in Vancouver, Kanada aufeinander.

Im Herbst 2000 findet der ACM Mid-Central European Regional Programming Contest in Freiburg statt, an dem Universitäten aus Deutschland, Tschechien, Österreich und der Schweiz teilnehmen werden. Die Uni Ulm, die sich seit 1996 fünfmal 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 7. Juli 2000 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 zum März 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, SUN-Pool
Datum und Uhrzeit Freitag, 7. Juli 2000, 13:15 Uhr
Wettbewerbsdauer 5 Stunden
Betriebssystem Unix (SUN Solaris)
erlaubte Programmiersprachen ANSI C, C++, Java, ISO Pascal
verwendete Compiler gcc, g++, javac, pc
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, Netscape, 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 11 Bestplazierten und dem Organisator (der eine Wildcard erhält) 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-2, Org. => Team 1
Plätze 3-5 => Team 2
Plätze 6-8 => Team 3
Plätze 9-11 => Ersatzleute für Team 1, 2 und 3

2. Aufgaben

Die 8 Aufgaben werden aus verschiedenen Bereichen der Informatik kommen. Bereiche, die wahrscheinlich dabei sein werden, sind

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 A₁ * A₂ * ... * A_n, 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

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 A₁ * A₂ * ... * A_n, 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

Zu jeder Aufgabe (bzw. zu so vielen wie in 5 Stunden eben möglich) soll ein Programm geschrieben werden, das diese Aufgabe löst. Wer glaubt, sein Programm sei korrekt, der schickt es mit dem Befehl submit problemname.(c|C|pas|java) an die Jury. Die Jury compiliert das Programm, testet es dann mit Beispieleingaben und schickt schließlich eine der folgenden Meldungen per e-mail zurück.

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

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

Sieger ist, wer die meisten korrekten Programme schafft. Bei Gleichstand entscheidet die Summe der Zeiten, zu denen die korrekten Programme mit submit abgeschickt wurden. Je niedriger diese Summe, desto besser. Außerdem werden noch 20 Strafminuten pro Fehlversuch angerechnet. Fehlversuche werden allerdings nur für Programme gezählt, die man letztendlich doch als korrekt gewertet bekam.

5. Preise

Alle Teilnehmer, die mindestens ein Problem lösen, erhalten:

eine Urkunde,
zwei Software-Pakete (IBM Visual Age for C++ und IBM Visual Age for Java) und
ein ACM-Contest-T-Shirt.

Für die drei Bestplazierten gibt es Medaillen. Der Sieger erhält außerdem einen Pokal.

6. Tips zur Vorbereitung

Die beste Vorbereitung besteht darin, Probleme vergangener ACM-Wettbewerbe zu lösen, um eine Vorstellung von der Art der Aufgaben zu bekommen.

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

Ohne damit Einfluß auf die Wahl der Programmiersprache zu nehmen, hier einige Kommentare zu den erlaubten Sprachen:

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.

Grundsätzlich sind alle gestellten Aufgaben in allen Sprachen lösbar --- schließlich geht's ja um die Algorithmen und nicht um die Sprachen. Bei manchen Problemen macht man sich das Programmieren durch die Wahl einer geeigneten Sprache leichter.

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

... aller Art (Contestablauf, Programmiersprachen, Aufgaben) könnt Ihr jederzeit an Walter Guttmann schicken. Oder löchert einfach jemanden den Ihr kennt und der schon mal teilgenommen hat.

The UNIVERSITY OF ULM LOCAL CONTEST 2000 starts in...

19. April 2000

Walter Guttmann

Austragungsort	O 27, SUN-Pool
Datum und Uhrzeit	Freitag, 7. Juli 2000, 13:15 Uhr
Wettbewerbsdauer	5 Stunden
Betriebssystem	Unix (SUN Solaris)
erlaubte Programmiersprachen	ANSI C, C++, Java, ISO Pascal
verwendete Compiler	gcc, g++, javac, pc
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, Netscape, E-Mail