Gibt es eine schnellere Lösung für das Google Code Jam Great Wall-Problem?

Betrachten Sie die folgende Frage zu Google Code Jam in Runde 1C :

Die Chinesische Mauer beginnt als unendliche Linie, wobei die Höhe an allen Stellen .$0$

Einige Anzahl von Stämmen , N ≤ 1000 , wird die Wand der Wand angreifen gemäß den folgenden Parametern - Anfangstag, D , eine Start Stärke S , einen Start west-Koordinate, W , und ein Start-Ost-Koordinate, E . Dieser erste Angriff erfolgt am Tag D , auf Bereich [ W , E ] , an Stärke S . Befindet sich ein Teil der Chinesischen Mauer in [ W , E ] , dessen Höhe < S ist $N$$N \le 1000$$D$$S$$W$$E$$D$$[W,E]$$S$$[W,E]$$< S$Wenn der Angriff erfolgreich ist, wird die Mauer am Ende des Tages so aufgebaut, dass sich jedes Segment innerhalb von der Höhe < S auf der Höhe S befindet (oder größer, wenn ein anderer Angriff erfolgt) dieser Tag traf auf dasselbe Segment mit der Stärke S ′ > S )$[W,E]$$< S$$S$$S' > S$

Jeder Stamm wird bis zu Angriffe ausführen, bevor er sich zurückzieht, und jeder Angriff wird iterativ von dem vor ihm bestimmten bestimmt. Jeder Stamm hat einige δ D , δ X und δ S , die die Reihenfolge ihrer Angriffe bestimmen: Die warten δ D ≥ 1 Tage zwischen den Angriffen, sie bewegen ihre Angriffsreichweite δ X Einheiten für jeden Angriff (negativ = Westen, positiv = east), obwohl die Größe der Reichweite gleich bleibt und ihre Stärke nach jedem Angriff um einen konstanten Wert zunimmt / abnimmt.$1000$$\delta_D$$\delta_X$$\delta_S$$\delta_D \ge 1$$\delta_X$

Ziel des Problems ist es, anhand einer vollständigen Beschreibung der angreifenden Stämme zu bestimmen, wie viele ihrer Angriffe erfolgreich sein werden.

Ich habe es geschafft, eine funktionierende Lösung zu codieren, die in etwa 20 Sekunden ausgeführt wurde: Ich glaube, die von mir implementierte Lösung benötigt Zeit, wobei A = die Gesamtzahl der Angriffe in einer Simulation ist (max 1000000 ) und X = die Gesamtzahl der eindeutigen Kantenpunkte in Angriffsbereichen (max 2000000 ).$O(A\log A + (A+X)\log X)$$A =$$1000000$$X =$$2000000$

Auf hohem Niveau meine Lösung:

• Liest alle Stammesinformationen ein
• Berechnet alle eindeutigen Koordinaten für Angriffsbereiche - O ( A $X$$O(A)$
• Stellt die Wand als verzögert aktualisierten Binärbaum über den Bereichen dar, der die Mindesthöhenwerte verfolgt. Ein Blatt ist die Spanne von zwei X- Koordinaten, zwischen denen sich nichts befindet, und alle übergeordneten Knoten stellen das fortlaufende Intervall dar, das von ihren untergeordneten Knoten abgedeckt wird. - O ( X log X $X$$X$$O(X \log X)$
• Erzeugt alle Angriffe, die jeder Stamm ausführen wird, und sortiert sie nach Tag - $O(A \log A)$
• Überprüfen Sie für jeden Angriff, ob er erfolgreich sein würde ( query time). Wenn sich der Tag ändert, durchlaufen Sie alle nicht verarbeiteten erfolgreichen Angriffe und aktualisieren Sie die Wand entsprechend ( Aktualisierungszeit von Protokoll X für jeden Angriff). - O ( A log X $\log X$$\log X$$O(A\log X)$

Meine Frage lautet: Gibt es eine Möglichkeit, es besser zu machen als ? Gibt es vielleicht eine strategische Möglichkeit, die Linearität der aufeinanderfolgenden Angriffe der Stämme auszunutzen? 20 Sekunden sind zu lang für eine beabsichtigte Lösung (obwohl möglicherweise Java daran schuld ist).$O(A\log A + (A+X)\log X)$

Das offensichtliche Verbesserungspotential ist dieser Schritt:

Erzeugt alle Angriffe, die jeder Stamm ausführen wird, und sortiert sie nach Tag - O ( A log A $O(A\log A)$

Wir wissen, dass die Stämme von einem bestimmten Tag an in regelmäßigen Abständen angreifen werden. Das heißt, wir sollten im Wesentlichen viele vorsortierte Listen zusammenführen. Die Problemstellung sagt uns auch, dass es niemals mehr als 1.000 Stämme geben wird (dh 1.000 Listen, die zusammengeführt werden müssen). eine winzige Zahl im Vergleich zu den 1.000.000 maximalen Angriffen! Abhängig von den relativen Timings Ihrer Implementierung kann sich die Verarbeitungszeit durch Umschalten halbieren.

Das ist wirklich alles, was ich zur Optimierung der theoretischen Komplexität vorschlagen kann, aber ich habe keinen Beweis, dass es nach dieser Änderung optimal wäre.

Ich habe das Puzzle selbst ausprobiert, aber ich habe eine sehr langweilige Darstellung der Wand verwendet: einen binären Suchbaum ( std::mapgenauer gesagt C ++ ), in dem Orte gespeichert sind, an denen sich die Höhe der Wand ändert. Auf diese Weise konnte ich Knoten nach Bedarf hinzufügen und entfernen (dh wenn ein komplizierter Abschnitt einem großen, überwältigenden Angriff ausgesetzt war oder mehrere Angriffe derselben Stärke betroffen waren, verringerte sich die Anzahl der Knoten erheblich). Dies löste die große Eingabe in 3,9 Sekunden (auf meinem mittelgroßen Entwicklungs-Laptop). Ich vermute, dass es mehrere Gründe für die Verbesserung gibt:

• Wie Sie bereits betont haben, kann das Ein- und Auspacken teuer werden, aber die vorlagenbasierten Container von C ++ verhindern dies gänzlich.
• Obwohl die von mir verwendete Wanddarstellung theoretisch schlechter ist, war es in den allermeisten Fällen superschnell, die Anzahl der Knoten dynamisch zu reduzieren (die meisten Testfälle waren bei weniger als 1k Knoten maximal, und alle außer 2 waren unter 10k). . Tatsächlich war der einzige Fall, der eine signifikante Zeit in Anspruch nahm, # 7, bei dem anscheinend viele sich nicht überschneidende Bereiche getestet wurden.
• Ich habe keine Vorverarbeitung verwendet (Stufen werden bestimmt, indem verfolgt wird, wann jeder Stamm das nächste Mal angreift und in jeder Runde nach dem niedrigsten Gelenk gesucht wird). Auch dies ist theoretisch noch schlimmer, aber in den meisten Fällen bedeutet der geringere Overhead, dass dies schneller war (ich werde dies testen und auf Sie zurückkommen). Update : Ich habe eine Prioritätswarteschlange für Angriffe hinzugefügt, ähnlich der oben beschriebenen Methode (obwohl ich das große Array nicht direkt erstellt habe) und die Zeit für die große Eingabe auf 3,0 Sekunden gesunken ist.

Kurz gesagt, obwohl ich denke, dass Ihr Algorithmus im Allgemeinen nahezu optimal ist, gibt es verschiedene Möglichkeiten, ihn für typische Eingaben zu beschleunigen .

Folgendes wurde aus der Frage entfernt, da es sich um eine Antwort handelt.

Ein Blick auf andere Diskussionen und erfolgreiche Lösungen scheint darauf hinzudeuten, dass die von mir beschriebene Lösung in etwa dem erwarteten Algorithmus entspricht. Die Verlangsamung meiner Lösung ist möglicherweise nur auf die langsame Verwendung von Auto-Boxing und einer zeigerbasierten Baumstruktur zurückzuführen, nicht auf eine arraybasierte. Ich vermute also, dass es wahrscheinlich keine vollständige Lösung gibt, wenn es eine gibt viel besser als was hier ist.

Die Lösung finden Sie hier . Es ist sehr ähnlich zu dem, was ich hier gepostet habe. Ich bin daher eher der Ansicht, dass es keine effizientere Lösung gibt.