Im November 2009 findet in Nürnberg der ACM Northwestern European Regional Programming Contest statt, an dem Universitäten aus Belgien, Dänemark, Deutschland, Finnland, Großbritannien, Irland, Island, Luxemburg, den Niederlanden, Norwegen und Schweden teilnehmen werden. Die Uni Ulm, die sich 1996-2004 neunmal hintereinander für die WM qualifizierte, sucht auch dieses Jahr wieder 12 Top-Programmierer, aus denen dann unsere drei Teams für den Regional Contest gebildet werden. Deswegen wird am Freitag, den 17. Juli 2009 ein universitätsinterner Programmierwettbewerb stattfinden.
Teilnehmen können alle Studenten der Universität Ulm, die das Diplom noch nicht abgeschlossen haben und bis Ende 2009 in Ulm bleiben werden. Insbesondere sind Studenten der ersten beiden Semester eingeladen, am Wettbewerb teilzunehmen (es kostet nichts - ist aber nicht umsonst, traut Euch :-)
Hier folgt eine Zusammenfassung der wichtigsten Rahmenbedingungen:
| Austragungsort | O 27, Linux-Pool |
| Datum und Uhrzeit | Freitag, 17. Juli 2009, 13:00 Uhr |
| Wettbewerbsdauer | 5 Stunden |
| Umfang | 8 Aufgaben |
| Betriebssystem | Linux |
| erlaubte Programmiersprachen | ANSI C, C++, Java, (Free) Pascal, Haskell |
| eingesetzte Compiler | gcc, g++, javac, ppc386, ghc |
| verwendbare Texteditoren | vi, emacs, xemacs, nedit, joe, ... |
| erlaubte Hilfsmittel | Bücher, Skripte, Referenzen, Listings, man-pages |
| verbotene Hilfsmittel | elektronische Geräte, Datenträger, (Netzwerk-)Kommunikation |
Im Prinzip simulieren wir damit den Regional Contest so genau wie möglich. Der Hauptunterschied ist, daß der Ulmer Wettbewerb ein Einzelwettbewerb ist. Für den Regionalwettbewerb werden wir aus den Bestplazierten drei Teams bilden, wobei Team 3 grundsätzlich für Studenten aus dem 1.-3. Semester reserviert ist.
| 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 daß 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 | Auswertung eines arithmetischen Ausdrucks, z.B. Eingabe: "4+3*(7-2)", Ausgabe: 19 |
Schaut Euch am besten mal die Aufgaben vom letzten Jahr an. 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).
compile dateiname übersetzt Euer Programm indem es anhand der Dateiendung den passenden Compiler aufruft:
| Dateiname | Compiler | Version |
|---|---|---|
| *.c | gcc -Wall -g -lm -O3 | gcc 4.3.3 |
| *.cc *.cpp *.C | g++ -Wall -g -lm -O3 | g++ 4.3.3 |
| *.java | javac | Sun JDK 1.6 |
| *.p *.pas | ppc386 -vew -g -O2 | Free Pascal 2.2.2 |
| *.hs | ghc -Wall -O | ghc 6.8.2 |
Das compile-Skript erstellt eine ausführbare Datei mit demselben Namen wie das Programm ohne Endung bzw. im Falle von Java eine Datei name.class, die mit dem Befehl java name ausgeführt werden kann.
Die Jury verwendet dasselbe compile-Skript wie Ihr.
Ihr solltet den Compiler nicht manuell aufrufen sondern nur mit dem compile-Skript, da nur dann garantiert ist, daß dasselbe passiert wie später bei der Jury (die z.B. das Skript kurzfristig ändern kann).
Wer glaubt, sein Programm sei korrekt, der schickt es an die Jury. Die Jury compiliert das Programm, testet es dann mit (geheimen) Beispieleingaben und schickt schließlich eine der folgenden Meldungen zurück:
| Meldung | Bedeutung |
|---|---|
| CTE (Compile-Time Error) | Die Übersetzung mit dem compile-Skript war nicht erfolgreich. Sollte eigentlich nicht vorkommen... |
| TLE (Time-Limit Exceeded) | Das Programm wurde ausgeführt, terminierte aber nicht innerhalb der vorgegebenen Zeitschranke, die standardmäßig 10 Sekunden beträgt. Die Jury wird mit der 10-Sekunden-Schranke großzügig umgehen (vor allem bei Java- und Haskell-Programmen). Wenn dies vorkommt, heißt es, daß Euer Programm in eine Endlosschleife geraten ist, oder daß Euer Algorithmus eine zu hohe Komplexität hat. |
| RTE (Runtime Error) | Das Programm terminierte nicht mit Rückgabewert 0.
Dies ist normalerweise ein Laufzeitfehler.
Es ist möglich, künstliche Laufzeitfehler zu erzeugen, z.B. in C mit return 1 oder assert(...).
Division durch 0 oder ähnliches erzeugt nicht unbedingt Laufzeitfehler (wir übernehmen keine Garantie).
|
| WRA (Wrong Answer) | Die Ausgabe des Programms für die Eingabedatei der Jury ist fehlerhaft. Die Eingabedatei der Jury ist größer als der 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. |
| PRE (Presentation Error) | Die Ausgabe des Programms für die Eingabedatei der Jury ist inhaltlich richtig, genügt jedoch Forderungen der Problemstellung nach spezieller Formatierung nicht (zuviele/zuwenige Leerzeichen/-zeilen, falsche Texte, Groß-/kleinschreibung nicht beachtet, etc). Wenn Ihr Eure Ausgabe so erzeugt, wie der Sample-Output auf der Problemstellung, sollte es keine Probleme geben. Erzeugt keine unnötigen Leerzeilen und Leerzeichen, es sei denn sie sind explizit verlangt. |
| ACC (Accepted) | Problem gilt als gelöst, Gratulation! Für jedes gelöste Problem bekommt Ihr einen Luftballon an den Monitor geklebt. Jede Aufgabe hat ihre eigene Farbe. Wenn sich also die Luftballons in Eurer Umgebung häufen, solltet Ihr zusätzlich motiviert sein... |
| CRV (Contest-Rule Violation) | Ein Verstoß gegen die Regeln des Wettbewerbs kann mehr oder weniger harmlos sein.
Die eingereichten Programme müssen u.a. den folgenden Kriterien genügen:
|
Die Jury bewertet nach dem Kriterium, das ihr als erstes auffällt. Der Unterschied zwischen TLE, WRA und PRE ist leider etwas fließend. Fehlerhafte Submissions, d.h. alle außer ACC, bringen 20 Minuten Zeitstrafe (aber nur, wenn das Problem letztendlich gelöst wurde). Um ein ACC 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, daß 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. Kommunikation unter den Teilnehmern ist nicht erlaubt (und das meinen wir ernst).
Um 12:15 Uhr wird der Linux-Pool geschlossen. Die Rechner werden für den Wettbewerb initialisiert, d.h. Eure Verzeichnisse werden gelöscht. Anschließend, etwa um 13:00 Uhr (aber nicht früher) geht es los.
Der Wettbewerb dauert dann genau 5 Stunden. Kurz vor Ende des Wettbewerbs kann es sein, daß die Jury viel zu tun hat und Ihr deswegen nicht mehr während des Wettbewerbs Antworten auf Eure Submissions bekommt. Es gilt:
Erfolgreiche Teilnehmer erhalten eine Urkunde und für die drei Bestplazierten gibt es Medaillen. Der Sieger erhält außerdem einen Pokal.
Die endgültige Rangliste ist ein Anhaltspunkt für die Team-Zuordnung für unsere Teilnahme am südwesteuropäischen Regionalwettbewerb im November in Nürnberg. Wir planen zwar damit, daß wir auch diesmal mit 3 Teams teilnehmen können, wissen das aber noch nicht genau (das hängt davon ab, wieviele Plätze dort zur Verfügung stehen und wieviele Teams von anderen Unis dort teilnehmen werden). Ein Team besteht aus drei Programmierern und einer Reserve. Das Team 3 ist grundsätzlich für Studenten aus dem 1.-3. Semester reserviert, während die Teams 1 und 2 für Studenten bis zum 9. Semester offen sind. (Letzteres ist eine Vorgabe für den Regionalwettbewerb - hier in Ulm dürfen auch Studenten aus höheren Semestern teilnehmen.) Der Coach stellt die Teams im Einvernehmen mit den Bestplazieren des Lokalwettbewerbs auf. Bis auf die eben erwähnten Beschränkungen sieht das üblicherweise so aus:
Hier sind ein paar Seiten, die Euch als Implementation für häufig vorkommende Algorithmen dienen können:
Um Einfluß auf die Wahl der Programmiersprache zu nehmen, hier einige Kommentare zu den erlaubten Sprachen:Empfohlene Literatur zur Vorbereitung und im Wettbewerb:
Viel Erfolg!