Herausforderungen der Yandex.Algorithm 2017 Marathonrunde

    Und wieder steht, wie in den Vorjahren, das Finale des Yandex.Algorithm-Wettbewerbs vor der Tür. In diesem Jahr haben wir einen neuen Rundmarathon eingeführt. Es ist ein Optimierungsproblem ohne exakte Lösung, das die Teilnehmer innerhalb von 48 Stunden „verdrehen“ sollten. Dieses Format ähnelt eher der Lösung praktischer Probleme als das Programmieren von Wettbewerben für populäre Sportarten.




    Ein Merkmal der meisten praktischen Probleme ist das Fehlen einer genauen Lösung - oder die Algorithmen, um sie zu finden, sind zu langsam. Das Team und der einzelne Entwickler müssen einen guten Prototyp der Lösung erstellen, der im endgültigen Algorithmus implementiert wird. Aufgaben dieser Art wurden schon lange in TopCoder- Wettbewerben , den jährlichen Wettbewerben Marathon24 , Deadline24 , Google Hash Code und anderen angetroffen . Der Wettbewerb dauert länger als die üblichen algorithmischen Runden, so dass die Teilnehmer die erfundene Methode in einer entspannten Atmosphäre und zu einem günstigen Zeitpunkt anwenden können.


    Wir, die Organisatoren des Algorithmus, möchten wirklich, dass sich die verschiedenen Teilnehmer erfolgreich beweisen können. Aus diesem Grund denken wir darüber nach, die Marathonrunde hinzuzufügen, um das Publikum zu erweitern und solche Wettbewerbe bekannt zu machen.


    Wir haben die Teilnehmer, die das beste Ergebnis gezeigt haben, gebeten, zu erklären, wie sie es erreicht haben.


    Wir empfehlen, dass Sie versuchen, das Problem zu lösen ! Wer vor dem Finale des Algorithmus das beste Ergebnis zeigt, bekommt ein T-Shirt mit den Symbolen des Wettbewerbs. Das Finale findet am 18. Juli statt. Sowohl diejenigen, die die Runde im Rahmen des Algorithmus entschieden haben, als auch neue Teilnehmer sind zur Teilnahme eingeladen.


    Bedingung der Aufgabe "Teilung des Landes"


    Zustand anzeigen
    Zeitlimit:Speicherlimit:Eingabe:Fazit:
    2 s256 MBStandardeingabeStandardausgabe

    In einem Elfenland ist eine Spaltung gereift. Wie so oft konnten seine Söhne nach dem Tod des Königs lange Zeit nicht entscheiden, wer das Land regieren sollte, und als Ergebnis fiel ihnen nichts Besseres ein, als es in getrennte Gebiete aufzuteilen.


    Das elfische Land wird durch ein kariertes Rechteck aus n Zeilen und m Spalten dargestellt. In k Zellen gibt es Quellen des Lebens, eine andere in k Zellen sind Quellen der Magie, während sich alle Quellen in verschiedenen Zellen befinden. Glücklicherweise hatte der verstorbene König genau k Söhne, daher möchten sie das Land in k zusammenhängende Gebiete aufteilen, so dass jedes Gebiet genau eine Quelle des Lebens und genau eine Quelle der Magie enthält. Eine Region wird als kohäsiv bezeichnet, wenn es von einer ihrer Zellen aus möglich ist, in eine andere Zelle dieser Region zu gelangen, die nur an Zellen der Region vorbeiführt und eine gemeinsame Seite hat. Jede Zelle muss zu genau einem Bereich gehören. Die Bereiche können „Löcher“ enthalten, dh einer der Bereiche kann allseitig von dem anderen umgeben sein.


    Eingabeformat


    • Die erste Zeile enthält drei ganze Zahlen n, m und k (3 ≤ n, m ≤ 50, 3 ≤ k ≤ 16) - die Größe des Landes und die Anzahl der Quellen des Lebens und der Magie.
    • Die nächsten k Zeilen enthalten Paare von ganzen Zahlen rli, cli (0 ≤ rli ≤ n - 1, 0 ≤ cli ≤ m - 1) - die Koordinaten der Lebensquellen.
    • Die nächsten k Zeilen enthalten Paare von ganzen Zahlen rmi, cmi (0 ≤ rmi ≤ n - 1, 0 ≤ cmi ≤ m - 1) - die Koordinaten der Quellen der Magie.
    • Es wird garantiert, dass sich alle Quellen in verschiedenen Zellen befinden und dass für die angegebenen Eingabedaten mindestens eine Unterteilung in Regionen vorliegt, die die obigen Bedingungen erfüllen.

    Ausgabeformat


    Drucken Sie jeweils n Zeilen mit m lateinischen Buchstaben: Unterteilen Sie das Land in Regionen. Sites, die dieselben Buchstaben enthalten, werden demselben Bereich zugewiesen. Englische Klein- und Großbuchstaben sind als Zeichen zulässig. Insgesamt müssen k Buchstaben genau verwendet werden. Zellen mit den gleichen Buchstaben sollten einen zusammenhängenden Bereich bilden. Jeder Bereich muss genau eine Quelle des Lebens und genau eine Quelle der Magie enthalten.


    Bewertungssystem


    Die angegebene Aufschlüsselung wird nach folgendem System ausgewertet:


    • Wenn die Partition falsch ist (sie enthält inkohärente Bereiche oder die Bereiche enthalten die falsche Anzahl von Quellen oder das Ausgabeformat wird nicht befolgt), erhält Ihre Entscheidung für diesen Test 0 Punkte.
    • Ansonsten definieren wir für jede Region ihre "Ausbuchtung" als das Verhältnis der Fläche zum Quadrat des Umfangs der Region, wobei die Fläche die Anzahl der Zellen ist, die in die Region eintreten, und der Umfang die Anzahl der Seiten von Zellen, die an andere Regionen oder an die Grenze des Landes angrenzen (siehe Beispiel zur Erläuterung). ;
    • Die Gesamtpunktzahl für den Test ist die durchschnittliche Ausbeulung aller Bereiche, multipliziert mit 160.000 und auf die nächste ganze Zahl gerundet.

    Beim Versenden während des Wettbewerbs wird Ihre Entscheidung anhand von 50 Vorversuchen überprüft. Ihr vorläufiges Ergebnis entspricht der durchschnittlichen Punktzahl für alle Tests. Achten Sie auf den Link „Bericht“ neben der gesendeten Lösung: Hier können Sie sehen, bei welchen Tests Ihr Programm erfolgreich war und bei welchen es eine falsche Antwort gab oder überhaupt nicht. Sie können nicht sowohl die Eingabe- als auch die Ausgabedaten für einen bestimmten Test anzeigen.


    Nach dem Ende des Wettbewerbs wird Ihre zuletzt gesendete und kompilierte Lösung in einem vollständigen Satz von 250 Tests getestet (50 vorläufige Tests sind nicht im vollständigen Satz enthalten). Die durchschnittliche Punktzahl für alle Tests aus dem gesamten Satz ist Ihr Endergebnis.


    Test Generation


    • 40% der Tests in jedem Satz sind völlig zufällig: n, m, k werden mit gleicher Wahrscheinlichkeit ausgewählt, wonach die entsprechende Anzahl von Lebens- und Zauberquellen zufällig auf dem Feld verteilt wird.
    • 40% der Tests in jedem Satz werden wie folgt erzeugt: n, m, k sind gleich wahrscheinlich, wonach k Lebensquellen zufällig auf dem Feld verteilt werden. Eine magische Quelle wird zufällig neben jeder Lebensquelle erzeugt, so dass die Koordinatendifferenz auf jeder Achse d nicht überschreitet, wobei d eine feste Zahl für den Test von 1 bis 4 ist, die gleich gewählt wird.
    • 20% der Tests in jedem Satz werden wie folgt erzeugt: n, m, k werden mit gleicher Wahrscheinlichkeit ausgewählt, wonach eine Zahl s so gewählt wird, dass 2s ≤ min (n, m) und k ≤ 4 (s - 1). Danach wurden zufällig zwei disjunkte Quadrate der Größe s × s auf dem Feld ausgewählt, in denen k Lebensquellen zufällig verteilt sind k und in den anderen k Quellen der Magie.

    Wenn beim nächsten Generierungsschritt in einem der Algorithmen keine weiteren Aktionen ausgeführt werden können, wird der gesamte Generierungsprozess erneut gestartet.


    Beispiel


    EingabeFazit
    4 6 3
    0 0
    1 3
    3 0
    3 5
    2 4
    2 2
    aaabbc
    aaabbc
    aaabbc
    cccccc

    Hinweise


    Das Beispiel hat drei Bereiche:


    • Bereich 'a': Bereich 9, Umfang 3 + 3 + 3 + 3 = 12, "Ausbuchtung" 0,0625
    • Bereich 'b': Bereich 6, Umfang 3 + 2 + 3 + 2 = 10, "Ausbuchtung" 0,06
    • Bereich "c": Bereich 9, Umfang 4 + 6 + 1 + 5 + 3 + 1 = 20, "Ausbuchtung" 0,0225

    Dann ist die durchschnittliche "Ausbuchtung" gleich 0,048 (3), und die Anzahl der Punkte für diesen Test beträgt 7733.


    Sie können Entscheidungen höchstens alle 5 Minuten einreichen.




    Konstantin Khadaev (Russland, 7. Platz nach den Ergebnissen der Runde)

    Zuerst finden wir einige Wege von einer Quelle zur anderen. Dies ist eine Standard-Threading-Aufgabe. Einige Teilnehmer hier verwendeten Min-Cost-Max-Flow, aber in meiner Lösung gab es kein Wachstum, und in der neuesten Version habe ich den Dinits-Algorithmus verlassen.

    Dann müssen Sie irgendwie alle anderen Zellen verteilen. Ich habe das sehr primitiv gemacht. Wir gehen alle nicht zugewiesenen Zellen durch und wählen einen zufälligen Nachbarn aus. Wenn einem Sohn ein Nachbar gegeben wird, geben wir ihm diesen Käfig. Andernfalls lassen Sie es undefiniert. Und so iterieren wir, bis wir alle Zellen verteilt haben. Kleinere Optimierung: Wenn drei Nachbarn demselben Sohn übergeben werden, müssen wir ihm den Käfig geben.

    Natürlich können Sie den beiden vorherigen Schritten eine Zufälligkeit hinzufügen. Mische die Eckpunkte für Dinitsa und durchlaufe die Zellen in zufälliger Reihenfolge.

    Dann haben wir eine Art Karte, die wir lokal optimieren werden.

    Hier habe ich drei Fälle:
    • Eine Zelle hat nur einen Nachbarn aus demselben Gebiet wie sie und mindestens zwei Nachbarn aus dem anderen. Dann soll sie dorthin versetzt werden, mit wem sie zwei Nachbarn hat.
    • Die Zelle hat zwei Nachbarn aus demselben Gebiet und zwei aus einem anderen. Dann hängt der Nutzen der Übertragung vom Gebiet dieser Gebiete ab.
    • Die Zelle hat einen Nachbarn aus demselben Gebiet und einen Nachbarn aus drei weiteren.

    Um schnell zu verstehen, was in den Fällen 2 und 3 rentabler ist, müssen Sie die Fläche und den Umfang aller Gebiete pflegen. In jedem Fall war jedoch ein deutlicher Anstieg zu verzeichnen.

    Nun, all dies kann viele Male gemacht werden, solange Zeit ist, und das Beste auswählen.

    In dieser Form gewinnt die Lösung bereits einige Punkte, erreicht jedoch häufig lokale Tiefstände. Ein möglicher Weg, um damit umzugehen: In den Fällen 2 und 3 ist die Änderung, auch wenn sie nicht nützlich ist, immer noch mit einer gewissen Wahrscheinlichkeit möglich, und diese Wahrscheinlichkeit nimmt mit jeder Iteration ab. Diese Änderung erhöhte das Ergebnis um fast 200 Punkte.

    Und zum Feedback:
    Mir hat es nicht gefallen, dass es den VK Cup schneidet. Dies gilt übrigens auch für die nächste Runde - es ist am selben Tag wie der russische Code Cup und Distributed Code Jam, ich werde definitiv nicht drei Wettbewerbe an einem Tag gewinnen. Und die Aufgabe ist sehr angenehm, ja.

    Eryx (Polen, 2. Platz nach den Ergebnissen der Runde)

    Vielen Dank für den hervorragenden Wettbewerb und eine sehr interessante Aufgabe. Es war eine Freude, daran zu arbeiten. Das einzige, was mir nicht gefallen hat, war die etwas undurchsichtige Beschreibung der Testdatengenerierung ("Zufallsverteilung" - aber was?). Vielleicht hat es sich gelohnt, den „offiziellen“ Datengenerator (ohne Anfangswert) hinzuzufügen, und wir sollten den nicht trivialen Teil dort belassen, wo wir „sicherstellen müssen, dass die Lösung vorhanden ist“.

    Eine Version meiner Lösung mit Kommentaren finden Sie hier:
    https://www.mimuw.edu.pl/~erykk/yandex/solution.cpp

    Ich sehe, dass ein Teil der Abschlusstests fehlgeschlagen ist (obwohl bei öffentlichen Tests alles in Ordnung war). Ich hatte keine Ahnung, wie man mit Min-Cost-Max-Flow Pfade baut. Ich denke, wenn ich dies als alternativen Ansatz verwenden würde, würde ich die richtigen Antworten auf diese Tests erhalten und möglicherweise andere Ergebnisse verbessern.
    Original in Englisch
    Vielen Dank für den tollen Wettbewerb und die sehr interessante Aufgabe! Es war eine Freude, daran zu arbeiten. Das einzige, was ich nicht mochte, war eine etwas unklare
    Aussage über die Testfallgenerierung ("irgendeine zufällige Verteilung" - aber welche Verteilung?). Möglicherweise könnte sogar ein "offizieller" Testgenerator enthalten sein (ohne Samen), mit dem nicht -trivialer Teil "Stellen Sie sicher, dass eine Lösung vorhanden ist", der von uns implementiert (oder manuell gelöst) werden kann.

    Die kommentierte Version meiner Lösung finden Sie unter:
    https://www.mimuw.edu.pl/~erykk/yandex/solution.cpp

    Ich sehe, dass ich einige Abschlusstests nicht bestanden habe (die öffentlichen Tests waren alle in Ordnung). Ich hatte nicht die Idee, Min-Cost-Max-Flow zum Generieren von Pfaden zu verwenden. Ich denke, dies als alternative Methode zu verwenden, könnte mir helfen, bei diesen wenigen Tests positive Ergebnisse zu erzielen und möglicherweise die Ergebnisse bei anderen Tests zu verbessern.

    Ilya Kornakov (Schweiz, 6. Platz nach den Ergebnissen der Runde)

    Ich habe bereits etwas auf http://codeforces.com/blog/entry/51858?#comment-358766 geschrieben. Ich

    mochte die Aufgabe, modulo Java Brakes. Die Lösung ist wie folgt angeordnet:
    • Zunächst sucht min-cost-max-flow nach Pfaden, die die Quellen und Senken verbinden.
    • Dann dehnen sich die Wege eifrig aus, bis das Feld gefüllt ist. Gierige Schritte versuchen, einer vorhandenen Komponente jeweils eine Zelle sowie ein Spalten- / Zeilensegment hinzuzufügen. Die Zielfunktion ist die Änderung der Geschwindigkeit / (Anzahl der hinzugefügten Zellen + 10).
    • Die resultierende Lösung wird eifrig optimiert, indem Zellen oder Segmente von Spalten / Zeilen zwischen Komponenten geworfen werden (mit derselben Zielfunktion).
    • Der beschriebene Prozess wird mehrmals gestartet, die beste Lösung wird ausgewählt. Dem Prozess wurde Zufall hinzugefügt: Die Kanten im Flussdiagramm werden gemischt, die Fasten in der Gier werden mit einer Zufallszahl von 1 bis 1,2 multipliziert.

    Die meisten Punkte kamen vom Umschreiben der Lösung von Java auf C ++ (~ + 150). Gierige Verbesserungen nach der Erstellung der Lösung sind anscheinend eine nützliche Idee. Aus dem Unrealisierten heraus - versuchen Sie mehr Änderungen in der Gier (z. B. schneiden Sie die "Ecken" - Seitenpaare ab) und machen Sie anstelle des Flusses etwas, das besser für die Zielmetrik geeignet ist (weil für den Fluss ein langer horizontaler Pfad viel besser ist als der Pfad entlang Diagonalen mit der gleichen horizontalen Verschiebung und aus Sicht der Zielmetrik - viel schlimmer). Es gab auch die Idee, simuliertes Tempern anstelle von Gier zu versuchen, aber es blieb keine Zeit mehr.

    Jetzt auch beliebt: