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 2000 in Orlando, Florida aufeinander.

Die Uni Ulm, die sich 1995, 1996, 1997 und 1998 viermal 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 2. Juli 1999 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 2000 in Ulm bleiben werden.

AustragungsortO 27, SUN-Pool
Datum und UhrzeitFreitag, 2. Juli 1999, 13:15 Uhr
Wettbewerbsdauer5 Stunden
BetriebssystemUnix (SUN Solaris)
erlaubte ProgrammiersprachenANSI C, C++, Java, ISO Pascal
verwendete Compilergcc, g++, pc
verwendbare Texteditorentextedit, emacs, xemacs, nedit oder vi (je nach Wunsch)
erlaubte HilfsmittelBücher, Skripte, Listings, Man Pages (man, xman), nichtprogrammierbarer Taschenrechner
verbotene HilfsmittelDisketten, Laptop, Handy, FTP, Telnet, Netscape, E-Mail

Im Prinzip werden wir den ACM Southwestern European Regional Contest , der dann im November stattfindet, 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 fuer Team 1, 2 und 3

2. Aufgaben

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

BereichBeispielprobleme
Backtracking8-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.

4. Ablauf des Wettbewerbs

Zu jeder Aufgabe (bzw. zu so vielen wie in 5 Stunden eben möglich) soll ein C-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) 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

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.

5. 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.

6. Preise

Alle Teilnehmer, die mindestens ein Problem lösen, erhalten: Der Sieger erhält außerdem einen Pokal.

Direkt im Anschluss an den Wettbewerb findet eine Grillparty auf der Terrasse der Neuroinformatik im 4. Stock statt, zu der alle eingeladen sind. Für Getränke und Fleisch wird gesorgt, Salate oder Desserts müssten selbst mitgebracht werden.

7. 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:

8. 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"
Die Programmiersprache C (erhältlich im Rechenzentrum, O 26, für DM 6.50)
The UNIVERSITY OF ULM LOCAL CONTEST 1999 starts in...
5. Mai 1999
Mark Dettinger <dettinger@acm.org>