Ad-hoc Strategies

IOI 2016 Molecules

Ein gutes Beispiel einer Ad-hoc Aufgabe ist von der IOI 2016 “molecules”: Gegeben sind die Gewichte von $n$ 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,3$ und einen Detektor, der die Erkennungsbreite $7$ bis $9$ hat. Hier ist es nicht schwer, herauszufinden, dass es nicht möglich ist, ein Subset zusammenzustellen, welches die Summe $7,8$ oder $9$ hat, da die maximale Summe $6$ 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 $k$ 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 $k$ Elemente existiert (wobei $1 \leq k\leq n$). Dies hilft einem für folgendes: wenn die minimale und maximale Summe für $k$ Elemente je kleiner (oder grösser) als der Bereich ist, gibt es sicherlich keine Lösung mit $k$ Elementen (denn jede Summe liegt zwischen dem kleinsten und grössten Element). Existiert aber ein $k$, 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 $n$ Personen, verteilt auf einem Kreis. Amir will nun jeder Person eine Box verteilen. Er kann maximal $k$ Boxen gleichzeitig tragen und will möglichst schnell fertig sein. (Zeit braucht nur das Laufen). Er endet und startet am Punkt $0$. Das Programm soll nun bestimmen, wie lange Amir mindestens braucht. Als Input ist die Anzahl Personen $n$, die Anzahl Boxen, die Amir gleichzeitig tragen kann $k$, die Grösse des Kreises $m$ und für jede Person einen Index $a_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 $k$ 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 $k$ 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 $0$, dann geht er zu $1, 2, \ldots$ bis $n$ und von dort geht er wieder zu $0$. 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 $k$ Boxen verteilt. Falls beim zweiten Rundgang weniger als $k$ 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 $0$ ein, bis es insgesamt $2k$ Punkte auf dem Kreis sind. * Auf einer Hälfte des Kreises hat es mindestens $k$ Punkte. Dabei zählt $0$ zu beiden Hälften (und falls $m=2l+1$, also ungerade, zählt auch $l+1$ zu beiden Hälften, da es auf beide Richtungen gleich weit vom Nullpunkt entfernt ist)

Wir könnten also folgendes machen: Amir verteilt $k$ 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 $x$ Boxen auf die linke Seite und $k-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 $x$ sein muss beim Kreis, den Amir macht, bei einem festen $x$ 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 $d$ 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]$ wobei der Vector (oder das Array) $a$ anzeigt, wie weit die $x$-te Person von Amir weg ist. Wir wissen, dass Amir den folgenden $k$ Personen schon Boxen verteilt hat, also wird er als nächstes bis zu $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 $n \log{n}$ Zeit tun.

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

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 $k$ 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.