Geekly articles weekly

Wettbewerb von Yandex.Taxi: Analyse des Backend-Tracks der Programmiermeisterschaft


Preisverleihung an die Teilnehmer des Backend-Tracks

Wir fĂŒhren eine Reihe von Analysen der zweiten Programmiermeisterschaft durch. In den letzten Wochen haben wir eine Analyse von drei Tracks veröffentlicht: ML, Frontend und Mobile Development. Es bleibt die Spur im Backend zu analysieren. Es stellte sich als das beliebteste heraus: 2682 Personen nahmen an der Qualifikation teil, 320 von ihnen erreichten das Finale. Aufgaben fĂŒr Backend-Entwickler wurden vom Yandex.Taxi-Team erfunden.

Mars-Gutscheincodes

Autor: Maxim Pedchenko
Zeitlimit1 s
Speicherlimit64 MB
EintretenStandardeingabe oder input.txt
FazitStandardausgabe oder output.txt
Seit dem Start von Yandex.Taxi auf dem Mars sind sechs Monate vergangen. Bis zum Mars-Neujahr beschloss Yandex.Taxi, den Marsianern Aktionscodes zu geben. Es stellte sich jedoch heraus, dass die Marsmenschen keine Werbecodes fĂŒr die Erde verwenden können, da die Server auf dem Mars nicht nach den Regeln der Erde funktionieren. Aus diesem Grund hat Yandex.Taxi spezielle Mars-Promotion-Codes entwickelt.

Der Mars-Werbecode wird wie folgt generiert:

  1. Ein VerschlĂŒsselungsschlĂŒssel wird generiert.
  2. Der VerschlĂŒsselungsschlĂŒssel ist in Teilzeichenfolgen von zufĂ€lliger LĂ€nge unterteilt.
  3. Von allen Unterzeichenfolgen werden Unterzeichenfolgen der LÀnge L ausgewÀhlt.
  4. Die ausgewÀhlten Teilzeichenfolgen werden gemischt und verkettet.
  5. Das Ergebnis der Verkettung ist ein Werbecode.

Herausforderung:
Es ist zu prĂŒfen, ob der eingegebene Aktionscode gĂŒltig ist. Wenn der Aktionscode gĂŒltig ist, mĂŒssen Sie "JA" drucken. Wenn ungĂŒltig, "NEIN".

E / A-Formate, Beispiele und Hinweise

Eingabeformat


<LĂ€nge des Promotion-Codes>
<Aktionscode>

<SchlĂŒssellĂ€nge>

<key>

<TeilstringlÀnge L>

Ausgabeformat


GĂŒltigkeit des Promotion-Codes: JA oder NEIN.

Beispiel 1

EintretenFazit
6
ABCDEA
6
EAABCD
2		YES

Beispiel 2

EintretenFazit
12
MARS1234MARS
24
ASDGRV12MARSS1234VRCMARS
4		YES

Beispiel 3

EintretenFazit
12
ABC123123ABC
9
ABC123123
3		NO

Hinweise


LĂ€nge L> 1.
Promotion-Code-Alphabet [AZ, 0-9].
Die LĂ€nge des Aktionscodes liegt im Bereich [6, 30].
Die SchlĂŒssellĂ€nge liegt im Bereich [6, 30].
TeillĂ€nge L <SchlĂŒssellĂ€nge.
Die LĂ€nge des Aktionscodes ist ein Vielfaches von L.

Lösung


Wir mĂŒssen alle möglichen Partitionen des VerschlĂŒsselungsschlĂŒssels in Teilfolgen der LĂ€nge L berĂŒcksichtigen und prĂŒfen, ob dieser Promo-Code aus möglichen Partitionen zusammengesetzt werden kann.

Der Hinweis ist in den Konditionsnotizen versteckt:
Die LĂ€nge des Aktionscodes liegt im Bereich [6, 30].
Die SchlĂŒssellĂ€nge liegt im Bereich [6, 30].

Kleine EinschrĂ€nkungen deuten darauf hin, dass keine effektive Lösung erforderlich ist, sodass Sie keine Zeit fĂŒr die Suche nach Optimierungen aufwenden mĂŒssen. Es ist besser, das Problem direkt zu lösen.

Diese Situation ist typisch fĂŒr die Produkt-Backend-Entwicklung. Oft gibt es Situationen, in denen Sie Wochen mit dem optimalen Algorithmus verbringen können, aber wenn Sie die EinschrĂ€nkungen abwĂ€gen, wird klar, dass es besser ist, eine schnelle und nicht die optimalste Lösung zu verwenden.

Wir betrachten also die Zeile mit dem Promo-Code als eine Folge von Teilzeichenfolgen S der LĂ€nge L. FĂŒr jede Teilzeichenfolge S finden wir alle gleichlautenden Teilzeichenfolgen S k aus dem ChiffrierschlĂŒssel. Denken Sie fĂŒr jedes S k an seine Verwendung, fahren Sie mit dem nĂ€chsten Teilstring S fort und wiederholen Sie den Algorithmus.

Wenn es fĂŒr die Teilzeichenfolge S nicht möglich ist, nicht verwendete S k zu finden, muss eine andere Variante der Aufteilung versucht werden. Wenn keine andere Variante vorhanden ist, ist der Aktionscode ungĂŒltig.

Wenn fĂŒr jeden S S k fĂŒr mindestens einen Fall gefunden wurde, ist der Aktionscode gĂŒltig.

Optimierung des Mars-Transportsystems

Autoren: Dmitry Polishchuk und Anton Todua
Zeitlimit3 s
Speicherlimit64 MB
EintretenStandardeingabe
FazitStandardausgabe
Es war das Jahr 2058. Kolonien der ersten Siedler waren bereits auf dem Mars gelandet und begannen, sich dort niederzulassen, und Yandex.Taxi begann, ein System von Shuttle-Stationen einzusetzen.

FĂŒr den normalen Betrieb benötigt die Shuttle-Station eine konstante Stromversorgung aus dem Energienetz. Um die Station mit Strom zu versorgen, mĂŒssen Sie entweder einen Uran-Atomgenerator in der Station selbst bauen oder ein Kabel zu einer anderen (bereits mit Strom versorgten) Shuttle-Station verlegen. Die Kosten fĂŒr den Bau eines Generators in verschiedenen Shuttle-Stationen können variieren. Die KabelfĂŒhrung zwischen den Shuttle-Stationen variiert ebenfalls in den Kosten und ist nicht immer möglich. Die Kabelverbindung ist bidirektional.

Die Aufgabe besteht darin, eine effiziente (mit minimalen Kosten verbundene) Stromversorgung fĂŒr alle Shuttle-Stationen bereitzustellen.

Am Eingang erhĂ€lt das Programm die Gesamtzahl der Shuttle-Stationen, die Kosten fĂŒr den Bau von Generatoren fĂŒr jede Shuttle-Station und eine Beschreibung aller möglichen Kabel zwischen den Shuttle-Stationen (Anzahl der angeschlossenen Stationen und Kosten fĂŒr die Kabelverlegung).

E / A-Formate, Beispiele und Hinweise

Eingabeformat


Die erste Zeile enthĂ€lt eine einzelne nicht negative Anzahl von Shuttle-Stationen N ≀ 1000.

Die zweite Zeile enthĂ€lt N Nummern, die die Kosten fĂŒr den Bau des Generators in der entsprechenden Station angeben.

Die dritte Zeile enthĂ€lt eine einzelne nicht negative Anzahl möglicher Kabel K ≀ 100000 zwischen den Shuttle-Stationen.

Die nĂ€chsten K-Leitungen (ab der vierten) enthalten eine Beschreibung eines Kabels - drei ganzzahlige nicht negative Zahlen: die Nummer der ersten Station , die Nummer der zweiten Station und die Kosten fĂŒr die DurchfĂŒhrung .

Ausgabeformat


Eine ganze Zahl gibt die minimalen Stromkosten fĂŒr alle Shuttle-Stationen fĂŒr eine bestimmte Konfiguration an.

Beispiel 1

EintretenFazit
1
77
0		77

Beispiel 2

EintretenFazit
2
11 29
1
1 2 17		28

Hinweise


Stationen sind von eins nummeriert.
Die Zahlen in der Zeile werden durch ein einzelnes Leerzeichen getrennt.
Die Richtigkeit der Eingabedaten muss nicht ĂŒberprĂŒft werden.

Lösung


Erstens lohnt es sich, von einer schönen Beschreibung zu einer ungerichteten gewichteten Grafik ĂŒberzugehen, bei der an der Stelle der Shuttle-Stationen Spitzen auftreten, Kabel zu Kanten werden und die Kosten fĂŒr den Bau von Kabeln sich in die Gewichte der entsprechenden Kanten Ă€ndern. Es bleibt jedoch die Frage, wie die Kosten fĂŒr den Bau von Urangeneratoren in den Stationen (Peaks) selbst zu berĂŒcksichtigen sind. Die Antwort auf diese Frage ist das Wesen des Problems.

Angenommen, es gibt einen anderen Scheitelpunkt - eine Energiequelle, und von diesem Scheitelpunkt wird eine Kante zu jedem Scheitelpunkt des Diagramms gezogen, deren Gewicht den Kosten fĂŒr den Bau eines Urangenerators in der entsprechenden Station (oben) entspricht. Diese Annahme fĂŒhrt uns zu einem zusammenhĂ€ngenden Graphen, der in einen Baum verwandelt werden muss, damit die Summe der Gewichte der Kanten darin so klein wie möglich wird. Dies ist nichts anderes als das Problem, den minimalen Spannbaum in einem Diagramm zu finden. Sie können einen minimalen Spannbaum mit einem der bekannten Algorithmen erstellen, z. B. Prima oder Kraskal.

Beispielcode mit Kommentaren
 #include <algorithm> #include <iostream> #include <tuple> #include <vector> using Price = std::size_t; using Vertex = std::size_t; using Transition = std::tuple<Price, Vertex, Vertex>; using Graph = std::vector<Transition>; //        ( ). class Equals { public: //    . explicit Equals(std::size_t size) { equals_.resize(size); //     . for (std::size_t i = 0; i < size; i++) { equals_[i] = i; } } //   v1  v2   true,    //      . bool Emplace(std::size_t v1, std::size_t v2) { while (v1 != v2) { if (v2 < v1) { std::swap(v1, v2); } auto& next_v2 = equals_[v2]; if (next_v2 == v2) { next_v2 = v1; return true; } v2 = next_v2; } return false; } private: std::vector<size_t> equals_; }; int main() { //   . std::size_t vertex_count = 0; std::cin >> vertex_count; if (vertex_count == 0) { std::cout << 0 << std::endl; return 0; } //    —   —   . vertex_count++; //  . Graph graph; graph.reserve(vertex_count); //       . for (Vertex i = 1; i < vertex_count; i++) { Price price = 0; std::cin >> price; graph.emplace_back(price, 0, i); } //    . std::size_t edge_count = 0; std::cin >> edge_count; for (std::size_t i = 0; i < edge_count; i++) { Price price = 0; Vertex from = 0, to = 0; std::cin >> from >> to >> price; graph.emplace_back(price, from, to); } //      . std::sort(graph.begin(), graph.end()); //      . // https://ru.wikipedia.org/wiki/_ Price result = 0; Equals equals{vertex_count}; for (const auto& [price, from, to] : graph) { if (equals.Emplace(from, to)) { result += price; } } //  . std::cout << result << std::endl; return 0; }

Kein Parkplatz

Autoren: Ilya Mescherin und Artyom Serebriysky
Alle SprachenPython 3.7.3 und Python 2.7
Zeitlimit1 s10 s
Speicherlimit256 MB
EintretenStandardeingabe oder input.txt
FazitStandardausgabe oder output.txt
In einer Stadt durften Autos nicht anhalten, es sei denn, sie bestiegen einen Passagier. Und der Passagier stimmt nicht zu, lĂ€nger als 3 Minuten zu warten. In dieser Stadt bestellt ein FußgĂ€nger ein Taxi zum Punkt X und gibt ein Intervall von 180 Sekunden an. Der Fahrer muss genau in diesem Intervall ankommen. Wenn Sie frĂŒher anreisen, können Sie keinen Passagier erwarten. Wenn Sie zu spĂ€t ankommen, storniert der verĂ€rgerte Passagier die Bestellung.

Aufgrund solcher EinschrÀnkungen blieben nur Z-Fahrer in dieser Stadt, von denen sich jeder zu Beginn der Aufgabe an einer der Spitzenpositionen in der Verkehrsgrafik befindet. Das Steuerungssystem sollte den besten Fahrer aus denjenigen bestimmen, die es schaffen, in dem angegebenen Intervall anzukommen. Der beste Fahrer ist derjenige, der so nah wie möglich am Intervallanfang zur Bestellung kommt. Wenn es mehrere solcher Treiber gibt, dann einen von ihnen.

Jeder Fahrer muss bestimmen, ob er Zeit hat, um in dem angegebenen Intervall anzukommen, und wenn ja, zu welchem ​​frĂŒhesten Zeitpunkt in dem angegebenen Intervall er ankommen kann.

Formale Beschreibung

Gegeben:

  1. Orientierter Graph G mit N Ecken und K Kanten, die Ecken sind von 0 bis N - 1 nummeriert, 0 ≀ N ≀ 10 4 , 0 ≀ K ≀ 10 4 . Jede Flanke entspricht der darin enthaltenen Laufzeit - eine ganze Zahl W, 10 ≀ W ≀ 10 4 .
  2. Auftragsposition in der ID-Zielspalte.
  3. Z-Positionen der Fahrer in der Spalte IDsource 2 , 1 ≀ Z ≀ 10 4 .
  4. Zum Zeitpunkt t 0 ist 0 ≀ t 0 ≀ 600 eine ganze Zahl.

Es ist notwendig, dass jeder Fahrer solche t min findet, dass:

  1. es gibt eine solche Route von der Fahrer-IDsource z zum ID- Ziel, dass der Fahrer bei t min ankommt,
  2. t min ≀ [t 0 ; t 0 + 180],
  3. und dies ist das frĂŒhestmögliche t min : t min ≀ t i fĂŒr jedes t i, das die Punkte 1 und 2 erfĂŒllt,
  4. oder stellen Sie sicher, dass ein solches t min nicht existiert.

E / A-Formate, Beispiele und Hinweise

Eingabeformat


Die Grafik wird in Form von Tripel-Top-Top-End-Zeitreise-Tripeln erstellt.

Eingabedaten, jeder Artikel in einer eigenen Zeile:

1. K ist die Anzahl der Kanten.
2. K verdreifacht ID ID Gewicht - der anfĂ€ngliche Scheitelpunkt der Rippe, der endgĂŒltige Scheitelpunkt der Rippe, wie stark das Auto die Rippe antreibt.
3. ID- Ziel t 0 - Oben auf der Bestellung [Leerzeichen] der Beginn des Bereichs, an dem Sie ankommen mĂŒssen.
4. Z - die Anzahl der Fahrer.
5. (Z-mal) ID z ist das oberste Zeichen des nÀchsten Treibers.

Ausgabeformat


Geben Sie fĂŒr jeden Fahrer in derselben Reihenfolge, in der er sie eingegeben hat, in einer separaten Zeile die berechnete t min oder –1 aus, wenn diese t min nicht existiert.

Beispiel 1

EintretenFazit
2
0 1 10
2 3 10
3 0
1
0		-1

Beispiel 2

EintretenFazit
2
0 1 10
2 3 10
1 0
1
0		10

Beispiel 3

EintretenFazit
1
0 1 10
1 100
1
0		-1

Hinweise


1. Es können mehrere Kanten von Scheitelpunkt A nach Scheitelpunkt B verlaufen, auch solche mit demselben Gewicht.
2. Rippen von A bis A sind erlaubt.
3. Das gleichzeitige Vorhandensein von Kanten (A-> B) und (B-> A) (Zyklen der LÀnge 2) ist zulÀssig.

Lösung


Einzelner Fahrer

ZunĂ€chst analysieren wir einen einfachen Fall mit einem Fahrer. Das Maß fĂŒr die Rippen ist die Zeit [Fahrt darauf], die EinschrĂ€nkungen des Ziels werden in denselben Einheiten ausgedrĂŒckt, sodass wir das Problem umformulieren können: „Der Fahrer fĂ€hrt gemĂ€ĂŸ der Grafik von Punkt A nach Punkt B. Suchen Sie einen minimalen Pfad, dessen LĂ€nge im Segment [T, U] liegt. "

Der einfachste Weg, dies zu tun, besteht darin, einen modifizierten dijkstra von A nach B auszufĂŒhren:

  1. Änderung 1. Nehmen wir an, wir haben das Top von minQ erhalten und es wurde bereits schwarz markiert (dh der Mindestabstand dazu wurde bereits gefunden). Dann ignorieren wir es nicht, sondern verarbeiten es auf die ĂŒbliche Weise - setzen alle angrenzenden Eckpunkte mit dem neuen Abstand zurĂŒck in minQ.
  2. Wir stoppen es nur, wenn der Abstand zum aktuellen Scheitelpunkt minQ streng grĂ¶ĂŸer als U ist.
  3. Nehmen wir an, wir stoßen wĂ€hrend der Überquerung auf den Peak B. Wenn die aktuelle Distanz ≄ T ist, merken Sie sich dies als Antwort R. An dieser Stelle kann auch die Dijkstra unterbrochen werden.

Wenn wir also R haben, ist dies der minimale Pfad mit einer LĂ€nge im erforderlichen Intervall.

Viele Fahrer

Die Lösung fĂŒr die Stirn besteht darin, fĂŒr jeden Fahrer einen Algorithmus auszufĂŒhren. Eine solche Lösung ist jedoch nicht zeitlich begrenzt. Wir mĂŒssen lernen, fĂŒr jeden Fahrer eine Antwort fĂŒr O (1) zu geben.

Dazu modifizieren wir den Algorithmus fĂŒr einen Treiber:

  1. Anstelle der dijkstra vom Fahrer zum Bestellpunkt starten wir die dijkstra vom Bestellpunkt gemĂ€ĂŸ der Grafik mit umgekehrten (!) Kanten.
  2. Wir machen uns die Tatsache zunutze, dass die Anzahl der Eckpunkte ebenfalls auf zehntausend begrenzt war. Lassen Sie uns eine Reihe von Antworten R erhalten - fĂŒr jeden Scheitelpunkt ist dies die minimale Zeit im Bereich [T, U], in der er von A aus erreicht werden kann.
  3. Beim Durchlaufen des Graphen des modifizierten Dijkstroys geben wir ein: Rj = min ( Rj , dist), wenn wir den Scheitelpunkt j treffen und der aktuelle Abstand dazu im gewĂŒnschten Intervall [T, U] liegt.

Dann kann fĂŒr jeden Fahrer am Scheitelpunkt J Rj abgefragt werden , um herauszufinden, ob es einen Pfad gibt, der die Bedingungen erfĂŒllt, und wie lang er ist.

MinQ-Optimierung

Die PfadlĂ€nge ist immer ganzzahlig und von oben auf 781 begrenzt. Bei einer Bestellung bei t 0 = 600 betrĂ€gt die letzte gĂŒltige Sekunde der Ankunft des Fahrers 780. In diesem Fall mĂŒssen Sie zur Implementierung der dijkstra die folgende minQ-Implementierung verwenden.

Wir haben ein Fringe-Array der GrĂ¶ĂŸe [781]. In jedem Element von Fringe i gibt es eine ungeordnete Menge, die die ID aller Scheitelpunkte speichert, zu denen es einen Pfad der LĂ€nge i gibt.

1. FĂŒgen Sie einen Scheitelpunkt mit Abstand D hinzu:

 fringe[D].insert(vertex);

2. Entsprechend den Bedingungen ist das Mindestgewicht der Kante> 0. Anstatt also Elemente einzeln aus minQ zu entnehmen, können Sie das gesamte Segment durchgehen:

 for(int i = 0; i < fringe.size(); ++i) { if(fringe[i].empty()) { continue; } for(auto& vertex : fringe[i]) { // Do some stuff ProcessVertex(vertex, i); } }

Reisekostenrechner

Urheber: Nikolay Filchenko
Alle SprachenPython 3.7.3 und Python 2.7
Zeitlimit3 s65 c
Speicherlimit64 MB256 MB
EintretenStandardeingabe oder input.txt
FazitStandardausgabe oder output.txt
Die Reisekosten sind nach der angegebenen Formel zu berechnen. Jede Fahrt ist durch K ganzzahlige Parameter gekennzeichnet. Die Formel ist in umgekehrter polnischer Schreibweise angegeben.

ZulÀssige Operationen:

  • + - - Addition und Subtraktion;
  • * / - Multiplikation und Ganzzahldivision;
  • <= - Vergleich;
  • ? - Bedingter Operator. Wenn das erste Argument wahr ist, wird das zweite zurĂŒckgegeben, andernfalls das dritte.

Die Variable [az] und ganze Zahlen von -10 9 bis 10 9 werden ebenfalls in der Formel verwendet.

Wir können davon ausgehen, dass die Ergebnisse aller Operationen in der Formel den absoluten Wert von 10 9 nicht ĂŒberschreiten. Das Ergebnis von Vergleichsoperationen wird nur als Argument fĂŒr den bedingten Operator verwendet.

E / A-Formate und Beispiele

Eingabeformat


In der ersten Zeile ist eine Zahl 1 ≀ K ≀ 26 - die Anzahl der Variablen.

Die zweite Zeile enthĂ€lt die Formel zur Berechnung des Preises (nicht mehr als 3⋅10 4 Elemente). Alle Elemente sind durch Leerzeichen getrennt.

In der dritten Zeile ist 1 ≀ N ≀ 10 4 die Anzahl der Tests.

Die nĂ€chsten N Zeilen enthalten jeweils K ganze Zahlen (–10 9 ≀ v ≀ 10 9 ) - die Werte der Variablen in alphabetischer Reihenfolge.

Ausgabeformat


N Zeilen mit einer ganzen Zahl - die Ergebnisse der Ersetzung jedes Wertesatzes. Es ist garantiert, dass das Ergebnis des Ausdrucks endlich und definiert ist

Beispiel 1

EintretenFazit
1
a 2 2 + *
2
2
3		8
12

Beispiel 2

EintretenFazit
2
ab < 5 14 ?
2
10 5
5 10		14
5

Lösung


Dies ist eine Aufgabe fĂŒr eine sorgfĂ€ltige Umsetzung und Aufmerksamkeit. Es gibt zwei Hauptpunkte in der Lösung:

  1. Der ursprĂŒngliche Ausdruck selbst muss in ein Array von Zahlen und Operationen umgewandelt werden, damit die Zeichenfolge nicht in jeden Variablensatz zerlegt wird.
  2. Es muss beachtet werden, dass eine Ganzzahldivision durch Null zu SIGFPE fĂŒhrt. Daher sollte bei der Divisionsoperation explizit ĂŒberprĂŒft werden, ob der Nenner nicht Null ist. Basierend auf der Garantie der Endlichkeit und der Gewissheit des Ergebnisses des gesamten Ausdrucks kann man verstehen: Das Ergebnis solcher Unterteilungen ist nicht am Endergebnis beteiligt und befindet sich in nicht verwendeten Zweigen von bedingten Operatoren, sodass Sie es mit jedem akzeptieren können (z. B. Null).


Habrapostie zum Thema:

Source: https://habr.com/ru/post/de483624/

More articles:


All Articles