Bonjour, Habr!

Une fois, après avoir étudié un autre livre sur la fameuse Data Science, je suis arrivé à la conclusion qu'il était temps de mettre en pratique les connaissances accumulées et de voir la vie du département analytique de mes propres yeux. Heureusement, Yandex a lancé une sélection pour un stage de six mois dans la bonne direction, et je n'ai pas pu passer. L'acceptation des candidatures 2020 est déjà terminée, donc dans cet article je vais, en toute conscience, analyser les tâches que Yandex a proposé de résoudre pour les candidats dans la première étape. Il y aura du code Python. Spoiler: difficile, mais intéressant.

Tâche 1. Date limite

La tâche

Un analyste novice tente de résoudre le problème. Si le problème ne peut pas être résolu, il perd sa motivation et la probabilité de succès lors de la prochaine tentative diminue. Une tentative prend un jour et le délai de la tâche est de 90 jours. La probabilité que l'analyste résout le problème à partir de la i-ème tentative est:

$\frac{1}{(i+1)}$
$\frac{1}{(i+1)^2}$

Quelle est la probabilité que l'analyste résout le problème avant la date limite?

Décision

Vous avez peut-être déjà atteint pour taper: "@nice_one, vous avez dit que ce serait difficile, mais qu'est-ce que c'est?" Patience, amis, c'est une tâche simple à réchauffer, mais il y a quelque chose à manquer si vous ne pensez pas à la condition. Examinons l'exemple du premier paragraphe. Il est nécessaire de calculer la probabilité totale que l'analyste résoudra le problème dans l'un des 90 jours disponibles dans la réserve, tandis que la probabilité de succès pour chaque i-ème jour est donnée. Une option tentante peut sembler remplacer dans l'expression un nombre de 1 à 90 au lieu de i et ajouter, mais ce n'est pas vrai. Cette expression indique la probabilité de succès un jour i particulier, mais pour arriver à ce jour i, l'analyste doit échouer au cours des (i - 1) derniers jours. Si la probabilité de succès le i-ème jour est

\frac{1}{(i + 1)}

$\frac{1}{(i+1)}$ , alors la probabilité d'échec ce jour-là est donc égale à

1 - \frac{1}{(i + 1)} = \frac{i}{i + 1}

$1 - \frac{1}{(i+1)} = \frac{i}{i+1}$ . Comme vous le savez, pour trouver la probabilité de l'occurrence simultanée de plusieurs événements, il est nécessaire de multiplier la probabilité de chaque occurrence. Ainsi, la probabilité que l'analyste puisse faire face en exactement n jours est

(\prod_{k = 1}^{n - 1} \frac{k}{k + 1}) \cdot \frac{1}{n + 1}

$\biggl(\prod\limits_{k=1}^{n-1}\frac{k}{k+1}\biggr)\cdot\frac{1}{n+1}$ .

Les membres debout sous le signe des travaux sont responsables de l'échec dans chacun des premiers

(n - 1)

$(n - 1)$ jours, alors vous devez multiplier le produit par la probabilité de succès le nième jour.
Ainsi, pour n'importe quel nombre de jours, nous connaissons la probabilité de succès pour exactement cette période. Nous nous intéressons à la probabilité totale de succès pour chaque période possible pouvant aller jusqu'à 90 jours inclus. Vous pouvez maintenant remplacer les nombres de 1 à 90, mais déjà dans la formule résultante. La façon la plus simple est d'écrire une boucle dans du python qui calculera et ajoutera des probabilités, ce que j'ai fait.

Le 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)

La décision du deuxième paragraphe est complètement similaire au premier, seule la formule diffère. Je vais laisser le code résoudre le deuxième point - je pense que tout sera clair.

Point 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)

Tâche 2. Le sort du hamster

La tâche

Afin de survivre en hiver, le hamster avide et gourmand a décidé de voler une fabrique de noix située à 1000 mètres de son trou. Il restait 3 000 noix à l'usine. Un maximum de 1000 noix sont placées sur les joues du hamster. Partout et peu importe ce que le hamster va avec, chaque mètre, il doit être renforcé avec 1 écrou. Le hamster est déjà à l'usine et est dangereux. Quel est le nombre maximum de noix qu'il peut stocker? La réponse doit être arrondie à l'entier le plus proche.

Décision

Rappelle fortement la tâche d'une jeep, n'est-ce pas? Il en est ainsi, devant nous est sa prochaine variété. Dans le cas général, un véhicule (dans ce cas, un hamster) apparaît dans le problème de la jeep, qui doit parcourir une certaine distance dans des conditions de capacité limitée du réservoir de carburant (joues de hamster). L'idée sous-jacente à la solution à n'importe quel problème de cette classe - en cours de route, vous pouvez laisser des réserves de carburant et en revenir pour une nouvelle. Sinon, il n'existe pas d'algorithme de solution unique, car les conditions et objectifs initiaux peuvent être très différents. L'option proposée ici est intéressante car il faut non seulement parcourir la distance de l'usine au trou (ce qui est élémentaire, car le hamster peut contenir exactement 1000 noix, ce qui suffit pour 1000 mètres), mais y transférer autant de noix que possible. Il est préférable de dessiner un diagramme,représentant une longueur de 1000 m et un stock de noix à l'usine, et réfléchissez à la façon d'agir du hamster s'il veut transporter 3000 noix dans le trou, en mangeant le moins possible, c'est-à-dire en ayant passé le moins possible la distance totale. Essayons de nous déplacer aux plus petits pas, 1 m chacun, en transférant les 3000 noix avec vous sur plusieurs voyages.

De toute évidence, afin de transférer 3000 noix à tout moment, le hamster devra revenir au précédent au moins 3 fois. Lorsque 2000 noix restent et le reste est mangé en cours de route, le hamster aura besoin de 2 voyages vers le point précédent afin de les déplacer vers un nouveau. Lorsque le carburant est inférieur à 1000 unités, vous n'avez pas besoin de revenir en arrière, tout tient dans les joues du hamster. Ainsi, le processus de transfert des noix peut être divisé en trois étapes correspondantes. Voyons voir ce que le hamster aura «consommation de carburant» sur chacun. Lorsqu'il y a plus de 2000 noix, pour se déplacer de 1 mètre le hamster devra:

Ramassez les joues pleines de noix et marchez 1 m
Déchargez 998 noix (1 mangé en chemin, 1 à gauche pour revenir en arrière)
Remontez de 1 m vers le stock de noix
Répétez les étapes 1 à 3 pour le deuxième millier de noix
Prenez le dernier millier et avancez 1 m plus loin

Ainsi, un déplacement de 1 m avec toutes les proies coûte à un hamster 5 noix. Lorsque les écrous deviennent <2000, et cela se produit après 200 m de mouvement, l'algorithme sera le suivant:

Ramassez les joues pleines de noix et marchez 1 m
Déchargez 998 noix (1 mangé en chemin, 1 à gauche pour revenir en arrière)
Remontez de 1 m vers le stock de noix
Prenez le dernier millier et avancez 1 m plus loin

Un déplacement de 1 m coûte 3 noix à un hamster. Lorsqu'il atteindra le point des 534 m, un total de 2001 noix sera mangé, et le hamster devra prendre les 999 dernières noix et parcourir calmement les 466 mètres restants dans son trou. Quand il y arrivera, 533 noix resteront dans les joues - ce sera la réponse au problème.

Je tiens à noter que les tâches de cette classe sont assez populaires dans la théorie des algorithmes, ainsi que dans les entretiens dans les grandes entreprises. La meilleure façon d'apprendre à les résoudre est la pratique. Il n'y a pas de mécanisme unique pour le résoudre (enfin, ou il est passé devant moi), mais il est tout à fait possible de mettre la main sur eux et de développer une pensée créative.

Tâche 3. Distribution analytique

La tâche

Yandex veut créer

M

$M$ équipes d'analystes. Lors de l'embauche, chaque analyste choisit au hasard un groupe pour lui où il travaillera. Le chef d'équipe veut déterminer quel nombre minimum de milliers d'analystes est suffisant pour embaucher afin que son groupe soit plus probable

P

$P$ n'était pas moins

N

$N$ la personne?

Vous devez écrire un programme Python qui accepte

N

$N$ ,

M

$M$ et

P

$P$ en une seule ligne, et la sortie donne le nombre de milliers d'analystes.

1 \leq N \leq 100

$1 \leq N \leq 100$ ,

1 \leq M \leq 100000

$1 \leq M \leq 100000$ ,

0 \leq P \leq 1

$0 \leq P \leq 1$

Décision

Eh bien, la connaissance des statistiques, à savoir la distribution binomiale , a été très utile . Nous désignons le nombre d'analystes embauchés par Yandex pour

X

$X$ . Chacun des analystes embauchés choisit une équipe. Du point de vue de notre chef d'équipe, l'embauche d'un analyste pour le travail est une expérience avec deux résultats: un nouveau venu fait partie de notre équipe ou non. La probabilité de coup égale

\frac{1}{M}

$\frac{1}{M}$ , la probabilité que l'analyste choisisse un autre groupe, respectivement, est

\frac{M - 1}{M}

$\frac{M-1}{M}$ . Au total, de telles expériences avec le choix de l'équipe seront

X

$X$ . Le nombre de hits dans notre équipe

n

$n$ de

X

$X$ l'élection des analystes est répartie binomialement, la fonction de répartition est égale à:

P (n ⩽ N) = \sum_{k = 0}^{N} (\binom{X}{k}) (\frac{1}{M})^{k} (\frac{M - 1}{M})^{X - k}

$\mathbb{P}(n \leqslant N) = \sum\limits_{k=0}^{ N} \binom{X}{k}\, \biggl(\frac{1}{M}\biggr)^k \biggl(\frac{M-1}{M}\biggr)^{X-k}$

Cette fonction montre la probabilité que le nombre de hits soit inférieur ou égal à la valeur spécifiée

N

$N$ . Nous sommes intéressés par la probabilité que le nombre de hits soit supérieur ou égal à celui donné, donc la tâche ressemble à ceci:

X : 1 - P_{x} (n ⩽ N) = P; X - ?

$X: 1 - \mathbb{P_x}(n \leqslant N) = P; X-?$

Autrement dit, vous devez trouver le nombre d'analystes embauchés

X

$X$ à laquelle l'équipe obtient au moins

N

$N$ personne pour une probabilité donnée

P

$P$ .

Eh bien, nous avons compris les mathématiques - comment les trouver maintenant

X

$X$ ? Busting. Vous pouvez écrire un cycle qui triera le nombre d'analystes embauchés, en l'augmentant jusqu'à ce que la probabilité d'obtenir au moins

N

$N$ les analystes ne seront pas satisfaisants.

Le 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)) #

Tâche 4. Recherche de cadeaux

La tâche

Le Père Noël a apporté 100 cadeaux Anastasia et les a placés sous le sapin de Noël. L'arbre est grand et moelleux, il est donc difficile de naviguer sous Anastasia. Anastasia examine les cadeaux de cette façon: tend accidentellement du côté aléatoire de l'arbre vers une plage aléatoire, prend un cadeau, l'examine et le remet en place. Il s'avère que chaque fois qu'Anastasia peut également prendre n'importe quel cadeau de ceux qui se trouvent sous l'arbre. Trouver l'attente de la part de cadeaux qu'Anastasia considérera pour 100 étirements aléatoires?

Décision

À première vue, la tâche semble très simple, même la confiance semble qu'une solution peut être trouvée par une formule élémentaire, mais tout n'est pas si simple. Pas si simple. J'ai passé indécemment beaucoup de temps sur cette tâche, essayant de peindre des options et de dériver une formule, mais je n'ai pas réussi. Ensuite, je suis allé sur Google et, à ma grande surprise, j'ai dû creuser profondément dans les forums, avant de trouver une solution pour le cas général . Donc, si nous sélectionnons au hasard des éléments d'un ensemble avec un retour, la probabilité est

n

$n$ sélections de

m

$m$ les éléments de l'ensemble se retirent exactement

k

$k$ différents égaux:

P (m, k, n) = \frac{(\binom{m}{k}) \cdot k! \cdot S_{2} (n, k)}{m^{n}}

$P(m, k, n) = \frac{\binom{m}{k}\cdot k! \cdot S_2(n, k)}{m^n}$

Où

S_{2}

$S_2$ il y a un nombre Stirling du deuxième type - le nombre de partitions non ordonnées de l'ensemble de

n

$n$ articles sur

k

$k$ sous-ensembles non vides. Eh bien, pour trouver l'attente, il faut additionner les probabilités calculées par cette formule pour chaque fraction possible des dons uniques examinés - du centième à un tout. Cela peut être fait en utilisant une boucle en Python.

Le 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)) #

Tâche 5. Voyageur équiprobable

La tâche

Le voyageur commence à se déplacer le long des bords d'une grille à deux dimensions avec des nœuds entiers strictement vers la droite ou vers le haut. Il bouge d'un point

(0, 0)

$(0, 0)$ exactement

(100, 100)

$(100, 100)$ . Quelle est la probabilité de traverser une rivière en ligne droite reliant les points de départ et d'arrivée, si l'on considère que tous les itinéraires possibles sont également probables? On pense que le voyageur a traversé la rivière s'il était sur la même route strictement au-dessus et en dessous de la rivière. Une entrée de rivière n'est pas considérée comme une intersection.

Décision

Nous trouvons la probabilité de traverser l'approche classique - nous divisons le nombre de routes avec intersection par le nombre total de routes possibles. Laisser être

n

$n$ - la longueur des bords de la grille carrée. Puis le nombre total d'itinéraires possibles:

N = \frac{(2 n!)}{(n!)^{2}}

$N = \frac{(2n!)}{(n!)^2}$

La dérivation de la formule est décrite ici . Mais comment connaître le nombre d'itinéraires de traversée de rivière pour chacun

n

$n$ ? Ayant été intrigué par cette question, j'ai décidé de prendre quelques longueurs de grille plus petites, de dessiner des champs et de calculer manuellement le nombre d'itinéraires traversant la rivière, dans l'espoir de tracer la dépendance (je vous recommande vivement de prendre également un morceau de papier et un stylo maintenant et d'expérimenter avec le dessin de petites grilles et de chemins).

Soit une grille de taille 3 par 3 cellules. La diagonale latérale de la grille est occupée par la rivière, le voyageur est dans le coin inférieur gauche.

Image

, ,

Dès que j'ai fait le dessin, j'ai réalisé qu'il serait beaucoup plus facile de suivre les routes que la rivière ne traverse pas, à savoir les routes en dessous de la rivière. Il sera alors possible de multiplier leur nombre par 2, prenant ainsi en compte les trajets miroirs au dessus de la rivière. Puisque nous connaissons également le nombre total de routes, nous trouvons le nombre de personnes traversant la rivière. Mais revenons à la tâche principale - nous avons besoin d'une relation entre

n

$n$ et le nombre de chemins de traversée de rivière.

Dans la figure ci-dessus pour le cas de 3x3, j'ai marqué en bleu quelques itinéraires «terrestres» accessibles au voyageur: les itinéraires marqués passent le long des bords des cellules avec une coordonnée horizontale de 2, le voyageur n'entre pas auparavant dans les bords gauche et supérieur des cellules. Il existe 3 itinéraires de ce type, à savoir

n

$n$ . Voyons maintenant les itinéraires qui traversent la cellule de la colonne 1.

Image

J'ai marqué les nouveaux chemins en rouge. Donc, il est clair que si un voyageur se tourne vers la gauche puis le bord supérieur de la cellule (1, 0), alors seulement 2 des trois chemins à travers les cellules avec une coordonnée horizontale de 2 lui seront accessibles, car vous ne pouvez que vous déplacer vers le haut et vers la droite - le troisième chemin est plus bas . Ainsi, en ajoutant une nouvelle cellule de la colonne 1 à la route, nous avons augmenté le nombre total de chemins par le nombre de routes qui traversent les cellules de la colonne 2 qui ne sont pas inférieures à notre nouvelle cellule.

Prenez une grille de 4 x 4 et continuez à démêler l'enchevêtrement. Il est devenu clair que l' ajout d'une nouvelle cellule à une colonne augmente le nombre de chemins par le nombre de routes qui traversent la colonne suivante pas plus bas que le bord supérieur de la cellule ajoutée. Je ne marquerai pas les itinéraires avec de la couleur, je me limiterai à une description textuelle, mais si vous le jugez nécessaire, dessinez - dans le processus de résolution, j'ai dessiné une douzaine de grilles différentes avant de réussir à ressentir la dépendance en toute confiance.

Image

La colonne la plus à droite nous donne à nouveau

n

$n$ itinéraires. Le bord supérieur de la cellule (2, 0) nous ajoutera

n - 1

$n-1$ route. Le bord supérieur de la cellule (2, 1) ajoutera

n - 2

$n-2$ route. Le bord supérieur de la cellule (1, 0) ajoutera autant de routes que les cellules (2, 0) et (2, 1) se sont ajoutées. Si vous le souhaitez, vous pouvez dessiner une grille plus grande et continuer à considérer les itinéraires avec le même algorithme. Notre tâche consiste à calculer les itinéraires pour une grille 100x100. Pour ce faire, vous pouvez écrire un programme qui acceptera l'entrée

n

$n$ et construire une matrice

n \times n

$n\times n$ à partir de la colonne

n

$n$ puis pour chaque cellule des colonnes précédentes, en comptant le nombre de chemins ajoutés par la cellule en fonction des données de la colonne précédente. Ainsi, le nombre de chemins de traversée non fluviaux sera trouvé.

Le 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))

Tâche 6. État de la distribution linéaire

La tâche

L'État de distribution linéaire est une multitude de villes, dont certaines sont reliées par des routes.

Une fois que le roi de l'État a pris conscience que le peuple des points d'arrêt allait envahir ses frontières. Étant donné que l'État n'était pas prêt à se défendre, le roi a pris une décision difficile - diviser l'État en plusieurs petits États, dont chacun défendra indépendamment ses frontières.

Il a été décidé que deux villes peuvent et devraient être laissées dans un même État s'il est possible de se rendre dans la seconde depuis une ville, même si les habitants des points d'arrêt saisissent une route entre deux villes de l'État de distribution linéaire. Dans tous les autres cas, les villes doivent être dans des états différents.

Sur chaque route qui traversera la frontière de deux nouveaux États, il est nécessaire de mettre un bastion. Cela est nécessaire dans le cas où l'un de ces états est capturé par le peuple des points d'arrêt. Ensuite, le second pourra continuer à défendre ses frontières. En d'autres termes, le bastion sera mis sur la route qui relie les villes de différents états.

Le roi vous a demandé de lui donner une liste de routes sur lesquelles vous devez placer des bastions.

Format d'entrée et de sortie du programme

n

$n$

m

$m$ — .

(1 \leq n \leq 20000, 1 \leq m \leq 200000)

$(1 \leq n \leq 20000, 1 \leq m \leq 200000)$ . m . i

b_{i}, e_{i}

$b_i, e_i$ — ,

(1 \leq b_{i}, e_{i} \leq n)

$(1 \leq b_i, e_i \leq n)$

b — , . b — , , . , .

, , , , — .

Décision

Et voici le problème de la théorie des graphes. Pour de longues histoires sur le sort de l'État de la distribution linéaire, les rédacteurs ont dissimulé la tâche plutôt intéressante de trouver des ponts dans un graphique dont les nœuds sont des villes et les bords sont des routes. En bref, un pont est un tel bord d'un graphe, dont la suppression coupera une certaine partie de ce graphe d'autres sommets. C'est l'idée de capturer la route - si le pont est capturé, la communication entre certaines villes sera rompue, sinon il y aura toujours une route alternative entre les villes, donc ce sont les ponts que les États divisent, il faut mettre des bastions sur les ponts.

Algorithme de recherche de pont basé sur la recherche en profondeur(Recherche en profondeur d'abord, DFS) - une méthode de parcours de graphe dans laquelle toutes les arêtes provenant du sommet initial sont examinées, et si l'arête mène à un sommet qui n'a pas encore été pris en compte, l'algorithme démarre immédiatement récursivement à partir de ce sommet. Le fait suivant aidera dans la recherche de ponts:

Cherchons en profondeur, en cherchant maintenant toutes les arêtes du sommet V. Alors si l'arête courante (V, U) est telle qu'à partir du sommet U et de l'un de ses descendants dans l'arbre de parcours, il n'y a pas d'inverse chemin vers le sommet de V ou l'un de ses ancêtres, le bord considéré est un pont.

Afin d'apprendre à vérifier ce fait pour le sommet V, nous introduisons le temps d'entrée dans le disque de sommet [V](de l'anglais. découvert). Dans cette variable, l'étape de l'algorithme à laquelle le sommet a été traité sera enregistrée. De plus, avec chaque sommet V, la variable [V] la plus basse sera associée , dans laquelle nous écrivons l'heure d'entrée du premier sommet U, qui peut être atteinte à partir du sommet V. Pendant le traitement initial du sommet le plus bas [V] = disque [V] (Au sommet plus tôt que vous ne comprenez pas), mais plus tard dans le processus de recherche en profondeur, nous pouvons trouver un fils V, dont l'un des bords mène à l'ancêtre de V (appelons-le S). Dans ce cas, nous mettrons à jour le plus bas [V]: le plus bas [V] = disque [S]. Et quand pouvons-nous accrocher le pont? Ensuite, lorsque nous cherchons en profondeur, nous atteignons le sommet, qui n'a pas de fils qui n'ont pas encore été considérés (encore une fois, nous l'appelons U). Dans ce cas, nous vérifierons quel sommet le plus tôt peut être atteint à partir de U, et si ce sommet se produit plus tard que le parent immédiat de U (cela est possible, par exemple, lorsque U n'a pas de fils, alors le plus bas [U] = disque [U ] ), alors la connexion de U avec le parent est un pont.

Le code de l'algorithme implémenté avec commentaires est joint ci-dessous. Il convient de ne pas créer de variables distinctes pour le disque et le plus bas de chaque sommet, mais de placer des tableaux pour chaque valeur, où l'index est le numéro du sommet auquel appartient la valeur.

Le 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)

La source suivante m'a aidé à résoudre le problème de plusieurs façons , donc je considère qu'il est nécessaire de lui laisser un lien. Cela vaut la peine d'être regardé et voici cette vidéo - il y a une bonne animation de l'algorithme.

Conclusion

Telles sont les tâches qu'un spécialiste postulant pour un stage chez Yandex devrait résoudre en toute confiance. L'ensemble des tâches ci-dessus a été donné 5 heures - un temps assez court, à mon avis, mais chacun travaille à son propre rythme.

Mes décisions ont été testées et donnent les bonnes réponses, mais je ne doute pas qu'il existe des moyens plus efficaces de faire face aux tâches proposées. Si vous êtes prêt à proposer une solution plus rapide ou plus compréhensible ou si vous trouvez une erreur avec moi, n'hésitez pas à écrire à ce sujet.

Je souhaite à chacun de trouver un poste pour lui-même!

Stage d'analyste à Yandex: analyse des tâches de test

Tâche 1. Date limite

La tâche

Décision

Tâche 2. Le sort du hamster

La tâche

Décision

Tâche 3. Distribution analytique

La tâche

Décision

Tâche 4. Recherche de cadeaux

La tâche

Décision

Tâche 5. Voyageur équiprobable

La tâche

Décision

Tâche 6. État de la distribution linéaire

La tâche

Décision

Conclusion

More articles: