Erste Runde 2012

Resultate der Ersten Runde

Die folgenden Teilnehmer haben sich für die zweite Runde qualifiziert:

Rang Teilehmer Punkte (max: 60)
1. Johannes Kapfhammer 47.5
2. André Ryser 47
3. Peter Müller 43.5
4. Lukas Roth 31.5
5. Janis Peyer 30.5
6. Marco Keller 26.5
7. Michael Baumann 26
8. Cyrill Künzi 24.5
9. Ulrich Brodowsky 23.5
9. Cedric Münger 23.5
11. Cédric Neukom 23
12. Benjamin Schmid 22
13. Sammy Jäger 21.5
14. Livio Ciorciaro 21
14. Dimitri Wessels 21
16. Ramon Aerne 20
17. Alexander Kayed 18.5
18. Timon Stampfli 15
18. Patrick Eigensatz 15
18. Michael Aerni 15
21. Florian Wernli 14.5
22. Nicolas Da Mutten 14
23. Valentin Hartmann 13.5
24. Florian Eigenmann 12.5
24. Köbi Meier 12.5
26. Lorenz Brun 12
27. Filip Vucelic
28. Christian Schäpper
29. Cedric Tompkin

Für die erste Runde der SOI 2012 haben wir 6 knifflige Aufgaben entworfen. Es gibt verschiedene Arten von Aufgaben. Drei der Aufgaben sind praktisch: Du sollst zu diesen Aufgaben ein komplettes Programm entwickeln, welches die Aufgabe löst, und den Quelltext einschicken. Bei den zwei theoretischen Aufgaben liegt das Augenmerk auf den mathematischen Aspekten, die mit logischen Überlegungen analysiert werden um anschliessend einen Lösungsansatz in Worte zu fassen. Die letzte Aufgabe ist die Kreativaufgabe, wo es darum geht ein Programm zu entwickeln, welches interaktiv gegen die Programme der anderen Teilnehmer antritt. Die Aufgabe ist so gewählt, dass sie nicht optimal gelöst werden kann. Allerdings gibt bereits ein einfaches Programm Punkte.

Die Aufgabenstellungen gibt es hier auf der Webseite.

Aufgabe Typus
Posters praktisch
Eurokrise praktisch
Zusammengesetzte Wörter praktisch
Quellcode-Analyse theoretisch
Armee theoretisch
Ameisenhügel kreativ

Einsendungen und Bewertung

Am besten verwendest du das Upload-Formular, das bei den jeweiligen Aufgaben verlinkt ist, um deine Lösungen einzuschicken. Als Einsendung sollst du entweder die Datei mit der Lösung direkt abgeben, oder falls sie aus mehreren Dateien besteht, als Archiv einsenden.

Falls du Probleme beim Einsenden hast, kannst du deine Lösungen auch direkt per e-mail an round1@soi.ch senden (schreibe in diesem Fall umbedingt deinen vollen Namen und SOI-Loginname). Wichtig: Wir werden in diesem Fall deine Einsendung bestätigen. Solltest du also keine Bestätigung erhalten, versuche erneut einzusenden.

Alle Aufgaben haben für die Bewertung dasselbe Gewicht.

Praktische Aufgaben

Als Einsendung sollst du den Quelltext abgeben.

Sende bitte keine kompilierten Programme, sondern lediglich den Programmcode. Wir werden kompilierte Programme nicht ausführen. Versuche dich nach Möglichkeit auf nur eine Quelltextdatei zu beschränken um Übersicht und Kompilieren nicht zusätzlich zu komplizieren. Deine Quelltextdatei sollte einige Kopfzeilen enthalten mit den folgenden Informationen: Gelöste Aufgabe, Programmiersprache, Username.

Beispiel in C++:

/*
  Task: sample
  Lang: C++
  User: chuck
*/
Bewertung

Ein Programm, das alle unsere Testfälle innerhalb der Zeitlimite (einige Sekunden) korrekt löst, erhält die maximale Punktzahl. Diese Testfälle sind nicht öffentlich und du kannst dein Programm vorher nicht auf ihnen ausprobieren.

Bei der Zeitbeschränkung geht es um die asymptotische Laufzeitkomplexität deines Programms. Das heisst, du solltest die Laufzeit von Monaten auf Sekunden optimieren, nicht aber von 5s auf 3s. Des Weiteren bist du frei, wie viel Speicher du beanspruchst, solange es in einem vertretbaren Rahmen bleibt (so ca. 100MB).

Falls dein Programm schnell und korrekt ist, bekommst du die maximale Punktzahl. Für ein korrektes aber langsames Programm verteilen wir Teilpunkte (je nachdem wie langsam dein Programm ist) Ein schnelles aber (teilweise) falsches Programm wird (fast) keine Punkte erzielen.

Theoretische Aufgaben

Wir haben eine kleine Hilfestellung zusammengestellt, solltest du dich fragen, wie eine perfekte Lösung einer theoretischen Aufgabe aussieht. Schick uns deine Lösung auf jeden Fall auch wenn sie sich nicht genau an diese Richtlinie hält, du kannst auch dann noch viele Punkte erreichen.

Du kannst die Lösungen als Plaintext, PDF, Postscript, OpenOffice-Dokument, Word-Dokument oder als gescanntes Bild senden.

Bewertung

Deine Lösung wird zur Bewertung auf Korrektheit und Vollständigkeit überprüft. Für die volle Punktzahl sind Quelltext (das kann auch Pseudocode sein) und eine Beschreibung der optimalen Lösung, ein «Korrektheitsbeweis» sowie eine Abschätzung der Zeit- und Speicherkomplexität nötig. Weitere Informationen zu diesen Punkten findest du in den oben verlinkten HowTo Dateien.

Kreativaufgabe

Wir stellen ein Server-Programm zur Verfügung, mit dem du deine Programme gegeneinander testen kannst. Teil des Downloads sind untereinander äquivalente Beispielprogramme in vielen verschiedenen Programmiersprachen. Diese Beispielprogramme verfolgen eine ganz einfache Strategie. Wenn deine Lieblingssprache nicht dabei ist, dann kannst du gerne im Forum danach fragen, und wir werden dann nach Möglichkeit ein Beispielprogramm in dieser Programmiersprache schreiben.

Als Einsendung sollst du den Quelltext abgeben.

Bewertung

Ein Programm, dass die Beispielprogramme zuverlässig schlägt erhält die Hälfte der Punkte. Die andere Hälfte der Punkte wird im Kreativaufgaben-Turnier am SOI-Tag anhand der Rangliste verteilt. (Der SOI-Tag findet dieses Jahr am 14. Januar statt)