Ergebnisse des Russian Code Cup 2015 und Analyse der Endrunde



    Am Samstag, den 19. September, fand die Endrunde des RCC 2015 statt. Peter Mitrichev, der bereits zweimal den RCC Cup gewonnen hat: 2011 und 2013, wurde der Gewinner und Gewinner des Hauptpreises von 300.000 Rubel. Der zweite Platz und ein Preis von 150.000 Rubel gingen an den Gewinner des letztjährigen RCC - Gennady Korotkevich. Der dritte Platz sowie das letzte Jahr wurde von Jegor Kulikov belegt. Sein Preis belief sich auf 90.000 Rubel. Außerdem erhielten Teilnehmer, die 4 bis 10 Plätze belegten, Preise in Höhe von 30.000 Rubel - Pavel Marin, Vladislav Epifanov, Sergej Kopeliovich, Juri Pisarchik, Konstantin Semenov, Michail Tichomirow und Nikolai Kalinin.

    Helden der Runde:

    • Der erste in 6 Minuten und 8 Sekunden, der das Problem A (Bandbiegen) Gennady Korotkevich (Tourist) löste, war der erste, der Aufgabe D (Der rechte Garten) in 45 Minuten und 29 Sekunden erledigte.
    • Der japanische Finalist Kawai Ryuta (anta) löste das Problem B (Münzen sammeln) vor allen anderen - in 16 Minuten und 20 Sekunden.
    • Petr Mitrichev (Petr) war der erste, der das Problem C (Topologische Sortierung und Kinder) in 45 Minuten und 29 Sekunden löste.
    • Problem F (Roboter am Baum) konnte von keinem der Finalisten gelöst werden.

    Wie gesagt , dieses Jahr fand das Finale in einem für die IT-Meisterschaft einzigartigen Format statt: Es wurde von einer vierstündigen Online-Show begleitet, die auf unserer Website ausgestrahlt wurde. Die Veranstaltung wurde live von dem bekannten russischen Schausteller Anton Komolov (Absolvent der Staatlichen Technischen Universität Bauman Moskau) und Mikhail Mirzayanov, Leiter des Zentrums für Olympiadenprogrammierungstraining der Staatlichen Universität Saratow, übertragen. Die Gäste des Studios waren Nikolai Nikiforov, Minister für Telekommunikation und Massenkommunikation der Russischen Föderation, Vertreter führender IT-Unternehmen und wichtige Branchenexperten. Die Broadcast-Aufzeichnung kann unter https://it.mail.ru/rcc/ eingesehen werden  .

    Kommen wir nun zur Analyse der Aufgaben.

    Problem A. Biegen des Bandes


    Idee:  Vladimir Smykalov
    Implementierung:  Dmitry Filippov
    Analyse:  Dmitry Filippov

    Die Aufgabe erhält einen 1 × 2 n- Streifen , der zuerst  n  genau in zwei Hälften gefaltet und dann zurückgedreht wurde. Das Falten ist auf zwei Arten möglich: die linke Hälfte rechts oder die rechte Hälfte links. Es ist erforderlich, Fragen zu beantworten: anhand der Nummer der Biegung, um herauszufinden, ob sie nach oben oder unten ausgerichtet ist.

    Erfahren zum Reagieren auf eine Anforderung für O (log 2 n ), das heißt von O ( n ). Die Gesamtzahl der Anfragen überschreitet 10 5 nichtdeshalb ist es völlig ausreichend. Wir werden den Biegeprozess für jede Anfrage emulieren. Wenn Sie die aktuelle Bandlänge und die Biegezahl kennen, ist es leicht zu verstehen, in welcher Hälfte sich diese Zahl befindet. Wenn Sie wissen, auf welcher Seite die Biegung in zwei Hälften erfolgt, finden Sie auch die neue Biegeposition im doppelt geschnittenen Band. Um die Anfrage zu beantworten, unterstützen wir gleichzeitig die Position, in welche Richtung die Falte jetzt ausgerichtet ist. Insgesamt erhalten wir die Lösung in O ( qn ), wobei  q  die Gesamtzahl der Abfragen ist.

    Aufgabe B. Münzen sammeln


    Idee:  Vitaly Aksenov
    Implementierung:  Boris Minaev
    Analyse:  Boris Minaev

    Die Aufgabe erhält ein in Zellen zerbrochenes Band, auf dem der Spieler läuft. Jede Sekunde in jeder Zelle erscheint eine zusätzliche Anzahl von Münzen, die für jede Zelle festgelegt sind. Der Spieler kann in einer Sekunde zur nächsten Zelle wechseln oder in der aktuellen bleiben. Jedes Mal, wenn sich ein Spieler in einer bestimmten Zelle befindet, sammelt er alle darin enthaltenen Münzen. Es muss berechnet werden, wie viele Münzen ein Spieler maximal in t  Sekunden sammeln kann  .

    Beachten Sie, dass es für jede Zelle wichtig ist, nur den letzten Moment zu kennen, in dem sich der Spieler darin befand. Betrachten Sie den Weg des Spielers vom Ende. Zu jedem Zeitpunkt ist der letzte Moment ihres Besuchs bereits über ein kontinuierliches Segment von Zellen bekannt, jedoch nicht für den Rest der Zellen. Daher können Sie die dynamische Programmiermethode verwenden, deren Status das Segment der besuchten Zellen und die aktuelle Zeit ist. Außerdem müssen Sie die aktuelle Position des Players speichern. Beachten Sie, dass Sie diese Positionen nur speichern können, wenn der Spieler an einem Ende des Segments der besuchten Zellen steht. Von jedem Zustand gibt es nicht mehr als zwei Übergänge: Ein Spieler kann eine Zelle links oder rechts von den bereits besuchten besuchen. Somit beträgt die Laufzeit des Algorithmus O ( n 2 t ).
     

    Problem C. Topologische Sortierung und Kinder 


    Idee:  Artyom Vasiliev
    Implementierung:  Vitaly Aksyonov
    Analyse:  Vitaly Aksyonov.

    Das Problem erhält ein Diagramm und seine topologische Sortierung, von denen einige Elemente gelöscht wurden. Die topologische Sortierung muss korrekt wiederhergestellt werden.

    Wir betrachten zuerst den Algorithmus und beweisen dann seine Richtigkeit. Die Eckpunkte, für die die Reihenfolge angegeben ist, werden als beschriftet, der Rest als unbeschriftet bezeichnet. Wir wissen, welche Zahlen bei der topologischen Sortierung nicht verwendet wurden, und werden sie einzeln vom größten bis zum kleinsten Scheitelpunkt verfügbar machen. Wir haben eine andere unverzerrte Nummer. Der erste Schritt besteht darin, alle bereits markierten Abflüsse zu löschen. Als nächstes ermitteln wir für jeden unbeschrifteten Abfluss den Maximalwert am markierten Scheitelpunkt, der von den inversen Kanten aus erreichbar ist. Für jeden Scheitelpunkt kann diese Zahl im Voraus berechnet werden: Wir finden eine topologische Sortierung des Graphen und lösen das Problem der dynamischen Programmierung. Als entsprechenden Scheitelpunkt für die unverzerrte Zahl wählen wir eine Senke mit der größten berechneten Zahl aus und entfernen sie aus dem Diagramm.

    Die Vorberechnung der Zahlen erfolgt in O ( V + E ). Jede Iteration sollte so schnell wie möglich durchgeführt werden. Daher speichern wir an jedem Scheitelpunkt die Anzahl der von ihm verbleibenden ausgehenden Kanten. Wenn wir die Senke entfernen, alle Scheitelpunkte, von denen sich eine Kante darin befindet, nimmt der ausgehende Grad ab, und wenn dieser Grad Null wird, platzieren wir diesen Scheitelpunkt in der Menge auf den berechneten Wert. Somit werden alle Bestände in unserem Set gespeichert, und um den erforderlichen auszuwählen, reicht es aus, den allerletzten Peak aus dem Set zu entnehmen. Jeder Scheitelpunkt wird in das Set eingefügt und genau einmal herausgezogen. Gesamtlaufzeit des Algorithmus: O ( V · log ( V ) +  E ).

    Jetzt beweisen wir die Richtigkeit unseres Algorithmus. Beachten Sie, dass es für uns ausreicht, die Richtigkeit des ersten Schritts des Algorithmus zu beweisen. Dann verwenden wir die Methode der mathematischen Induktion. Betrachten Sie eine korrekt ausgefüllte topologische Sortierung  p , bei der zuvor alle markierten Senken weggeworfen wurden. Als nächstes betrachten wir die Senke  s , die wir für unseren Algorithmus für die maximale Anzahl ausgewählt haben, und die Senke, der sie in der topologischen Sortierung  p entspricht . Wenn wir alle Zahlen in der Permutation reduzieren, werden große  p (s) um eins und  s Geben Sie die maximale Anzahl an, die Permutation bleibt korrekt. Die Operation wurde korrekt ausgeführt: Wir haben die topologische Sortiereigenschaft für unbeschriftete Scheitelpunkte beibehalten, und für beschriftete Scheitelpunkte hat sich der Wert der topologischen Sortierung nicht geändert, da die Scheitelpunktauswahl-Eigenschaft  sp (s) größer ist als der topologische Sortierwert eines beschrifteten Scheitelpunkts.

    Aufgabe D. Der richtige Garten 


    Idee:  Artyom Vasilyev
    Implementierung:  Artyom Vasilyev
    Analyse:  Artyom Vasilyev

    In diesem Problem wird eine Reihe von Punkten in der Ebene angegeben und das Konzept einer guten  Menge von Punkten eingeführt  . Eine gute  Menge von Punkten ist eine Menge von Punkten, so dass jedes nicht entartete Rechteck mit Seiten parallel zu den Koordinatenachsen und mit entgegengesetzten Winkeln an bestimmten Punkten mindestens einen weiteren Punkt aus dieser Menge innerhalb oder am Rand enthält. Es muss überprüft werden, ob ein bestimmter Satz von Punkten diese Eigenschaft hat.

    Zunächst beweisen wir eine äquivalente Eigenschaft: Eine Menge von Punkten ist genau dann gut, wenn für jede Ecke eines solchen Rechtecks ​​ein Punkt auf der Seite neben diesem Winkel vorhanden ist. Wenn diese Eigenschaft erfüllt ist, ist natürlich auch die im Zustand der Aufgabe beschriebene Eigenschaft erfüllt. Jedoch wahr und folglich in der entgegengesetzten Richtung: ein beliebiges Rechteck mit Ecken an den Punkten Betrachten  A  und  B . Durch die Annahme, innerhalb oder auf der Grenze des Rechtecks es ein anderer Punkt aus dem Satz ist, wird sie genannt  C . Wenn dieser Punkt bereits auf der Seite neben  A liegt , ist unsere Aussage wahr. Andernfalls betrachten Sie ein Rechteck, das auf den Punkten  A aufgebaut ist und C. Seine Fläche ist , die streng kleiner ist als das Quellrechteck und der Satz von Punkten in einer endlichen Zahl, dann , wenn wir an einen Punkt liegt auf der Seite benachbart wählen  , A .

    Die formulierte Eigenschaft hilft, eine Lösung zu erreichen: Für einen Punkt ( x i , y i ) sei  links i  das Maximum  x <x i, so dass es in der gegebenen Menge einen Punkt ( x, y i ) gibt. Wenn dieser Wert nicht definiert ist, betrachten wir ihn als minus unendlich. Auf die gleiche Weise führen wir die Werte  richtig irunter i  und  rauf i ein . Betrachten Sie die Region (links irechts i ) × ( unten i , oben i ). Wenn sich in diesem Bereich ein anderer Punkt aus der angegebenen Menge befindet, können Sie zwei Punkte finden, für die das konstruierte Rechteck die Eigenschaft verletzt. Es ist erwähnenswert, dass nicht jeder Punkt in diesem Bereich geeignet ist. Der zweite Punkt ist immer geeignet, zum Beispiel der nächstgelegene in euklidischer oder Manhattan-Entfernung. Wenn sich in diesem Bereich nur ein Punkt ( x i , y i ) befindet , enthalten alle Rechtecke einen weiteren Punkt auf der angrenzenden Seite. Daher bestand die Lösung darin, n  Rechtecke auf das Vorhandensein von mehr als einem Punkt im Inneren zu überprüfen  .

    Sie können eine solche Prüfung mithilfe einer beliebigen Datenstruktur implementieren, mit der Sie die Anzahl der Punkte in einem Rechteck in der Ebene zählen können: einen zweidimensionalen Segmentbaum (Online-Lösung) oder eine Offline-Lösung mit einer Scan-Geraden und einem eindimensionalen Segmentbaum. Eine solche Lösung kann in O ( n  log ( n )) implementiert werden .

    Aufgabe E. Interfluve

     
    Idee:  Vitaliy Aksyonov
    Implementierung:  Ilya Zban
    Analyse:  Ilya Zban

    In dem Problem werden  n  disjunkte monotone gestrichelte Linien und ein konvexes Polygon angegeben. Sie müssen herausfinden, wie oft Sie mindestens ein Polygon anhängen müssen, damit jede Polylinie mindestens einen gemeinsamen Punkt mit einem der angewendeten Polygone hat (am Rand oder innerhalb des Polygons).

    Da das Polygon konvex ist und die unterbrochenen Linien monoton sind und sich nicht schneiden, gilt die folgende Tatsache: Wenn das Polygon die unterbrochenen Linien  i, k schneidet, schneidet dieses Polygon für jedes  j, so dass  i ≤ j ≤ k ist , auch  jgestrichelte Linie. Mit dieser Tatsache werden wir das Problem der gierigen lösen: das Maximum finden  i 1 , so dass es ein Polygon, das alle mit dem 1. bis gebrochen Kreuze  i 1 th, fügen Sie es in der Antwort, und wird auch weiterhin: das Maximum finden  i 2  so , dass es existiert ein Polygon , die unterbrochene Linien von i 1 + 1 bis i 2 abdecken  und so weiter. Die Anzahl der Polygone, die verwendet werden mussten, ist die Antwort.

    Wir lernen für die gestrichelte Linie  i k,  den Wert  i k + 1 zu finden . Dies ist der maximale Index, so dass ein Polygon existiert, das i k + 1 und  i abdeckt k + 1. Polylinie. Zunächst werden wir ein einfacheres Problem lösen: Es gibt einen Punkt A und ein Segment BC. Wir müssen prüfen, ob ein Polygon vorhanden ist, das sowohl diesen Punkt als auch einige Punkte des Segments enthält. Dazu konstruieren wir die Minkowski-Summe dieses Polygons und es selbst, invertiert in Bezug auf (0, 0) (dh mit den Koordinaten aller im Vorzeichen entgegengesetzten Punkte). Dies ist ein neues Polygon, nennen wir es P mit O ( n ) Eckpunkten, die einen Punkt (0, 0) enthalten. Wir verschieben es so, dass der Punkt (0, 0) zum Punkt A übergeht, und überprüfen, ob das Segment BC das verschobene Polygon P schneidet. Es ist leicht zu überprüfen, ob dies eine notwendige und ausreichende Bedingung ist.

    Wenn Sie lernen, zu überprüfen, ob ein Polygon vorhanden ist, das einen Punkt und ein Segment schneidet, ist es nicht schwierig, dasselbe für zwei Polygone zu überprüfen: Iterieren Sie über ein Segment auf einer Polygonlinie, konstruieren Sie die Minkowski-Summe mit Polygon P und prüfen Sie, ob sich ein neues konvexes Polygon mit einem Segment der zweiten Polygonlinie schneidet .

    Sei  k  die Gesamtzahl der Eckpunkte auf allen unterbrochenen Linien. Wir finden das asymptotische Verhalten der Operationen, die wir verwenden - O ( n ), um das Polygon P zu konstruieren, O ( n ), um die Minkowski-Summe P und das Segment der polygonalen Linie zu konstruieren, und O (log  n ), um den Schnittpunkt des konvexen Polygons und des Segments zu überprüfen. Da die Polygone maximal  k bilden müssenund im schlimmsten Fall muss jedes Polygon mit jedem Segment geschnitten werden, das resultierende asymptotische Verhalten der Betriebszeit ist O ( nk + k 2 log  n ).

    Problem F. Roboter auf einem Baum 


    Idee:  Boris Minaev
    Implementierung:  Boris Minaev.
    Analyse:  Boris Minaev.

    Ein unorientierter Baum mit n  ≤ 10 Eckpunkten ist im Problem angegeben  . Jede Rippe ist bekannt für ihre Stärke  wi , die 15 nicht überschreitet. Ein Roboter bewegt sich um den Baum, der sich anfangs an einem zufälligen Scheitelpunkt befindet. Jedes Mal wählt der Roboter gleich wahrscheinlich eine Kante aus denen aus, an denen er vorbeikommen kann, und bewegt sich entlang dieser. Jedes Mal, wenn ein Roboter eine Kante passiert, nimmt seine Stärke um eins ab. Wenn die Stärke Null wird, wird die Rippe entfernt. Wenn der Roboter keine Rippen hat, denen er folgen kann, stoppt er. Es ist notwendig, die mathematische Erwartung der Weglänge des Roboters zu berechnen.

    Zunächst werden wir ein einfacheres Problem lösen. Angenommen, es ist notwendig, nicht die mathematische Erwartung der Pfadlänge zu berechnen, sondern die Anzahl der verschiedenen Pfade, auf denen der Roboter fahren könnte. Stellen Sie sich vor, wir haben die Spitzen aufgezeichnet, an denen der Roboter seinen Weg begonnen und beendet hat, sowie die Häufigkeit, mit der der Roboter jede Kante durchlaufen hat. Beachten Sie die Einschränkungen für diese Mengen. Erstens müssen die Kanten, an denen der Roboter eine positive Anzahl von Malen passiert hat, einen verbundenen Teilgraphen des Quellbaums bilden. Zweitens betrachten wir einen bestimmten Scheitelpunkt und die Häufigkeit, mit der der Roboter alle Kanten durchlaufen hat, die an diesen Scheitelpunkt angrenzen. Wenn dieser Scheitelpunkt das Ende des Pfades ist, muss jede angrenzende Kante genau  mit verwendet werden mal. Maximal zwei Kanten neben dem Scheitelpunkt müssen ungerade oft verwendet werden. Wenn dieser Scheitelpunkt vom Anfang bis zum Ende auf dem Pfad liegt, müssen außerdem genau zwei Kanten ungerade oft verwendet werden. Für die Start- und Endscheitelpunkte (wenn sie nicht zusammenfallen) muss genau eine Kante vorhanden sein, die ungerade oft verwendet wird, oder Null, wenn die Scheitelpunkte zusammenfallen. Für alle anderen Eckpunkte müssen alle benachbarten Kanten gerade verwendet werden.

    Wenn alle diese Bedingungen erfüllt sind, lernen wir, wie Sie die Anzahl der Pfade zählen, die die Bedingung des Problems erfüllen, und Kanten eine feste Anzahl von Malen verwenden. Für jeden Scheitelpunkt betrachten wir alle angrenzenden Kanten. Wir wissen, wie oft der Roboter jeden von ihnen durchlaufen hat. Wir können leicht berechnen, wie oft der Roboter entlang der Kante in Richtung vom angegebenen Scheitelpunkt gefahren ist. In welcher Reihenfolge könnte der Roboter entlang dieser Rippen laufen? Erstens sollte der Roboter entlang der Kante, die auf dem Weg nach oben liegt, wo der Roboter die Reise beendet hat, als letzter fahren. Auf allen anderen Rippen kann er in beliebiger Reihenfolge gehen. Das Zählen der Anzahl solcher Methoden ist eine Standardaufgabe. Um die Gesamtzahl der Pfade zu berechnen, die ein Roboter gehen kann, müssen die berechneten Werte für jeden Scheitelpunkt multipliziert werden.

    Beachten Sie, dass Sie die dynamische Programmiermethode verwenden können, um die Gesamtzahl der Pfade zu berechnen. Wir berechnen die Anzahl der Pfade, die eine bestimmte Anzahl von Malen entlang einer bestimmten Kante verlaufen, und in irgendeiner Weise entlang eines Teilbaums, der durch diese Kante begrenzt ist. Darüber hinaus wird angenommen, dass er jedes Mal, wenn der Pfad den Rand hinaufführt, sofort zurückkehrt. Um den Wert der dynamischen Programmierung zu berechnen, muss festgelegt werden, wie oft der Roboter an jeder Kante in Teilbäume gelaufen ist, multipliziert mit den bereits berechneten Werten für Teilbäume sowie der Anzahl der Möglichkeiten, Übergänge in Teilbäumen anzuordnen. Wir werden der Reihe nach die Teilbäume des Scheitelpunkts betrachten und festlegen, wie oft der Roboter insgesamt zu allen betrachteten Teilbäumen geht. In Anbetracht des nächsten Teilbaums sortieren wir, wie oft der Roboter in diesen Teilbaum gelangt. Wir multiplizieren die Antwort auf den Wert der dynamischen Programmierung aus einem Teilbaum sowie die Anzahl der Möglichkeiten, Übergänge in einen Teilbaum unter anderen Übergängen anzuordnen.

    Kehren wir zur ursprünglichen Aufgabe zurück. Anstelle der Anzahl der Methoden speichern wir nun die Wahrscheinlichkeit, einen solchen Pfad zu wählen, sowie die mathematische Erwartung seiner Länge. Die Berechnung der Wahrscheinlichkeit unterscheidet sich von der Berechnung der Anzahl der Methoden nur darin, dass bei jedem Übergang entlang der Kante der Wert durch die Anzahl der Kanten geteilt werden muss, die auf diesen Scheitelpunkt fallen. Das einzige Problem, das dabei auftritt, ist, dass der Grad des Scheitelpunkts nicht konstant ist, da die Kanten während der Fahrt des Roboters entfernt werden. Um die dynamischen Programmierwerte für eine Kante zu berechnen, verwenden wir die folgende Idee. Wir korrigieren alle Teilbäume, deren Kanten entfernt werden, sowie die Gesamtzahl der Male, die der Roboter entlang einer Kante von oben fährt. Wir werden den Pfad vom Ende wiederherstellen. Es gibt zwei mögliche Optionen: was unterschieden werden muss. Oder der Roboter fährt entlang einer Kante, die nicht entfernt wird. Dann müssen Sie die Anzahl der Kanten reduzieren, entlang derer der Roboter noch eine kleinere Aufgabe ausführen muss. Oder der Roboter bewegt sich entlang der Kante, die entfernt werden soll. Um die Gesamtzahl der Kanten zu bestimmen, entlang derer der Roboter fahren muss, müssen Sie die Häufigkeit hinzufügen, mit der er sich entlang dieser Kante bewegt, und die Anzahl der vorhandenen einfallenden Kanten um eins erhöhen.

    Insgesamt gibt es in der dynamischen Programmierung für eine gegebene Kante O (2 Kinderwi ) Zustände, und der Übergang zwischen ihnen wird in O (1) ausgeführt. Da es notwendig ist, den Wert der dynamischen Programmierung für jede Anzahl von Malen zu berechnen, in denen eine Kante verwendet wurde, stellt sich heraus, dass die Gesamtlaufzeit des Algorithmus O (2 n (∑ wi ) 2 ) ist.

    Jetzt auch beliebt: