Die Association for 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 80 Teams der Welt treffen schließlich bei den World Finals aufeinander. Die Universität Ulm war seit 1996 schon 9 mal bei den World Finals vertreten, und belegte im Jahr 2000 den dritten Platz!
Am Freitag, den 2. Februar 2007, veranstaltet das ACM Student Chapter der Universität Ulm einen Online-Programmierwettbewerb. Dieser Wettbewerb soll als Vorbereitung für den lokalen Ausscheidungswettbewerb des ACM International Collegiate Programming Contests (ICPC) dienen, der im kommenden Sommersemester stattfinden wird.
Teilnehmen können alle Studenten der Universität Ulm, die das Diplom noch nicht abgeschlossen haben und bis Ende 2007 in Ulm bleiben werden. Insbesondere sind Studenten der ersten beiden Semester eingeladen, am Wettbewerb teilzunehmen.
Hier folgt eine Zusammenfassung der wichtigsten Rahmenbedingungen:
| Contest Website | www.spoj.pl/ULM07/embed/info/ |
| Datum und Uhrzeit | Freitag, 2. Februar 2007, 17:00 Uhr |
| Wettbewerbsdauer | 3 Stunden |
| Teamgröße | maximal 3 Personen |
| Umfang | 4 Aufgaben |
| erlaubte Programmiersprachen | C, C++, Java, Pascal, Haskell, Python und andere vom Online Judge unterstützte Sprachen |
| erlaubte Hilfsmittel | alles was einem bei den Aufgaben helfen kann; Ausnahme: keine Kommunikation mit Personen außerhalb des Teams. |
Um an dem Wettbewerb teilnehmen zu können, sollte man einen Account beim Sphere Online Judge anlegen. Anschließend einfach der Gruppe Contest ULM07 group beitreten, indem man als Passwort den Nachnamen (erster Buchstabe groß, den Rest klein) eines weltweit bekannten Wissenschaftlers eingibt, der in Ulm geboren wurde und Albert mit Vornamen hieß; wer nicht draufkommt, kann mir auch eine Email schreiben an Adrian.Kuegel [at] uni-ulm.de.
Es wird 4 Aufgaben geben, die jeweils nur grundlegende Kenntnisse aus der Informatik oder Mathematik erfordern. Auf der Contest Website sind zwei Beispielaufgaben zu finden. Es empfiehlt sich, die Aufgaben vor dem Wettbewerb zu lösen um zu sehen wie das Einschicken von Programmen funktioniert.
Die Aufgabenstellung erfolgt in englischer Sprache. Alle sind nach dem folgenden Muster zu lösen:
Die Aufgaben sind nicht nach Länge oder Schwierigkeitsgrad geordnet. Wir empfehlen: lest Euch am Anfang alle Aufgaben durch (oder zumindest bis Ihr denkt, Ihr habt eine hinreichend einfache gefunden) und werft gelegentlich einen Blick auf die aktuellen Ranglisten (wurde eine Aufgabe bereits von vielen gelöst, ist sie vielleicht einfach).
Zu jeder Aufgabe (bzw. zu so vielen wie in 3 Stunden eben möglich) soll ein Programm geschrieben werden, das diese Aufgabe löst. Bevor Ihr eine vermeintliche Lösung einsendet, solltet Ihr sie mit dem Sample-Input testen und Eure Ausgabe mit dem Sample-Output vergleichen. Achtet insbesondere auf die Schreibweise bei Wörtern; selbst wenn nur zwei Buchstaben verdreht sind gilt die Ausgabe als falsch.
Zu beachten ist zudem, dass in manchen Programmiersprachen das Programm eine gewisse Form haben muss, z. B. in Java muss die Hauptklasse "Main" heißen. Siehe dazu hier.
Wer glaubt, sein Programm sei korrekt, der schickt es mit dem submit Formular an den Online Judge. Der Online Judge compiliert das Programm, testet es dann mit (geheimen) Beispieleingaben und zeigt schließlich eine der folgenden Meldungen unter status an:
| Meldung | Bedeutung |
|---|---|
| compilation error | Die Übersetzung war nicht erfolgreich. Sollte eigentlich nicht vorkommen... |
| time limit exceeded | Das Programm wurde ausgeführt, terminierte aber nicht innerhalb der vorgegebenen Zeitschranke, die standardmäßig 10 Sekunden beträgt. Wenn dies vorkommt, heißt es, dass; Euer Programm in eine Endlosschleife geraten ist, oder dass Euer Algorithmus eine zu hohe Komplexität hat. |
| runtime error | In Klammern wird dabei noch angezeigt um welche Art von Laufzeitfehler es sich handelte.
Es ist möglich, künstliche Laufzeitfehler zu erzeugen, z.B. in C mit return 1 oder assert(...).
|
| wrong answer | Die Ausgabe des eingeschickten Programms für die Eingabe des Online Judges ist fehlerhaft. Die Eingabe umfasst mehr als den Sample-Input und überprüft auch Fälle, die der Spezifikation entsprechen, an die Ihr vielleicht nicht gedacht habt. D.h. eine korrekte Abarbeitung des Sample-Input ist notwendig, aber nicht hinreichend für eine korrekte Lösung. |
| accepted | Problem gilt als gelöst, Gratulation! |
Fehlerhafte Submissions, d.h. alle außer accepted, bringen 20 Minuten Zeitstrafe (aber nur, wenn das Problem letztendlich gelöst wurde). Um ein accepted zu erreichen könnt Ihr soviele Submissions machen, wie Ihr wollt. Wir empfehlen spätestens nach der 10. fehlerhaften Submission zur selben Aufgabe ein neues Problem anzufangen.
Neben dem Abschicken einer Lösung könnt Ihr während des Wettbewerbs per e-mail Fragen in englischer Sprache an die Jury stellen. Wir werden Fragen wie "Is the algorithm XYZ correct for problem Q?" oder "Does the jury-input contain such-and-such test-cases?" nicht sinnvoll beantworten. D.h. fragt nur, wenn Ihr denkt, dass Ihr einen Fehler in der Aufgabenstellung gefunden habt. Im Zweifelsfall gilt: Macht keine Annahmen, die in der Aufgabenstellung nicht spezifiziert sind. Fragen von allgemeinem Interesse werden mit einer Antwort an alle bedacht. Weitergeben von Lösungen an andere Teams ist nicht erlaubt.
Um Einfluß auf die Wahl der Programmiersprache zu nehmen, hier einige Kommentare zu den erlaubten Sprachen:
Fragen aller Art (Contestablauf, Programmiersprachen, Aufgaben) könnt Ihr jederzeit an Adrian.Kuegel [at] uni-ulm.de schicken. Oder löchert einfach jemanden den Ihr kennt und der schon mal teilgenommen hat.
Viel Erfolg!