Am ersten Juni fand das Finale unserer Programmiermeisterschaft statt. Die Namen der Gewinner sind bereits bekannt. Bald werden sie ihre Auszeichnungen erhalten, und in der Zwischenzeit veröffentlichen wir eine Analyse der Aufgaben der Meisterschaft. Zunächst analysieren wir die Aufgaben der Qualifizierungsphase unter den Backend-Entwicklern.
Die Qualifikation dauert eine Woche, und die Anzahl der Teilnehmer zu Tausenden. Daher stellt sich heraus, dass die Vorbereitung von Aufgaben keine leichte Aufgabe ist. Insgesamt mussten wir 24 Aufgaben erledigen und diese auf die vier Optionen aufteilen, damit die Optionen in ihrer Komplexität vergleichbar waren.
Diesmal haben wir sechs Aufgaben entwickelt, für die jeweils mehrere alternative Formulierungen entwickelt werden konnten: Aus einer erfundenen Aufgabe entstanden vier gleichzeitig! Somit erwiesen sich die Optionen als möglichst vergleichbar.
Daher werde ich keine Analysen aller 24 Probleme veröffentlichen. Stattdessen werde ich die sechs Aufgaben einer der Qualifikationsoptionen analysieren: Andere werden auf ähnliche Weise gelöst.
A. Alarme
AufgabenbedingungDie Arbeit in den meisten IT-Unternehmen hat viele Vorteile: Es gibt keine Kleiderordnung, manchmal können Sie remote arbeiten, coole und kluge Kollegen und natürlich einen kostenlosen Zeitplan! Ein freier Zeitplan und die Fähigkeit, aus der Ferne zu arbeiten, erfordern jedoch viel Willenskraft.
Der Programmierer Alexei arbeitet gerne nachts und kommt nicht gerne spät zur Arbeit. Um morgens genau aufzuwachen, beginnt Alexey jede Nacht N Alarme auf Ihrem Telefon. Jeder Wecker ist so eingestellt, dass er jeden klingelt X Minuten ab dem Zeitpunkt, zu dem er brachte. Zum Beispiel, wenn zu einem bestimmten Zeitpunkt ein Alarm eingestellt wurde ti dann wird er mal anrufen ti , ti+X , ti+2 cdotX usw. Wenn gleichzeitig zwei Alarme zu einem bestimmten Zeitpunkt zu klingeln beginnen, wird nur einer von ihnen angezeigt.
Es ist bekannt, dass Alexey vor dem Aufwachen jeden Morgen zuhört K Wecker, nach denen es aufwacht. Bestimmen Sie den Zeitpunkt, zu dem Alex aufwacht.
Alle Alarme klingeln zu ganzzahligen Zeiten, und alle Alarme haben dieselbe Anrufschlummerperiode. Wenn zu bestimmten Zeitpunkten zwei Alarme eingestellt sind ti und tj und diese Zeitpunkte ergeben den gleichen Rest, wenn sie durch geteilt werden X können Sie nur einen Wecker lassen - den, der den ersten klingelt.
Der erste Schritt besteht also darin, unnötige Alarme zu beseitigen: Wir werden sie nach dem Wert des Restes der Division durch gruppieren X und von jeder Gruppe lassen wir zum frühesten Zeitpunkt nur einen Wecker eingestellt.
Jetzt lernen wir, wie Sie bestimmen können, wie viele Alarme zu einem bestimmten Zeitpunkt klingelten T . Wenn der Alarm rechtzeitig eingestellt ist ti , die Anzahl seiner Anrufe zu der Zeit T wird gleich sein
max Big( fracT−tiX,0 Big).
Wenn wir diese Werte für alle Alarme addieren, erhalten wir die Gesamtzahl der klingelnden Alarme nach Zeit T .
Danach wird das anfängliche Problem durch binäre Suche durch gelöst T : mit Zunahme T die Anzahl der Klingelalarme nimmt nicht ab (d. h. die Funktion ist eintönig); Sie können 0 als anfänglichen linken Rand und die maximal mögliche Antwort im Problem mit dem rechten auswählen.
B. Sportturnier
AufgabenbedingungWährend Mascha im Urlaub war, organisierten ihre Kollegen ein Schachturnier im olympischen System. Während des Restes hat Mascha diesem Unterfangen nicht viel Aufmerksamkeit geschenkt, so dass sie sich kaum erinnern kann, wer mit wem gespielt hat (über die Reihenfolge der Spiele gibt es keine Frage). Plötzlich kam Mascha die Idee, dass es schön wäre, dem Gewinner des Turniers ein Souvenir aus dem Urlaub zu bringen. Mascha weiß nicht, wer das letzte Spiel gewonnen hat, aber sie kann leicht herausfinden, wer darin gespielt hat, wenn sie sich nur richtig an die spielenden Paare erinnert. Helfen Sie ihr zu überprüfen, ob dies der Fall ist, und identifizieren Sie mögliche Kandidaten für die Gewinner.
Dieses Problem kann durch Wiederherstellen des Diagramms der Turnierspiele gelöst werden. Zunächst ist für jeden Teilnehmer klar, welche Phase des Turniers er erreicht hat: Dies wird durch die Anzahl der Spiele mit seiner Teilnahme bestimmt.
Danach können Sie die Spiele auf Touren verteilen. Angenommen, in allen Spielen der ersten Runde ist einer der Teilnehmer in der ersten Runde gestartet, und der andere ist nicht früher als in der zweiten Runde gestartet. Bei der Bearbeitung eines Tourspiels mit einer Nummer x Es muss überprüft werden, ob alle Teilnehmer an diesem Spiel derzeit die gleiche Anzahl von Spielen gespielt haben, die der Anzahl entspricht x Andernfalls ist das Turnier ungültig.
Nach der Wiederherstellung des Turnierschemas müssen Sie nur noch die Antwort ableiten.
C. Interessantes Spiel
AufgabenbedingungPetya und Vasya spielen ein interessantes Spiel. Zuerst gibt Vasya bekannt, wie viele Punkte Sie benötigen, um das Spiel zu beenden. Dann nimmt Petja die Karten, auf die nicht negative ganze Zahlen geschrieben sind, und legt sie nacheinander auf den Tisch. Wenn die Karte ein Vielfaches von fünf enthält, erhält Vasya einen Punkt. Befindet sich ein Vielfaches von drei auf der Karte, erhält ein Punkt Petja. Wenn sich auf der Karte eine Zahl befindet, die kein Vielfaches von drei oder fünf ist, oder umgekehrt, ein Vielfaches von beiden, erhält niemand Punkte.
Sobald einer der Teilnehmer die Anzahl der Punkte erreicht, die Vasya zu Beginn des Spiels benannt hat, stoppt das Spiel und dieser Spieler wird der Gewinner. Wenn keiner der Teilnehmer die erforderliche Anzahl von Punkten erzielt hat, aber gleichzeitig alle Karten vorbei sind, gilt der Spieler mit den meisten Punkten als Gewinner. Wenn alle Karten vorbei sind und die Punkte gleichmäßig verteilt sind, wird ein Unentschieden erklärt.
Petya und Vasya haben es manchmal eilig, deshalb möchten sie das Spiel nicht vollständig spielen, sondern sofort herausfinden, wer mit den bekannten Anfangsdaten gewinnen würde. Sie haben Sie gebeten, ein Programm zu schreiben, das Ihnen bei der Beantwortung dieser Frage hilft.
Das Wichtigste bei dieser Aufgabe ist, anhand der Bedingung, welche der Spieler und wie viele Punkte nach jedem neuen Zug vergeben werden und unter welchen Bedingungen der Spieler sie verdient, richtig zu verstehen.
Das Problem wird auf einfache Weise gelöst. Da die Einschränkungen mehr als sanft sind, reicht es aus, die Daten einmal durchzugehen und ihre Verarbeitung zu unterbrechen, wenn einer der Spieler im nächsten Schritt die erforderliche Anzahl von Punkten erzielt hat. Wenn keiner der Spieler die erforderliche Mindestpunktzahl erreicht hat, wird der Gewinner am Ende des Zyklus ermittelt.
In einigen Versionen dieser Aufgabe war es notwendig, die Situation weiter zu behandeln, in der Spieler gleichzeitig Punkte für dieselbe Karte erhalten konnten.
Diese Aufgabe war erwartungsgemäß die einfachste unter allen Qualifikationsaufgaben.
D. Ausnahmeanalysator
AufgabenbedingungWir beschreiben die Syntax einer Programmiersprache EX ::
func f() {...} - Funktionsdeklaration (in Klammern - der Körper)maybethrow Exc ist ein Befehl, der eine Ausnahme vom Typ Exc kann oder nicht.try {...} suppress Exc - Wenn in diesem Block eine Ausnahme vom Typ Exc auftritt, wird sie unterdrückt.f() ist ein Aufruf von f .
In der Sprache EX Alle Anweisungen mit Ausnahme von Funktionsdeklarationen können sich nur im Hauptteil einer Funktion befinden. Funktionen können nicht in anderen Funktionen deklariert werden. Eine Funktion kann sowohl vor ihrer Definition als auch in ihrem eigenen Körper aufgerufen werden. Namen von Funktionen und Ausnahmen in der Sprache EX muss mit dem regulären Ausdruck übereinstimmen [a−zA−Z0−9 ]+ , einzigartig sein und nicht mit den Schlüsselwörtern maybethrow übereinstimmen, try , suppress , maybethrow .
Ein Programm in Sprache wird eingegeben EX und Nummer x . Für jede Funktion des Programms nicht mehr als x Ausnahmen, die daraus herausfliegen können. Sollte ausgeben x lexikographisch kleinste Ausnahmen.
Diese Aufgabe erwies sich als die schwierigste aller Qualifizierungsaufgaben.
Um dies zu lösen, konnte das Programm syntaktisch analysiert werden, indem ein Diagramm mit Funktionsaufrufen erstellt wurde: In diesem Diagramm entspricht jede Funktion einem Scheitelpunkt und dem Funktionsaufruf einer Kante. Danach muss die Logik der Verteilung von Ausnahmen über den Graphen direkt implementiert werden - dafür ist ein Graph-Bypass in der Breite geeignet.
Wir werden eine Ausnahme und alle Funktionen auswählen, die dazu führen können. Diese Funktionen werden von anderen Funktionen aufgerufen. Möglicherweise befinden sich die Aufrufe im try {...} suppress In diesem Fall gilt die Ausnahme nicht für die Funktion, in der der Aufruf erfolgt. Somit ist es möglich, alle Funktionen, von denen diese Ausnahme ausgelöst werden kann, unter Verwendung der Diagrammbreitenüberquerung zu bestimmen.
Nachdem der Bypass für alle möglichen Ausnahmen durchgeführt wurde, bleibt nur noch eine Antwort zu bilden.
E. Dekodierung
AufgabenbedingungEin neuer Dienst ist im Internet erschienen. Leider hat er keine Dokumentation. Empirisch wurde die Zeichenfolge s vom Server empfangen. Einige Zeichen in dieser Zeile sind jedoch codiert. Um eine echte Antwort zu erhalten, müssen Sie diese Zeile mehrmals dekodieren. Da es keine Dokumentation für den Dienst gibt, muss für weitere Experimente bestimmt werden, wie oft diese Zeile maximal nicht trivial dekodiert werden kann. Das Dekodierungsverfahren ist wie folgt: Sie müssen alle Teilzeichenfolgen der Form ~XY , wobei X und Y große oder kleine hexadezimale Ziffern sind, und sie gleichzeitig durch ein Zeichen mit einem ASCII-Code ersetzen 16X+Y (Jeder Teilstring hat seinen eigenen). Die Dekodierung wird als trivial bezeichnet, wenn keine Teilzeichenfolgen dieser Art vorhanden sind.
In einer einzelnen Zeile wird die maximale Anzahl aufeinanderfolgender nicht trivialer Decodierungen der ursprünglichen Zeichenfolge gedruckt.
Wir werden die Zeichen der Quellzeichenfolge nacheinander von links nach rechts betrachten. Wenn das Hinzufügen eines weiteren Zeichens zu einer Sequenz führt, die dekodiert werden kann, müssen Sie dies tun. Die Decodierung sollte so lange wie möglich wiederholt werden, d.h. Am Ende der aktuellen Zeile befindet sich eine Sequenz der Form, die durch die Bedingungen der Aufgabe definiert ist.
Für jedes Zeichen der resultierenden dekodierten Zeichenfolge müssen Sie sich merken, wie oft Sie die ursprüngliche Zeichenfolge dekodieren mussten, um sie zu erhalten. Es ist klar, dass das der Zeichenfolge hinzugefügte Zeichen nullmal dekodiert wird. Wenn die dekodierten Symbole am nächsten Dekodierungsvorgang teilnehmen r1,r2,...,rk Mal benötigt dann das Symbol, das sie gebildet haben max(r1,r2,...,rk)+1 Dekodierungsvorgänge.
Lassen Sie die endgültige dekodierte Zeichenfolge Zeichen enthalten a1,...,ak , um zu erhalten, welche es notwendig war, jeweils eine Decodierung durchzuführen, r1,...,rk mal. Dann ist die Antwort die Menge
max(r1,...,rk).
F. Finden eines Breaking Commits
AufgabenbedingungYandex Search implementiert die sogenannte "Green Trunk" -Richtlinie: Jeder Code, der mit einigen Einschränkungen in das Repository gelangt, wird die Assembly und die Tests garantiert nicht beschädigen.
Tests sind jedoch äußerst schwierig, und es ist unpraktisch, sie alle bei jedem Commit auszuführen. In besonders schwierigen Fällen wird das folgende Verfahren implementiert: Tests werden regelmäßig ausgeführt, und eine Reihe von Festschreibungen wird sofort überprüft. Somit können für einige Zeit n nicht getestete Commits in den Trunk fallen, von denen mindestens einer einen Fehler enthält.
In einer solchen Situation sollte das Testsystem die Anzahl m des ersten Commits ermitteln, der die Tests abgebrochen hat. Diese Nummer hat die folgende Eigenschaft: Alle Commits mit Zahlen kleiner als m bestehen Tests erfolgreich und Commits mit Zahlen größer oder gleich m Fehlertests. Die Aufgabe stellt sicher, dass ein Commit mit den angegebenen Eigenschaften unbedingt vorhanden und eindeutig ist.
Um Ressourcen zu sparen, kann das Testsystem jeweils nur ein Commit überprüfen. Sie müssen ein Programm schreiben, das die Anzahl m bestimmt.
Diese Aufgabe hat einen Prototyp in unserer Produktion: Einige Tests von Suchkomponenten sind wirklich zu kompliziert, sie sind zu teuer, um für jedes Commit ausgeführt zu werden, und für sie ist das Verfahren zum Auffinden von Ausfällen ähnlich dem in der Aufgabe beschriebenen implementiert. Natürlich können Entwickler die Überprüfung vor dem Audit verwenden und dies in der Regel tun, sodass dieses Verfahren nicht so häufig benötigt wird.
Verschiedene Versionen der Aufgabe unterschieden sich in der Anzahl der Commits, die gleichzeitig überprüft werden müssen.
Die Lösung hier ist ganz einfach: Sie müssen eine etwas komplexere Version der binären Suche implementieren. Wenn Sie beispielsweise vier Commits gleichzeitig überprüfen möchten, müssen Sie das aktuelle Segment gleichmäßig mit vier Zahlen aufteilen. Während der Implementierung muss sorgfältig darauf geachtet werden, Schleifen zu vermeiden, wenn die Länge des Segments geringer ist als die Anzahl der gleichzeitig überprüften Commits. Es ist auch erwähnenswert, dass Sie je nach den Bedingungen des Problems dasselbe Commit mehrmals überprüfen können - manchmal müssen Sie dies tun, z. B. wenn es insgesamt zwei Commits gibt und Sie drei Commits gleichzeitig überprüfen müssen.
Die besprochenen Aufgaben der Qualifikationsrunde sind als Codeforces-Training verfügbar. Wir haben auch ein Training zu den Aufgaben des Finales gemacht .