Nachdem ich im letzten Beitrag zur Informatik-Olympiade beschrieben habe, was man überhaupt an der SOI macht, werde ich heute ein Beispiele für Aufgaben geben.

Die Aufgabe, die ich vorstellen werde, trägt den Namen „Two Tables“ und ist hier abrufbar.

In der Aufgabe geht es darum, dass eine grosse Festgemeinschaft auf zwei Tische verteilt werde muss, jedoch gewisse Personen sich nicht verstehen und daher nicht am selben Tisch sitzen wollen. Um das Beispiel aus der Aufgabenstellung zu verwenden: Richard mag Bob nicht und Steve mag Richard nicht. Also muss Richard am einen Tisch sitzen und Bob und Steve am zweiten Tisch. Gefragt ist nun die Anzahl Möglichkeiten, die Gäste auf die beiden Tische zu verteilen.

Aus diesem Beispiel sieht man bereits, dass diese drei Personen als eine betrachtet werden können, da wenn eine davon an einen Tisch platziert wird, ist für alle anderen klar, wo sie sitzen müssen. Was man auch leicht erkennt, ist die Tatsache, dass es für jede Person zwei Möglichkeiten gibt, sie zu platzieren, an den linken oder den rechten Tisch. Für die Lösung muss also die Anzahl solcher Gruppen bestimmt werden. Die Lösung ist anschliessend 2^Gruppenzahl.

Wie kann nun die Anzahl Gruppen bestimmt werden und weiter Gruppen erkannt werden, welche nicht platziert werden können (z.B. wenn im obigen Beispiel Bob und Steve sich nicht vertragen würden). Dies kann leicht mit einem bestehenden Algorithmus namens Breitensuche herausfinden. Dazu starten wir bei einer beliebigen Person und geben ihr die Nummer 1. Alle Personen, mit der sie sich nicht verträgt geben wir die Nummer 2 und besuchen diese der Reihe nach. So verfahren wir solange, bis eine Gruppe vollständig besucht ist. Wird während dem Durchgehen eine Person entdeckt, die bereits eine Nummer hat, überprüfen wir einfach, ob beide gerade bzw. ungerade sind oder ob die eine ungerade und die Andere geraden ist. Ist das Zweite der Fall, ist es kein Problem, da alle mit einer geraden Nummer am einen Tisch sitzen und die mit einer ungeraden Nummer am anderen. Ist das Erste der Fall haben wir eine Gruppe entdeckt, die nicht platziert werden kann und somit ist die Lösung der gesamten Aufgabe, dass es keine Möglichkeit gibt.

Um die Anzahl der Gruppen zu bestimmen, zählen wir, wie oft wir eine solche Suche starten müssen, um alle Personen zu besuchen.

Wie aus dieser Beispielaufgabe ersichtlich wird, geht es an der Informatik-Olympiade weniger ums Programmieren selbst, sondern vielmehr um logisches Überlegen und etwas Fantasie, um ein Problem etwas anders zu sehen und zu sehen, worauf es ankommt.