Ad-hoc Strategies

This wiki article doesn't exist in English. We will display it in German for you instead.

Written by Stefanie Zbinden.

Einige Aufgaben der SOI und IOI lassen sich nicht mit einem bestimmten, schon bestehenden Algorithmus lösen, sondern brauchen eigene, kreative Lösungsansätze. Diese Aufgaben nennt man Ad-hoc Aufgaben und sind meine persönlichen Lieblingsaufgaben.

Beispiel einer Ad-hoc Aufgabe

IOI 2016 Molecules

Ein gutes Beispiel einer Ad-hoc Aufgabe ist von der IOI 2016 “molecules”: Gegeben sind die Gewichte von nn Molekülen und ein Detektor, der die Moleküle entdeckt, falls ein Subset von Molekülen existiert, dessen Gewicht im Bereich des Detektors liegt. Die Bedingungen sind, dass der Gewichtsunterschied zwischen dem leichtesten und dem schwersten Molekül kleiner gleich der Spannweite des Detektors ist. Die Frage ist nun, ob der Detektor die Moleküle erkennen kann, und falls ja, dank welchem Subset (also die Summe welches Subsets im Bereich des Detektors liegt).

Als Beispiel nehmen wir die Moleküle mit den Gewichten 1,2,31,2,3 und einen Detektor, der die Erkennungsbreite 77 bis 99 hat. Hier ist es nicht schwer, herauszufinden, dass es nicht möglich ist, ein Subset zusammenzustellen, welches die Summe 7,87,8 oder 99 hat, da die maximale Summe 66 ist. Im allgemeinen Fall ist es jedoch schon sichtlich schwieriger.

Lösungsidee

Wie in vielen Ad-hoc Problemen ist es hier sinnvoll, die Elemente der Grösse nach zu ordnen. Es bleibt die Frage, was man mit der etwas merkwürdigen Nebenbedingung anstellen kann. Nach einigem Überlegen und Ausprobieren kann man auf folgende Idee kommen: wenn man eine Summe von kk Gliedern hat, die kleiner (oder grösser) als der Bereich des Detektors ist, kann man ein beliebiges Element austauschen, sodass die Summe kleiner oder im Bereich (oder eben grösser oder im Bereich) des Detektors ist. Die Limits erlauben es nicht, alle beliebigen Subsets als Summe auszuprobieren, doch man kann je die maximale und minimale Summe ausrechen die für kk Elemente existiert (wobei 1kn1 \leq k\leq n). Dies hilft einem für folgendes: wenn die minimale und maximale Summe für kk Elemente je kleiner (oder grösser) als der Bereich ist, gibt es sicherlich keine Lösung mit kk Elementen (denn jede Summe liegt zwischen dem kleinsten und grössten Element). Existiert aber ein kk, bei dem die minimale Summe kleiner als der Bereich und die maximale Summe grösser ist, können wir immer eine Lösung finden. Dies, indem wir mit dem Subset für die minimale Summe starten und dann so lange die kleinen Elemente löschen und dafür die grösseren einfügen bis wir im Bereich sind. Durch unsere obige Bemerkung wissen wir, dass wir den Bereich nicht “überspringen” können und daher mindestens einmal darin landen werden.

IOI 2015 Boxes

Eine andere Ad-hoc Aufgabe ist Boxes von der IOI 2015. Die Aufgabe geht folgendermassen: man hat nn Personen, verteilt auf einem Kreis. Amir will nun jeder Person eine Box verteilen. Er kann maximal kk Boxen gleichzeitig tragen und will möglichst schnell fertig sein. (Zeit braucht nur das Laufen). Er endet und startet am Punkt 00. Das Programm soll nun bestimmen, wie lange Amir mindestens braucht. Als Input ist die Anzahl Personen nn, die Anzahl Boxen, die Amir gleichzeitig tragen kann kk, die Grösse des Kreises mm und für jede Person einen Index aia_i, wo auf dem Kreis sie sich befindet.

Nun kann man gewisse Aussagen machen über Amirs Verhalten. Zum Beispiel ist es einfach zu sehen, dass Amir immer kk Geschenke mitnimmt, denn auch wenn er sie nicht verteilt, wird er nicht langsamer dadurch sie mitzutragen. Eine andere Beobachtung ist, dass er sie auch alle verteilen wird (sofern er an mindestens kk Personen vorbeigeht).

Bevor ihr weiterlest, überlegt doch selbst, was für Beobachtungen man noch machen kann. Als Denkhilfen könnt ihr folgende Fragen verwenden: An wen verteilt Amir die Boxen? Wie sehen die Laufwege von Amir aus?

Passt auf: Wenn ihr Vermutungen anstellt, versucht sie zu beweisen oder ein Gegenbeispiel zu finden. Es gibt viele Ansätze, die richtig aussehen können aber nur meistens stimmen aber nicht immer. Stützt sich euer Code auf solche Annahmen, wird er bei wenigen Testfällen fehlschlagen und ihr werdet Mühe haben ihn zu debuggen und so viel Zeit verbraten.

Ich hoffe ihr habt nun alle eure eigenen Ideen gesammelt. Und wenn nicht: auch nicht schlimm. Jemand sagte mir einmal folgendes: Die Lösung eines Problems hilft einem dann weiter (für spätere Probleme), wenn man sie entweder selbst gefunden oder lange darüber nachgedacht und dann die Lösung angeschaut hat.

Wir bemerken, dass Amir zwei Möglichkeiten hat, Boxen zu verteilen: * Er macht eine Runde, also er startet in 00, dann geht er zu 1,2,1, 2, \ldots bis nn und von dort geht er wieder zu 00. Wichtig ist, dass die Reihenfolge, in der Amir sich bewegt, keine Rolle spielt, ob er also im oder gegen den Uhrzeigersinn wandelt, ist egal. * Er geht bis zu einem gewissen Punkt und dreht dann um und geht so zurück.

Nun, was passiert, wenn er zweimal einen vollen Kreis geht? Dafür markieren wir alle Personen, denen Amir eine Box gegeben hat als Punkte auf dem Kreis. Wir bemerken zwei Dinge: * Beim ersten Kreis, den Amir gemacht hat, hat er genau kk Boxen verteilt. Falls beim zweiten Rundgang weniger als kk Boxen verteilt wurden (das geht nur, wenn es der letzte war und somit keine Personen mehr übrig sind, an die man Boxen verteilen kann, sonst verteilt Amir einfach mehr), fügen wir einfach so viele Punkte bei 00 ein, bis es insgesamt 2k2k Punkte auf dem Kreis sind. * Auf einer Hälfte des Kreises hat es mindestens kk Punkte. Dabei zählt 00 zu beiden Hälften (und falls m=2l+1m=2l+1, also ungerade, zählt auch l+1l+1 zu beiden Hälften, da es auf beide Richtungen gleich weit vom Nullpunkt entfernt ist)

Wir könnten also folgendes machen: Amir verteilt kk Boxen auf der Seite, auf der es mehr hat (sagen wir, es sei die linke Seite) und macht dann einen Kreis, um die restlichen Boxen zu verteilen. Dies ist sicher nicht schlechter, als wenn man zwei Kreise macht (in den meisten Fällen sogar besser). Wir haben also die Laufzeit von Amir optimiert, in dem wir ihn einen Kreis weniger gehen lassen. Somit wissen wir folgendes: Amir macht höchstens einen Kreis. Da die Reihenfolge des Boxenverteilens nicht daraufankommt, setzen wir sie folgendermassen fest: * Amir macht einen Kreis und verteilt dabei xx Boxen auf die linke Seite und kxk-x auf die rechte Seite. (Falls Amir keinen Kreis macht, lässt er diesen Schritt aus.) * Amir verteilt die Boxen für die linke Seite, seine Laufwege sortieren wir absteigend, also beim ersten Weg läuft er am weitesten und bei den weiteren immer weniger weit. * Amir macht dasselbe auf der rechten Seite.

Es ist schwierig, Aussagen zu machen, wie gross das xx sein muss beim Kreis, den Amir macht, bei einem festen xx können wir jedoch sagen, welche Boxen er nimmt. Intuitiv ist es am besten, wenn Amir die Boxen nimmt, die am weitesten weg sind (aber auf derselben Seite). Denn beachtet folgendes: wenn bei einem Laufweg eine Box genommen wird, die dd weg ist, dann kann stattdessen auch eine genommen werden, die weniger weg ist, denn wir haben gesagt, dass Amir nach dem Kreis einfach auf einer Seite hin und her geht (und dann später auf der anderen). Er geht also zwangsläufig an allen Boxen vorbei, die auf derselben Seite sind. Somit kann er auch dort eine Box verteilen, denn wenn er die Box weiter weg nicht verteilt, hat er tatsächlich die Kapazität, eine zusätzliche Box zu verteilen. Wir wissen nun also folgendes: * Amir nimmt auf jedem Weg diejenigen Boxen, welche am weitesten entfernt von seinem Ursprungsort sind und alle auf derselben Seite liegen.

Somit wissen wir auch, wie lange Amir für seinen Laufweg braucht: nämlich a[x]a[x] wobei der Vector (oder das Array) aa anzeigt, wie weit die xx-te Person von Amir weg ist. Wir wissen, dass Amir den folgenden kk Personen schon Boxen verteilt hat, also wird er als nächstes bis zu a[xk]a[x-k] gehen. Dies funktioniert natürlich nur, wenn wir die Personen zuerst geordnet und in der Mitte aufgeteilt haben und dies können wir am Anfang in nlognn \log{n} Zeit tun.

Wenn wir herausgefunden haben, wo der Kreis sein sollte, können wir in O(n/k)O(n/k) Zeit herausfinden, wie lange Amir für den Weg braucht. Unsere Laufzeit erlaubt uns also, die kk Möglichkeiten für den Kreis auszuprobieren (und auch die Möglichkeit ohne Kreis) was zu einer Gesamtlaufzeit von O(nlogn+n/kk)O(n\log n + n/k\cdot k), also O(nlogn)O(n\log n) führt.

Häufige Strategien

Auch wenn Ad-hoc Aufgaben grundsätzlich daraus bestehen, eigene, kreative Lösungsansätze zu finden, gibt es Tricks, die häufig verwendet werden. Dies sind noch lange nicht alle, aber es hilft, wenn man sich mit einigen auseinandersetzt.

Was passiert mit dem grössten (oder kleinsten) Element?

Bei einigen Aufgaben verhält sich das grösste oder kleinste Element speziell. Bei der Aufgabe “molecules” war der Haupttrick, die grösste und kleinste Summe anzusehen. Viele Aufgaben verhalten sich da ähnlich. Noch ein Tipp: meist ist es sinnvoll, den Input zu sortieren. Dies haben wir hier bei beiden Aufgaben gebraucht. Wenn der Input eine zufällige Reihenfolge hat, kann man nichts über ihn aussagen, ist er hingegen sortiert, sind viele Operationen leichter zu bewältigen. Ausserdem ist es kein grosser Aufwand (verwende std::sort, falls du es noch nicht kennst, dies erleichtert die Sache.)

Kann man Dinge systematisch vertauschen, sodass die Lösung besser wird (oder zumindest gleich gut bleibt)?

Meist gibt es nicht nur eine optimale Lösung, sondern mehrere. Dies ist bei beiden vorgestellten Aufgaben der Fall. Es kann jedoch sein, dass gewisse optimale Lösungen Strukturen aufweisen, und somit einfacher zu coden sind. Ein Beispiel dafür: wir haben bei dem Task Boxes immer die kk Personen genommen, die am weitesten weg sind. Dies ist für die Lösung nicht zwingend, aber führt trotzdem zu einer optimalen Lösung. Anders kann es aber auch sein, dass man mit einer Lösung anfängt, die nicht optimal ist, und sie dann durch das Vertauschen von Elementen optimal macht.

Gibt es Dinge, die sich nie ändern?

Es kann zum Beispiel sein, dass bei einer Graphentheorie Aufgabe ein Graph erstellt wird, in dem immer mehr Knoten hinzugefügt werden. Vielleicht ist es ja der Fall, dass es immer ein Baum bleibt. In diesem Fall kann man für den Code die Eigenschaften von Bäumen ausnützen.

Hat die Lösung bestimmte Eigenschaften?

Dies ist eine sehr offene Frage. Als Beispiel nehmen wir wieder die Aufgabe Boxes: dort haben wir herausgefunden, dass eine optimale Lösung immer nur einen Kreis hat. Meistens findet man die Eigenschaften durch Vertauschungen heraus, denn man kann so ziemlich gut die Struktur der Aufgabe (und der Lösung) analysieren.

Allgemeine Bemerkungen

Ad-hoc Aufgaben kommen an der IOI häufig vor, und es ist daher sinnvoll, sich mit ihnen auseinander zu setzen. Anders als bei anderen Themen, kann man nicht einfach einen Algorithmus auswendig lernen, sondern muss kreative Lösungsansätze haben. Aber dies lässt sich auch trainieren. Eigene Lösungsansätze braucht man nicht nur bei den Ad-hoc Aufgaben, sondern sind zum Beispiel auch bei Greedy-Aufgaben wichtig.

Vergesst nicht:

Es macht Sinn, eine Aufgabe auf Papier zu analysieren bevor man sich ans Coden macht. So können viele Sachen vereinfacht werden.

Am Anfang mag dies schwierig sein, aber ich kann garantieren: es erleichtert euer Coding-Leben.