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

Austragungsort | O 27, SUN-Pool
Datum und Uhrzeit | Freitag, 2. Juli 1999, 13:15 Uhr
Wettbewerbsdauer | 5 Stunden
Betriebssystem | Unix (SUN Solaris)
erlaubte Programmiersprachen | ANSI C, C++, Java, ISO Pascal
verwendete Compiler | gcc, g++, pc
verwendbare Texteditoren | textedit, emacs, xemacs, nedit oder vi (je nach Wunsch)
erlaubte Hilfsmittel | Bücher, Skripte, Listings, Man Pages (man, xman), nichtprogrammierbarer Taschenrechner
verbotene Hilfsmittel | Disketten, 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

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.

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

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

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:

- Musterimplementierung einer Priority Queue
- Pfadinformationsprobleme
- Breitensuche
- Backtracking
- Starke Zusammenhangskomponenten
- Tips & Tricks mit C
- Contest Page von Gerhard Lutz, dem Sieger von 1996

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