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

AustragungsortO 27, SUN-Pool
Datum und UhrzeitFreitag, 7. Juli 2000, 13:15 Uhr
Wettbewerbsdauer5 Stunden
BetriebssystemUnix (SUN Solaris)
erlaubte ProgrammiersprachenANSI C, C++, Java, ISO Pascal
verwendete Compilergcc, g++, javac, pc
verwendbare Texteditorentextedit, emacs, xemacs, nedit oder vi (je nach Wunsch)
erlaubte HilfsmittelBücher, Skripte, Listings, Man Pages (man, xman)
verbotene HilfsmittelTaschenrechner, 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

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.

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

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