Get best of the week

Analystenpraktikum in Yandex: Analyse von Testaufgaben



Hallo Habr!

Einmal, nachdem ich ein anderes Buch über die berüchtigte Datenwissenschaft studiert hatte, kam ich zu dem Schluss, dass es Zeit war, das gesammelte Wissen in die Praxis umzusetzen und das Leben der Analytikabteilung mit eigenen Augen zu sehen. Glücklicherweise hat Yandex eine Auswahl für ein sechsmonatiges Praktikum in die entsprechende Richtung getroffen, und ich konnte nicht vorbeikommen. Die Annahme von Anträgen für 2020 ist bereits abgeschlossen. Daher werde ich in diesem Artikel mit gutem Gewissen die Aufgaben analysieren, die Yandex in der ersten Phase für Antragsteller lösen wollte. Es wird Python-Code geben. Spoiler: schwierig, aber interessant.

Aufgabe 1. Frist


Die Aufgabe


Anfänger versuchen, das Problem zu lösen. Wenn das Problem nicht gelöst werden konnte, verliert er die Motivation und die Erfolgswahrscheinlichkeit beim nächsten Versuch sinkt. Ein Versuch dauert einen Tag und die Aufgabenfrist beträgt 90 Tage. Die Wahrscheinlichkeit, dass der Analyst das Problem aus dem i-ten Versuch löst, ist:

  1. 1(i+1)
  2. 1(i+1)2

Wie wahrscheinlich ist es, dass der Analyst das Problem vor Ablauf der Frist löst?

Entscheidung


Möglicherweise haben Sie bereits Folgendes eingegeben: "@nice_one, Sie sagten, es wäre schwierig, aber was ist das?" Geduld, Freunde, dies ist eine einfache Aufgabe zum Aufwärmen, aber es gibt etwas zu verpassen, wenn Sie nicht über den Zustand nachdenken. Lassen Sie uns das Beispiel des ersten Absatzes untersuchen. Es ist erforderlich, die Gesamtwahrscheinlichkeit zu berechnen, mit der der Analyst das Problem in einem der 90 in der Reserve verfügbaren Tage lösen wird, während die Erfolgswahrscheinlichkeit an jedem i-ten Tag angegeben wird. Eine verlockende Option scheint im Ausdruck eine Zahl von 1 bis 90 anstelle von i zu ersetzen und hinzuzufügen, aber dies ist nicht wahr. Dieser Ausdruck gibt die Wahrscheinlichkeit des Erfolgs an einem bestimmten i-Tag an. Um jedoch zu diesem i-Tag zu gelangen, muss der Analyst in den letzten (i - 1) Tagen versagen. Wenn die Erfolgswahrscheinlichkeit am i-ten Tag ist1(i+1)dann ist die Ausfallwahrscheinlichkeit an diesem Tag also gleich 1−1(i+1)=ii+1. Wie Sie wissen, ist es erforderlich, die Wahrscheinlichkeit jedes Auftretens zu multiplizieren, um die Wahrscheinlichkeit des gleichzeitigen Auftretens mehrerer Ereignisse zu ermitteln. Somit ist die Wahrscheinlichkeit, dass der Analyst in genau n Tagen zurechtkommt, gleich(∏k=1n−1kk+1)⋅1n+1.

Mitglieder, die unter dem Zeichen der Arbeit stehen, sind für das Scheitern in jedem der ersten verantwortlich(n−1)Tage, dann müssen Sie das Produkt mit der Erfolgswahrscheinlichkeit am n-ten Tag multiplizieren.
Wir kennen also für eine beliebige Anzahl von Tagen die Erfolgswahrscheinlichkeit für genau diesen Zeitraum. Wir sind an der Gesamterfolgswahrscheinlichkeit für jeden möglichen Zeitraum von bis zu 90 Tagen einschließlich interessiert. Jetzt können Sie Zahlen von 1 bis 90 ersetzen, jedoch bereits in der resultierenden Formel. Der einfachste Weg ist, eine Schleife in eine Python zu schreiben, die Wahrscheinlichkeiten berechnet und hinzufügt, was ich getan habe.

Der Code
import numpy as np

n = 90

probs = []

for i in range(1, n+1): #   

    prob_now = 1/(i+1) #      

    prob_not_before = []
    
    for k in range(1, i): #      
        prob_not_before.append(k/(k+1))
        
    prob_not_before = np.array(prob_not_before).prod() # 

    probs.append(prob_not_before * prob_now)

s = sum(probs) #   

print(s)


Die Entscheidung des zweiten Absatzes ist der ersten völlig ähnlich, nur die Formel unterscheidet sich. Ich werde den Code verlassen, um den zweiten Punkt zu lösen - ich denke, alles wird klar sein.

Punkt 2
import numpy as np

n = 90

probs = []

for i in range(1, n+1): #   

    prob_now = 1/((i+1)**2) #      

    prob_not_before = []
    
    for k in range(1, i): #      
        prob_not_before.append(1 - (1/((k+1)**2)))
        
    prob_not_before = np.array(prob_not_before).prod() 

    probs.append(prob_not_before * prob_now)

s = sum(probs) #   

print(s)



Aufgabe 2. Das Schicksal des Hamsters


Die Aufgabe


Um im Winter zu überleben, beschloss der gierige, hungrige Hamster, eine Nussfabrik auszurauben, die 1000 Meter von seinem Loch entfernt liegt. In der Fabrik waren noch 3.000 Nüsse übrig. Maximal 1000 Nüsse werden auf die Wangen des Hamsters gelegt. Überall und egal mit was der Hamster geht, jeder Meter muss mit 1 Nuss verstärkt werden. Der Hamster ist bereits in der Fabrik und ist gefährlich. Was ist die maximale Anzahl von Nüssen, die er lagern kann? Die Antwort muss auf die nächste Ganzzahl gerundet werden.

Entscheidung


Erinnert stark an die Aufgabe eines Jeeps, Oder? So ist es, vor uns liegt seine nächste Sorte. Im allgemeinen Fall tritt im Jeep-Problem ein Fahrzeug (in diesem Fall ein Hamster) auf, das unter Bedingungen mit begrenztem Fassungsvermögen des Kraftstoffbehälters (Hamsterbacken) eine bestimmte Strecke zurücklegen muss. Die Idee, die der Lösung eines Problems dieser Klasse zugrunde liegt - auf dem Weg können Sie die Kraftstoffversorgung verlassen und für ein neues zurückkehren. Andernfalls existiert kein einziger Lösungsalgorithmus, da die Anfangsbedingungen und Ziele sehr unterschiedlich sein können. Die hier vorgeschlagene Option ist interessant, da nicht nur die Entfernung von der Fabrik zum Loch zurückgelegt werden muss (was elementar ist, da der Hamster genau 1000 Nüsse aufnehmen kann, was für 1000 Meter ausreicht), sondern auch so viele Nüsse wie möglich darauf übertragen werden müssen. Am besten zeichnen Sie ein Diagramm.Stellen Sie sich eine Länge von 1000 m und einen Vorrat an Nüssen in der Fabrik vor und überlegen Sie, wie der Hamster zu verhalten ist, wenn er 3000 Nüsse in das Loch transportieren möchte, wobei er so wenig wie möglich isst, d. h. die Gesamtstrecke so wenig wie möglich zurückgelegt hat. Versuchen wir, uns in den kleinsten Schritten von jeweils 1 m zu bewegen und alle 3000 Nüsse auf mehreren Fahrten mitzunehmen.

Um 3000 Nüsse an einen beliebigen Punkt zu übertragen, muss der Hamster mindestens dreimal zum vorherigen zurückkehren. Wenn noch 2000 Nüsse übrig sind und der Rest auf dem Weg gegessen wird, benötigt der Hamster zwei Fahrten zum vorherigen Punkt, um sie auf einen neuen zu verschieben. Wenn der Kraftstoff weniger als 1000 Einheiten beträgt, müssen Sie nicht zurück, alles passt in die Wangen des Hamsters. Somit kann der Prozess der Übertragung von Nüssen in drei entsprechende Stufen unterteilt werden. Mal sehen, welchen Kraftstoffverbrauch der Hamster hat. Wenn es mehr als 2.000 Nüsse gibt, muss der Hamster: 1 Meter bewegen:

  1. Nehmen Sie die vollen Nüsse der Nüsse und gehen Sie 1 m
  2. 998 Nüsse entladen (1 aß unterwegs, 1 ging zurück)
  3. Gehe wieder 1 m zurück zum Nussfond
  4. Wiederholen Sie die Schritte 1 bis 3 für die zweitausend Nüsse
  5. Nehmen Sie die letzten tausend und fahren Sie 1 m vorwärts

Somit kostet 1 m Verdrängung mit aller Beute einen Hamster 5 Nüsse. Wenn die Muttern <2000 werden und dies nach 200 m Bewegung geschieht, lautet der Algorithmus wie folgt:

  1. Nehmen Sie die vollen Nüsse der Nüsse und gehen Sie 1 m
  2. 998 Nüsse entladen (1 aß unterwegs, 1 ging zurück)
  3. Gehe wieder 1 m zurück zum Nussfond
  4. Nehmen Sie die letzten tausend und fahren Sie 1 m vorwärts

1 m Verdrängung kostet einen Hamster 3 Nüsse. Wenn er den Punkt von 534 m erreicht, werden insgesamt 2001 Nüsse gegessen, und der Hamster muss die letzten 999 Nüsse nehmen und die restlichen 466 Meter ruhig in sein Loch gehen. Wenn er dort ankommt, bleiben 533 Nüsse in den Wangen - dies ist die Antwort auf das Problem.

Ich möchte darauf hinweisen, dass Aufgaben dieser Klasse sowohl in der Theorie der Algorithmen als auch in Interviews in großen Unternehmen sehr beliebt sind. Der beste Weg, um zu lernen, wie man sie löst, ist Übung. Es gibt keinen einzigen Mechanismus, um es zu lösen (na ja, oder er ist an mir vorbei geschwommen), aber es ist durchaus möglich, sie in die Hand zu nehmen und kreatives Denken zu entwickeln.

Aufgabe 3. Analytische Verteilung


Die Aufgabe


Yandex will schaffen MAnalystenteams. Bei der Einstellung wählt jeder Analyst zufällig eine Gruppe für sich aus, in der er arbeiten wird. Der Teamleiter möchte herausfinden, welche Mindestanzahl von Tausenden von Analysten ausreicht, um seine Gruppe einzustellenP war nicht weniger NPerson?

Sie müssen ein Python-Programm schreiben, das akzeptiertN, Mund Pin einer Zeile, und die Ausgabe gibt die Anzahl von Tausenden von Analysten an.
1≤N≤100, 1≤M≤100000, 0≤P≤1

Entscheidung


Nun, Kenntnisse der Statistik, nämlich der Binomialverteilung , waren nützlich . Wir geben die Anzahl der von Yandex angeheuerten Analysten anX. Jeder der eingestellten Analysten wählt ein Team. Aus Sicht unseres Teamleiters ist die Einstellung eines Analysten für die Arbeit ein Experiment mit zwei Ergebnissen: Entweder fällt ein Neuling in unser Team oder nicht. Trefferwahrscheinlichkeit gleich1Mbeträgt die Wahrscheinlichkeit, dass der Analyst eine andere Gruppe auswählt M−1M. Insgesamt werden solche Experimente mit der Wahl des Teams seinX. Die Anzahl der Treffer in unserem Teamn von XDie Wahl der Analysten erfolgt binomial, die Verteilungsfunktion ist gleich:

P(n⩽N)=∑k=0N(Xk)(1M)k(M−1M)X−k

Diese Funktion zeigt die Wahrscheinlichkeit an, dass die Anzahl der Treffer kleiner oder gleich der angegebenen ist N. Wir sind an der Wahrscheinlichkeit interessiert, dass die Anzahl der Treffer größer oder gleich der angegebenen ist, daher sieht die Aufgabe folgendermaßen aus:

X:1−Px(n⩽N)=P;X−?


Das heißt, Sie müssen die Anzahl der eingestellten Analysten ermitteln Xbei dem bekommt das team wenigstens NPerson für eine gegebene Wahrscheinlichkeit P.

Nun, wir haben die Mathematik herausgefunden - wie man sie jetzt findetX? Busting. Sie können einen Zyklus schreiben, der die Anzahl der eingestellten Analysten sortiert und erhöht, bis die Wahrscheinlichkeit mindestens erreicht istN Analysten werden nicht zufriedenstellend sein.

Der Code
def c(n, k): #   ,    
    if 0 <= k <= n:
        nn = 1
        kk = 1
        for t in range(1, min(k, n - k) + 1):
            nn *= n
            kk *= t
            n -= 1
        return nn // kk
    else:
        return 0

def bin_prob(trials, k, m): #      

    return c(trials, k) * ((1/m)**k) * ((1 - 1/m)**(trials - k))

def cdf(maximum, trials, m): #   
    value = 0
    for i in range(maximum + 1):
        value += bin_prob(trials, i, m)
    return value

n, m, p = [(float(i)) for i in input().split()] #       
n = int(n)
m = int(m)


x = 1000 
while (1 - cdf(n, x, m)) < p: #      
    x += 1000 #   

print(int(x / 1000)) #



Aufgabe 4. Geschenkforschung


Die Aufgabe


Der Weihnachtsmann brachte Anastasia 100 Geschenke und legte sie unter den Weihnachtsbaum. Der Baum ist groß und flauschig, daher ist es schwierig, unter Anastasia zu navigieren. Anastasia untersucht Geschenke auf diese Weise: Sie greift versehentlich von der zufälligen Seite des Baums in einen zufälligen Bereich, nimmt ein Geschenk entgegen, untersucht es und legt es zurück. Es stellt sich heraus, dass Anastasia jedes Mal gleichermaßen wahrscheinlich Geschenke von denen annehmen kann, die unter dem Baum liegen. Finden Sie die Erwartung des Anteils an Geschenken, den Anastasia für 100 zufällige Strecken in Betracht ziehen wird?

Entscheidung


Auf den ersten Blick scheint die Aufgabe sehr einfach zu sein, sogar das Vertrauen scheint, dass eine Lösung durch eine Elementarformel gefunden werden kann, aber nicht alles ist so einfach. Nicht so einfach. Ich habe unanständig viel Zeit mit dieser Aufgabe verbracht und versucht, Optionen zu malen und eine Formel abzuleiten, aber es ist mir nicht gelungen. Dann ging ich zu Google und musste mich zu meiner Überraschung tief in die Foren vertiefen, bevor ich eine Lösung für den allgemeinen Fall fand . Wenn wir also zufällig Elemente aus einer Menge mit einer Rendite auswählen, ist die Wahrscheinlichkeitn Auswahl aus mElemente des Sets ziehen sich genau heraus kverschiedene gleich:

P(m,k,n)=(mk)⋅k!⋅S2(n,k)mn


Wo S2Es gibt eine Stirling-Nummer der zweiten Art - die Anzahl der ungeordneten Partitionen des Sets vonn Artikel auf knicht leere Teilmengen. Nun, um die Erwartung zu finden, ist es notwendig, die nach dieser Formel berechneten Wahrscheinlichkeiten für jeden möglichen Bruchteil der untersuchten einzigartigen Geschenke zu addieren - von einem Hundertstel bis zu einem Ganzen. Dies kann mithilfe einer Schleife in Python erfolgen.

Der Code
import math
import numpy as np
import sys
import sympy #     -   

sys.setrecursionlimit(10**9)

def c(n, k): # C

    return (math.factorial(n))/(math.factorial(k) * math.factorial(n-k))

def s(n, k): #      

    return sympy.functions.combinatorial.numbers.stirling(n, k)

    
def p(m, k, n): #    k

    return c(m, k) * math.factorial(k) * s(n, k) / (m**n)


pr = []
#      ,    ...
for j in range(1, 101): 
    pr.append(p(100, j, 100))
    
pr = np.array(pr)
#...    100
frac = np.array([i for i in range(1, 101)]) / 100


print(sum(pr*frac)) #



Aufgabe 5. Gleichwahrscheinlicher Reisender


Die Aufgabe


Der Reisende beginnt sich entlang der Ränder eines zweidimensionalen Gitters zu bewegen, wobei ganze Knoten streng nach rechts oder oben gerichtet sind. Er bewegt sich von einem Punkt(0,0) genau (100,100). Wie wahrscheinlich ist es, einen Fluss in einer geraden Linie zu überqueren, die den Start- und Endpunkt verbindet, wenn wir davon ausgehen, dass alle möglichen Routen gleich wahrscheinlich sind? Es wird angenommen, dass der Reisende den Fluss überquerte, wenn er sich ausschließlich über und unter dem Fluss auf derselben Route befand. Ein Flusseintritt wird nicht als Kreuzung betrachtet.

Entscheidung


Wir finden die Wahrscheinlichkeit, den klassischen Ansatz zu überqueren - wir teilen die Anzahl der Routen mit Kreuzung durch die Gesamtzahl der möglichen Routen. Lassenn- die Länge der Kanten des quadratischen Gitters. Dann die Gesamtzahl der möglichen Routen:

N=(2n!)(n!)2


Die Ableitung der Formel wird hier beschrieben . Aber wie kann man die Anzahl der Flussüberquerungsrouten für jede herausfinden?n? Nachdem ich von dieser Frage verwirrt war, entschied ich mich, ein paar kleinere Gitterlängen zu nehmen, Felder zu zeichnen und manuell zu berechnen, wie viele Routen den Fluss überqueren, in der Hoffnung, die Abhängigkeit zu verfolgen (ich empfehle dringend, jetzt auch ein Stück Papier und einen Stift zu nehmen und mit dem Zeichnen kleiner Gitter und Pfade zu experimentieren).

Es sei ein Raster mit einer Größe von 3 mal 3 Zellen vorhanden. Die Seitendiagonale des Gitters wird vom Fluss besetzt, der Reisende befindet sich in der unteren linken Ecke.

Bild
Die Zeichnung ist nicht perfekt, aber ich habe es ehrlich versucht



Als ich die Zeichnung machte, wurde mir klar, dass es viel einfacher sein würde, die Routen zu verfolgen, die der Fluss nicht kreuzt, nämlich die Routen unterhalb des Flusses. Dann ist es möglich, ihre Zahl mit 2 zu multiplizieren, wobei die Spiegelpfade über dem Fluss berücksichtigt werden. Da wir auch die Gesamtzahl der Routen kennen, finden wir die Anzahl der Menschen, die den Fluss überqueren. Aber zurück zur Hauptaufgabe - wir brauchen eine Beziehung zwischennund die Anzahl der Flusskreuzungswege.

In der obigen Abbildung für den Fall von 3x3 habe ich einige für den Reisenden zugängliche "Land" -Routen blau markiert: Die markierten Routen verlaufen entlang der Zellenränder mit einer horizontalen Koordinate von 2, der Reisende betritt zuvor nicht die linken und oberen Kanten der Zellen. Es gibt 3 solcher Routen, d.h.n. Lassen Sie uns nun die Routen herausfinden, die durch die Zelle in Spalte 1 führen.

Bild


Ich habe die neuen Pfade rot markiert. Es ist also klar, dass, wenn sich ein Reisender nach links und dann zum oberen Rand der Zelle (1, 0) dreht, ihm nur 2 der drei Pfade durch die Zellen mit einer horizontalen Koordinate von 2 zugänglich sind, da Sie sich nur nach oben und rechts bewegen können - der dritte Pfad liegt tiefer . Durch Hinzufügen einer neuen Zelle aus Spalte 1 zur Route haben wir die Gesamtzahl der Pfade um die Anzahl der Routen erhöht, die durch die Zellen der Spalte 2 verlaufen und nicht niedriger als unsere neue Zelle sind.

Nehmen Sie ein 4 x 4-Raster und lösen Sie das Gewirr weiter. Es wurde deutlich, dass das Hinzufügen einer neuen Zelle zu einer Spalte die Anzahl der Pfade um die Anzahl der Routen erhöht, die durch die nächste Spalte nicht niedriger als die Oberkante der hinzugefügten Zelle verlaufen. Ich werde die Routen nicht mit Farbe markieren, ich werde mich auf eine Textbeschreibung beschränken, aber wenn Sie es für notwendig halten, zeichnen Sie - beim Lösen habe ich ein Dutzend verschiedene Gitter gezeichnet, bevor ich die Abhängigkeit sicher spüren konnte.

Bild


Die Spalte ganz rechts gibt uns wieder nRouten. Die Oberkante der Zelle (2, 0) wird zu uns hinzugefügtn−1Route. Die Oberkante der Zelle (2, 1) wird hinzugefügtn−2Route. Die Oberkante der Zelle (1, 0) fügt so viele Routen hinzu, wie die Zellen (2, 0) und (2, 1) zusammen addiert haben. Wenn Sie möchten, können Sie ein größeres Raster zeichnen und die Routen weiterhin mit demselben Algorithmus berücksichtigen. Unsere Aufgabe ist es, die Routen für ein 100x100-Raster zu berechnen. Dazu können Sie ein Programm schreiben, das die Eingabe akzeptiertn und bauen Sie eine Matrix n×nausgehend von der Spalte nund dann für jede Zelle der vorherigen Spalten die Anzahl der von der Zelle hinzugefügten Pfade basierend auf den Daten der vorherigen Spalte zählen. Somit wird die Anzahl der Nicht-Flusskreuzungswege gefunden.

Der Code
import numpy as np
import math

def routes_total(n): #   
    return math.factorial(2*n) / (math.factorial(n)**2)

def fill_matrix(n): #  ,       
    net = np.zeros((n, n)) 
    net[0, 0] = n #    n 
    for i in range(n-2):
        net[1, i] = n - i - 1 

    for i in range(2, n):
        for j in range(n - i - 1): 
            net[i, j] = 0
            for g in range(j, n - i + 1):
                net[i, j] += net[i - 1, g]
    
    #      2,     
    return (2 * sum(sum(net))) 

#      -    1
print(1  - fill_matrix(100) / routes_total(100))



Aufgabe 6. Zustand der linearen Verteilung


Die Aufgabe


Der lineare Verteilungsstaat ist eine Vielzahl von Städten, von denen einige durch Straßen verbunden sind.

Als der König des Staates bemerkte, dass das Volk der Haltepunkte im Begriff war, in seine Grenzen einzudringen. Da der Staat nicht zur Verteidigung bereit war, traf der König eine schwierige Entscheidung - den Staat in viele kleine zu teilen, von denen jeder seine Grenzen unabhängig verteidigen wird.

Es wurde beschlossen, dass zwei Städte in einem Bundesstaat belassen werden können und sollten, wenn eine Stadt im zweiten erreicht werden kann, auch wenn die People of the Breakpoints eine Straße zwischen zwei Städten des Staates der linearen Verteilung belegen. In allen anderen Fällen müssen sich Städte in verschiedenen Bundesstaaten befinden.

Auf jeder Straße, die die Grenze zweier neuer Staaten überquert, muss eine Bastion errichtet werden. Dies ist erforderlich, wenn einer dieser Zustände von den People of Breakpoints erfasst wird. Dann kann der zweite seine Grenzen weiter verteidigen. Mit anderen Worten, die Bastion wird auf die Straße gebracht, die Städte aus verschiedenen Staaten verbindet.

Der König bat Sie, ihm eine Liste der Straßen zu geben, auf denen Sie Bastionen errichten müssen.

Programmeingabe- und Ausgabeformat

nm— . (1≤n≤20000,1≤m≤200000). m . i bi,ei— , (1≤bi,ei≤n)


b — , . b — , , . , .

, , , , — .


Entscheidung


Und hier ist das Problem der Graphentheorie. Für lange Geschichten über das Schicksal des Zustands der linearen Verteilung verbargen die Verfasser die ziemlich interessante Aufgabe, Brücken in einem Diagramm zu finden, dessen Knoten Städte und deren Kanten Straßen sind. Kurz gesagt, eine Brücke ist eine solche Kante eines Graphen, deren Entfernung einen bestimmten Teil dieses Graphen von anderen Eckpunkten abschneidet. Dies ist die Idee, die Straße zu erobern - wenn die Brücke erobert wird, wird die Kommunikation zwischen einigen Städten unterbrochen, andernfalls wird es immer eine alternative Straße zwischen den Städten geben, daher sind es die Brücken, die die Staaten teilen, es ist notwendig, Bastionen auf die Brücken zu setzen.

Brückensuchalgorithmus basierend auf der Tiefensuche(Depth-First-Suche, DFS) - Eine Graph-Traversal-Methode, bei der alle vom anfänglichen Scheitelpunkt kommenden Kanten untersucht werden. Wenn die Kante zu einem Scheitelpunkt führt, der noch nicht berücksichtigt wurde, startet der Algorithmus sofort rekursiv von diesem Scheitelpunkt aus. Die folgende Tatsache hilft bei der Suche nach Brücken:

Angenommen, wir schauen in die Tiefe und betrachten jetzt alle Kanten vom Scheitelpunkt V. Wenn die aktuelle Kante (V, U) so ist, dass vom Scheitelpunkt U und von einem ihrer Nachkommen im Traversalbaum keine Umkehrung erfolgt Auf dem Weg zum Gipfel von V oder einem seiner Vorfahren ist der betrachtete Rand eine Brücke.

Um zu lernen, wie diese Tatsache für den Scheitelpunkt V verifiziert werden kann, führen wir den Zeitpunkt des Eintritts in die Scheitelpunktscheibe [V] ein.(aus dem Englischen. entdeckt). In dieser Variablen wird der Schritt des Algorithmus aufgezeichnet, bei dem der Scheitelpunkt verarbeitet wurde. Außerdem wird jedem Scheitelpunkt V die niedrigste [V] -Variable zugeordnet , in die wir den Zeitpunkt des Auftretens des frühesten Scheitelpunkts U schreiben, der vom Scheitelpunkt V aus erreicht werden kann. Während der anfänglichen Verarbeitung des Scheitelpunkts niedrigste [V] = Scheibe [V] (zum Scheitelpunkt früher als selbst), aber später im Prozess der eingehenden Suche können wir einen Sohn V finden, dessen einer Rand zum Vorfahren von V führt (nennen wir ihn S). In diesem Fall aktualisieren wir das niedrigste [V]: das niedrigste [V] = die Scheibe [S]. Und wann können wir die Brücke einhaken? Wenn wir dann gründlich suchen, erreichen wir die Spitze, die keine Söhne hat, die noch nicht berücksichtigt wurden (wieder nennen wir es U). In diesem Fall prüfen wir, welcher früheste Scheitelpunkt von U aus erreicht werden kann, und wenn dieser früheste Scheitelpunkt später als der unmittelbare Elternteil von U auftritt (Dies ist beispielsweise möglich, wenn U keine Söhne hat, dann ist niedrigstes [U] = Scheibe [U. ] ), dann ist die Verbindung von U mit dem Elternteil eine Brücke.

Der Code des implementierten Algorithmus mit Kommentaren ist unten angefügt. Es ist praktisch, keine separaten Variablen für die Disc und den niedrigsten Wert jedes Scheitelpunkts zu erstellen, sondern Arrays für jeden Wert zu erstellen, wobei der Index die Nummer des Scheitelpunkts ist, auf den sich der Wert bezieht.

Der Code
import sys
from collections import Counter
import numpy as np
sys.setrecursionlimit(10**6) 

n, m = [int(i) for i in input().split()]
roads = [None] #    -    
graph = {}  #      ,    
for i in range(1, n+1):
    graph[i] = []
for i in range(1, m+1):
    twns = [int(j) for j in input().split()]
    graph[twns[0]].append(twns[1])
    graph[twns[1]].append(twns[0])
    roads.append(frozenset([j for j in twns]))
    
disc = [0] * (n+1) #  discovered
lowest = disc.copy() #  lowest
used = disc.copy() #  used. ,    
c = Counter(roads)

timer = 0 #   
nbridges = 0 #  
bridges = [] #  

def dfs(v, parent): #    ,    
    
    global timer
    global nbridges
    global bridges
    
    timer += 1 #   
    disc[v] = timer 
    lowest[v] = timer
    used[v] = True #     
    for u in graph[v]: #      
        if u == parent:
            continue #      ,    ,    
        if used[u]: #  ,    ,  
            lowest[v] = min(lowest[v], disc[u]) # ,       ;  lowest 
        else: #   
            dfs(u, v) #      
            #           cc  U:
            lowest[v] = min(lowest[v], lowest[u])  
            if lowest[u] > disc[v]: #   u    v   ,   
                twns = [] # ,  
                twns.append(u)
                twns.append(v)
                if c[frozenset(twns)] > 1: #     ,  ,    
                    continue
                nbridges += 1
                bridges.append(roads.index(set(twns)))

dfs(1, 0) #      

print(nbridges)
bridges = np.sort(bridges)
for bridge in bridges:
    print(bridge)



Die folgende Quelle hat mir in vielerlei Hinsicht geholfen, mit dem Problem umzugehen. Daher halte ich es für notwendig, einen Link dazu zu hinterlassen. Es lohnt sich anzusehen und hier ist dieses Video - es gibt eine gute Animation des Algorithmus.

Fazit


Dies sind die Aufgaben, die ein Spezialist, der sich für ein Praktikum bei Yandex bewirbt, sicher lösen sollte. Die oben genannten Aufgaben wurden mit 5 Stunden erledigt - meiner Meinung nach ziemlich kurze Zeit, aber jeder arbeitet in seinem eigenen Tempo.

Meine Entscheidungen wurden getestet und geben die richtigen Antworten, aber ich habe keinen Zweifel daran, dass es effektivere Möglichkeiten gibt, die vorgeschlagenen Aufgaben zu bewältigen. Wenn Sie bereit sind, eine schnellere oder verständlichere Lösung anzubieten, oder wenn Sie einen Fehler bei mir finden, zögern Sie nicht, darüber zu schreiben.

Ich wünsche jedem, eine Stelle für sich zu finden!

More articles:


All Articles