Nun ist auch die letzte Paranuss ausgewertet, also schreiten wir zur Musterlösung:
Um dieses Problem effizient zu lösen, ist die entscheidende Idee, sich erst einmal ein anderes Problem zu stellen:
Angenommen, wir haben eine Zielfüllung x
, die wir in allen Schneekanonen erreichen wollen, bereits gegeben - wie können wir entscheiden, ob diese erreichbar ist? Den theoretischer Angehauchten unter euch dürfte diese Umformulierung bekannt vorkommen: Das ist das zu unserem
Optimierungsproblem gehörige Entscheidungsproblem. In der Komplexitätstheorie sieht man diese beiden als äquivalent an, denn sie lassen sich polynomiell ineinander überführen - haben wir einen Algorithmus für das zweite Problem gefunden, finden wir per binärer Suche schnell die maximale Zielfüllung
!
Wir sind also fein raus, wenn wir das zweite Problem effizient lösen können. Und das sieht nicht nur einfacher aus, es lässt sich tatsächlich greedy lösen:
Zuerst einmal eine selbsterklärende, aber wichtige Beobachtung: Wir müssen nur Transporte zwischen direkten Nachbarn berücksichtigen, denn jeder längere lässt sich als Folge solcher realisieren. Fangen wir bei der ersten Schneekanone an und vergleichen deren Füllung
y mit der Zielfüllung
x. Ist sie größer, sind wir beruhigt und können die Differenz direkt zum rechten Nachbarn tragen, ansonsten müssen wir die fehlende Menge von diesem klauen (nicht dadurch verwirren lassen, dass dessen Füllmenge dadurch temporär negativ werden könnte). In jedem Fall ist die Zielfüllung nun erreicht und wir können einen Schritt nach rechts gehen. Bei der nächsten Kanone finden wir nun aber die gleiche Situation vor - wir müssen die Differenz wieder nach rechts schieben oder von dort einfordern, denn alle Kanonen links von uns sind haben sowohl die Zielfüllmenge erreicht als auch nichts mehr nach rechts abzugeben. Also können wir die Strategie weiterfahren und sehen, dass die Probleminstanz genau dann lösbar ist, wenn wir in der letzten Kanone mindestens die Zielfüllmenge vorfinden.
Und genauso einfach sieht das auch im Code aus (oder einfacher, wenn ich mir den Textblock oben nochmal anschaue):
C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
| bool HasSolution(long x){
long delta = canons[0].Value - x;
for(int i = 1; i < n; i++){
long carry = delta - (canons[i].Pos - canons[i-1].Pos); if(delta >= 0 && carry < 0)
carry = 0;
delta = (canons[i].Value - x) + carry;
}
return delta >= 0;
} |
Zusammen mit der binären Suche kommt eine Komplexität von
θ(n * max(y)) heraus - womit jede Eingabe in den gegebenen Schranken quasi instantan lösbar ist.
Kha