Halo, Habr!

Suatu kali, setelah mempelajari buku lain tentang Ilmu Data yang terkenal, saya sampai pada kesimpulan bahwa sudah waktunya untuk menerapkan pengetahuan yang terakumulasi ke dalam praktik dan melihat kehidupan departemen analitik dengan mata kepala saya sendiri. Untungnya, Yandex meluncurkan pilihan untuk magang enam bulan ke arah yang sesuai, dan saya tidak bisa lewat. Penerimaan aplikasi 2020 telah berakhir, jadi dalam artikel ini saya akan, dengan hati nurani yang jelas, menganalisis tugas-tugas yang diusulkan Yandex untuk diselesaikan bagi pelamar pada tahap pertama. Akan ada kode Python. Spoiler: sulit, tetapi menarik.

Tugas 1. Batas waktu

Tugas

Analis pemula sedang mencoba untuk memecahkan masalah. Jika masalah tidak dapat diselesaikan, maka ia kehilangan motivasi, dan probabilitas keberhasilan pada upaya berikutnya jatuh. Satu upaya membutuhkan waktu sehari, dan batas waktu tugas adalah 90 hari. Probabilitas bahwa analis akan menyelesaikan masalah dari upaya ke-i adalah:

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

Seberapa besar kemungkinan analis menyelesaikan masalah sebelum batas waktu?

Keputusan

Anda mungkin sudah menghubungi untuk mengetik: "@nice_one, Anda bilang itu akan sulit, tapi apa ini?" Sabar, teman-teman, ini adalah tugas sederhana untuk pemanasan, tetapi ada sesuatu yang terlewatkan jika Anda tidak memikirkan kondisinya. Mari kita periksa contoh paragraf pertama. Penting untuk menghitung probabilitas total bahwa analis akan menyelesaikan masalah dalam 90 hari yang tersedia di cadangan, sementara probabilitas keberhasilan pada setiap hari ke-i diberikan. Opsi yang menggoda mungkin tampak menggantikan dalam ekspresi angka dari 1 hingga 90, bukan i dan menambahkan, tetapi ini tidak benar. Ungkapan ini menunjukkan kemungkinan keberhasilan pada hari-hari tertentu, tetapi untuk mencapai hari-hari itu, analis harus gagal di hari-hari sebelumnya (1 - 1). Jika probabilitas keberhasilan pada hari ke-i adalah

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

$\frac{1}{(i+1)}$ , maka probabilitas kegagalan pada hari ini sama dengan

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

$1 - \frac{1}{(i+1)} = \frac{i}{i+1}$ . Seperti yang Anda ketahui, untuk menemukan probabilitas kemunculan simultan dari beberapa peristiwa, perlu untuk mengalikan probabilitas dari setiap kejadian. Dengan demikian, probabilitas bahwa analis dapat mengatasinya dalam n hari adalah

(\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}$ .

Anggota yang berdiri di bawah tanda pekerjaan bertanggung jawab atas kegagalan di masing-masing yang pertama

(n - 1)

$(n - 1)$ hari, maka Anda perlu melipatgandakan produk dengan probabilitas keberhasilan pada hari ke-n.
Jadi, untuk beberapa hari, kami tahu probabilitas keberhasilan untuk periode ini. Kami tertarik pada probabilitas total keberhasilan untuk setiap periode yang memungkinkan hingga 90 hari inklusif. Sekarang Anda dapat mengganti angka dari 1 hingga 90, tetapi sudah dalam rumus yang dihasilkan. Cara termudah adalah dengan menulis loop dalam beberapa python yang akan menghitung dan menambahkan probabilitas, yang saya lakukan.

Kode

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)

Keputusan paragraf kedua benar-benar mirip dengan yang pertama, hanya rumusnya yang berbeda. Saya akan meninggalkan kode memecahkan poin kedua - saya pikir semuanya akan jelas.

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

Tugas 2. Nasib hamster

Tugas

Untuk bertahan hidup di musim dingin, hamster lapar yang rakus memutuskan untuk merampok pabrik kacang yang terletak 1000 meter dari lubangnya. Ada 3.000 kacang yang tersisa di pabrik. Maksimal 1000 kacang diletakkan di pipi hamster. Di mana-mana dan apa pun hamster berjalan, setiap meter ia harus diperkuat dengan 1 kacang. Hamster sudah ada di pabrik dan berbahaya. Berapa jumlah maksimum kacang yang bisa dia persediaan? Jawabannya harus dibulatkan ke bilangan bulat terdekat.

Keputusan

Sangat mengingatkan pada tugas sebuah jip, Bukankah demikian? Jadi, sebelum kita adalah varietas berikutnya. Dalam kasus umum, kendaraan (dalam hal ini, hamster) muncul dalam masalah jip, yang perlu menempuh jarak tertentu dalam kondisi kapasitas terbatas dari wadah bahan bakar (pipi hamster). Gagasan yang mendasari solusi untuk setiap masalah kelas ini - di sepanjang jalan, Anda dapat meninggalkan pasokan bahan bakar, serta kembali untuk yang baru. Kalau tidak, algoritma solusi tunggal tidak ada, karena kondisi dan tujuan awal bisa sangat berbeda. Opsi yang diusulkan di sini menarik karena perlu tidak hanya menempuh jarak dari pabrik ke lubang (yang sifatnya elementer, karena hamster dapat memegang tepat 1000 kacang, yang cukup untuk 1000 meter), tetapi juga mentransfer kacang sebanyak mungkin. Yang terbaik untuk menggambar diagram,menggambarkan panjang 1000 m dan stok kacang di pabrik, dan berpikir tentang bagaimana bertindak hamster jika dia ingin mengangkut 3.000 kacang ke dalam lubang, makan sesedikit mungkin, mis., telah melewati sesedikit mungkin jarak total. Mari kita coba bergerak pada langkah terkecil, masing-masing 1 m, mentransfer semua 3.000 kacang bersamamu dalam beberapa perjalanan.

Jelas, untuk memindahkan 3000 kacang ke titik mana pun, hamster harus kembali ke yang sebelumnya setidaknya 3 kali. Ketika 2000 kacang tersisa dan sisanya dimakan di sepanjang jalan, hamster akan membutuhkan 2 perjalanan ke titik sebelumnya untuk memindahkannya ke yang baru. Saat bahan bakar kurang dari 1000 unit, Anda tidak harus kembali, semuanya cocok di pipi hamster. Dengan demikian, proses mentransfer kacang dapat dibagi menjadi tiga tahap yang sesuai. Mari kita lihat apa yang akan dimiliki "konsumsi bahan bakar" masing-masing hamster. Ketika ada lebih dari 2.000 kacang, untuk bergerak 1 meter hamster harus:

Angkat pipi penuh kacang dan berjalan 1 m
Bongkar 998 kacang (1 makan di jalan, 1 tersisa untuk kembali)
Kembali 1 m lagi ke stok kacang
Ulangi langkah 1-3 untuk seribu kacang kedua
Ambil seribu terakhir dan lanjutkan 1 m ke depan

Dengan demikian, perpindahan 1 m dengan semua mangsa membutuhkan biaya hamster 5 kacang. Ketika mur menjadi <2000, dan ini terjadi setelah 200 m gerakan, algoritme akan sebagai berikut:

Angkat pipi penuh kacang dan berjalan 1 m
Bongkar 998 kacang (1 makan di jalan, 1 tersisa untuk kembali)
Kembali 1 m lagi ke stok kacang
Ambil seribu terakhir dan lanjutkan 1 m ke depan

Pemindahan 1 m membutuhkan biaya hamster 3 kacang. Ketika ia mencapai titik 534 m, total kacang 2001 akan dimakan, dan hamster harus mengambil 999 kacang terakhir dan dengan tenang memasukkan 466 meter sisanya ke dalam lubangnya. Ketika dia sampai di sana, 533 kacang akan tetap ada di pipi - ini akan menjadi jawaban untuk masalahnya.

Saya ingin mencatat bahwa tugas-tugas kelas ini cukup populer dalam teori algoritma, serta dalam wawancara di perusahaan besar. Cara terbaik untuk belajar bagaimana menyelesaikannya adalah berlatih. Tidak ada mekanisme tunggal untuk menyelesaikannya (yah, atau dia berenang melewatiku), tetapi sangat mungkin untuk membantu mereka dan mengembangkan pemikiran kreatif.

Tugas 3. Distribusi analitis

Tugas

Yandex ingin membuat

M

$M$ tim analis. Saat merekrut, setiap analis secara acak memilih grup untuk dirinya sendiri di mana ia akan bekerja. Pemimpin tim ingin mengetahui jumlah minimum dari ribuan analis yang cukup untuk disewa sehingga kelompoknya lebih mungkin

P

$P$ tidak kurang

N

$N$ orang?

Anda harus menulis program Python yang menerima

N

$N$ ,

M

$M$ dan

P

$P$ dalam satu baris, dan output memberikan jumlah ribuan analis.

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$

Keputusan

Nah, pengetahuan statistik, yaitu distribusi binomial , berguna . Kami menunjukkan jumlah analis yang disewa oleh Yandex untuk

X

$X$ . Masing-masing analis yang direkrut memilih tim. Dari sudut pandang pemimpin tim kami, mempekerjakan seorang analis untuk bekerja adalah sebuah eksperimen dengan dua hasil: apakah pendatang baru masuk ke tim kami atau tidak. Probabilitas hit sama dengan

\frac{1}{M}

$\frac{1}{M}$ , probabilitas analis memilih kelompok lain, masing-masing, adalah

\frac{M - 1}{M}

$\frac{M-1}{M}$ . Secara total, percobaan seperti itu dengan pilihan tim akan

X

$X$ . Jumlah hit di tim kami

n

$n$ dari

X

$X$ pemilihan analis didistribusikan secara biner, fungsi distribusi sama dengan:

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}$

Fungsi ini menunjukkan probabilitas bahwa jumlah klik akan kurang dari atau sama dengan yang ditentukan

N

$N$ . Kami tertarik pada kemungkinan bahwa jumlah hit akan lebih besar atau sama dengan yang diberikan, sehingga tugasnya terlihat seperti ini:

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

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

Artinya, Anda perlu menemukan jumlah analis yang direkrut

X

$X$ di mana tim mendapatkan setidaknya

N

$N$ orang untuk probabilitas yang diberikan

P

$P$ .

Yah, kami sudah tahu matematika - bagaimana cara menemukannya sekarang

X

$X$ ? Busting. Anda dapat menulis siklus yang akan memilah-milah jumlah analis yang direkrut, meningkatkannya sampai kemungkinan mendapatkan setidaknya

N

$N$ analis tidak akan memuaskan.

Kode

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

Tugas 4. Penelitian hadiah

Tugas

Santa Claus membawa Anastasia 100 hadiah dan meletakkannya di bawah pohon Natal. Pohon itu besar dan mengembang, sehingga Anastasia sulit dijelajahi di bawahnya. Anastasia memeriksa hadiah dengan cara ini: secara tidak sengaja menjangkau dari sisi pohon secara acak ke kisaran acak, mengambil hadiah, memeriksanya dan mengembalikannya. Ternyata setiap kali Anastasia kemungkinan besar dapat mengambil hadiah apa pun dari mereka yang berbaring di bawah pohon. Temukan harapan pembagian hadiah yang akan dipertimbangkan Anastasia untuk 100 peregangan acak?

Keputusan

Sekilas, tugasnya tampak sangat sederhana, bahkan kepercayaan diri muncul bahwa solusi dapat ditemukan oleh beberapa rumus dasar, tetapi tidak semuanya begitu sederhana. Tidak sesederhana itu. Saya menghabiskan banyak waktu untuk tugas ini, mencoba untuk melukis opsi dan mendapatkan formula, tetapi saya tidak berhasil. Kemudian saya pergi ke Google dan, yang mengejutkan saya, saya harus menggali jauh ke dalam forum, sebelum saya menemukan solusi untuk kasus umum . Jadi, jika kita memilih elemen secara acak dari suatu set dengan return, probabilitasnya adalah

n

$n$ pilihan dari

m

$m$ elemen himpunan menarik tepat

k

$k$ berbeda sama dengan:

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}$

Dimana

S_{2}

$S_2$ ada sejumlah Stirling dari jenis kedua - jumlah partisi unordered dari himpunan

n

$n$ item aktif

k

$k$ himpunan bagian kosong Nah, untuk menemukan harapan, perlu menambahkan probabilitas yang dihitung dengan rumus ini untuk setiap fraksi yang mungkin dari hadiah unik yang diperiksa - dari seperseratus ke satu keseluruhan. Anda bisa melakukan ini menggunakan loop dalam Python.

Kode

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

Tugas 5. Pelancong yang sama

Tugas

Pelancong mulai bergerak di sepanjang tepi grid dua dimensi dengan seluruh node secara ketat ke kanan atau ke atas. Dia bergerak dari satu titik

(0, 0)

$(0, 0)$ persis

(100, 100)

$(100, 100)$ . Seberapa besar kemungkinannya menyeberangi sungai dalam garis lurus yang menghubungkan titik awal dan akhir, jika kita mengasumsikan bahwa semua rute yang mungkin sama kemungkinannya? Diyakini bahwa musafir menyeberangi sungai jika ia berada di rute yang sama persis di atas dan di bawah sungai. Entri sungai tidak dianggap sebagai persimpangan.

Keputusan

Kami menemukan kemungkinan melintasi pendekatan klasik - kami membagi jumlah rute dengan persimpangan dengan jumlah total rute yang mungkin. Biarkan saja

n

$n$ - panjang tepi kotak persegi. Maka jumlah total rute yang mungkin:

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

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

Derivasi formula dijelaskan di sini . Tetapi bagaimana cara mengetahui jumlah rute penyeberangan sungai untuk masing-masing

n

$n$ ? Setelah dibuat bingung oleh pertanyaan ini, saya memutuskan untuk mengambil beberapa panjang kotak yang lebih kecil, menggambar bidang, dan secara manual menghitung berapa rute melintasi sungai, berharap untuk melacak ketergantungan (saya sangat menyarankan Anda juga mengambil selembar kertas dan pena sekarang dan bereksperimen dengan menggambar grid dan jalur kecil).

Biarkan ada kisi ukuran 3 oleh 3 sel. Sisi diagonal dari grid ditempati oleh sungai, pelancong berada di sudut kiri bawah.

Gambar

Gambarnya tidak sempurna, tetapi saya mencoba, jujur

Segera setelah saya membuat gambar, saya menyadari bahwa akan jauh lebih mudah untuk melacak rute yang tidak dilintasi sungai, yaitu rute di bawah sungai. Maka akan mungkin untuk mengalikan angka mereka dengan 2, sehingga dengan mempertimbangkan jalur cermin di atas sungai. Karena kami juga tahu jumlah total rute, kami menemukan jumlah orang yang menyeberangi sungai. Namun kembali ke tugas utama - kita membutuhkan hubungan di antara keduanya

n

$n$ dan jumlah jalur penyeberangan sungai.

Pada gambar di atas untuk kasus 3x3, saya menandai dengan warna biru beberapa rute “darat” yang dapat diakses oleh pelancong: rute yang ditandai melewati tepi sel dengan koordinat 2 horizontal, pelancong tidak memasuki tepi kiri dan atas sel sebelumnya. Ada 3 rute seperti itu, yaitu

n

$n$ . Sekarang mari kita cari tahu rute yang melewati sel di kolom 1.

Gambar

Saya menandai jalur baru dengan warna merah. Jadi, jelas bahwa jika seorang musafir berbelok ke kiri dan kemudian tepi atas sel (1, 0), maka hanya 2 dari tiga jalur melalui sel dengan koordinat horizontal 2 akan dapat diakses olehnya, karena Anda hanya dapat bergerak ke atas dan ke kanan - jalur ketiga terletak lebih rendah . Jadi, dengan menambahkan sel baru dari kolom 1 ke rute, kami meningkatkan jumlah total jalur dengan jumlah rute yang melewati sel-sel kolom 2 yang tidak lebih rendah dari sel baru kami.

Ambil kotak berukuran 4 kali 4 dan lanjutkan mengurai jalinannya. Menjadi jelas bahwa menambahkan sel baru ke kolom meningkatkan jumlah jalur dengan jumlah rute yang melewati kolom berikutnya tidak lebih rendah dari tepi atas sel yang ditambahkan. Saya tidak akan menandai rute dengan warna, saya akan membatasi diri pada deskripsi tekstual, tetapi jika Anda menganggap perlu, menggambar - dalam proses penyelesaian saya menggambar selusin grid yang berbeda sebelum saya berhasil percaya diri merasakan ketergantungan.

Gambar

Kolom paling kanan lagi memberi kita

n

$n$ rute. Tepi atas sel (2, 0) akan menambah kita

n - 1

$n-1$ rute. Tepi atas sel (2, 1) akan ditambahkan

n - 2

$n-2$ rute. Tepi atas sel (1, 0) akan menambahkan rute sebanyak sel (2, 0) dan (2, 1) telah ditambahkan bersama. Jika mau, Anda bisa menggambar kotak yang lebih besar dan terus mempertimbangkan rute dengan algoritma yang sama. Tugas kami adalah menghitung rute untuk kisi 100x100. Untuk melakukan ini, Anda dapat menulis sebuah program yang akan menerima input

n

$n$ dan membangun sebuah matriks

n \times n

$n\times n$ mulai dari kolom

n

$n$ dan kemudian untuk setiap sel dari kolom sebelumnya, menghitung jumlah jalur yang ditambahkan oleh sel berdasarkan data dari kolom sebelumnya. Dengan demikian, jumlah lintasan non-sungai akan ditemukan.

Kode

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

Tugas 6. Keadaan Distribusi Linier

Tugas

Linear Distribution State adalah banyak kota, beberapa di antaranya dihubungkan oleh jalan.

Suatu ketika Raja Negara menyadari bahwa Orang-Orang dari Breakpoints akan menyerbu perbatasannya. Karena Negara tidak siap untuk pertahanan, raja membuat keputusan yang sulit - untuk membagi Negara menjadi banyak yang kecil, yang masing-masing akan secara independen mempertahankan perbatasannya.

Diputuskan bahwa dua kota dapat dan harus dibiarkan dalam satu negara jika memungkinkan untuk mendapatkan yang kedua dari satu kota, bahkan jika People of the Breakpoints merebut satu jalan antara dua kota di setiap Kota Linear Distribution State. Dalam semua kasus lainnya, kota harus berada di negara bagian yang berbeda.

Di setiap jalan yang akan melintasi perbatasan dari dua negara baru, perlu untuk menempatkan benteng. Ini diperlukan jika salah satu dari negara-negara ini ditangkap oleh People of Breakpoints. Kemudian yang kedua akan dapat terus mempertahankan perbatasannya. Dengan kata lain, benteng itu akan diletakkan di jalan yang menghubungkan kota-kota dari berbagai negara.

Raja meminta Anda untuk memberinya daftar jalan tempat Anda harus meletakkan benteng.

Input dan format output program

Masukkan format

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 — , , . , .

, , , , — .

Keputusan

Dan inilah masalah pada teori grafik. Untuk cerita panjang tentang nasib Negara Distribusi Linear, para perancang menyembunyikan tugas yang agak menarik untuk menemukan jembatan dalam grafik yang simpulnya adalah kota dan ujungnya adalah jalan. Secara singkat, sebuah jembatan adalah suatu tepi dari suatu grafik, penghapusan yang akan memotong bagian tertentu dari grafik ini dari simpul lain. Ini adalah ide untuk mengambil jalan - jika jembatan itu direbut, komunikasi antara beberapa kota akan terputus, jika tidak akan selalu ada jalan alternatif antara kota-kota, oleh karena itu jembatan yang dipisah oleh negara bagian, maka perlu untuk menempatkan benteng pada jembatan.

Algoritma Pencarian Jembatan Berdasarkan Pencarian Kedalaman(Pencarian mendalam pertama, DFS) - metode lintasan grafik di mana semua tepi yang berasal dari titik awal diperiksa, dan jika tepi mengarah ke titik yang belum dipertimbangkan, algoritma segera mulai secara rekursif dari titik ini. Fakta berikut akan membantu dalam pencarian jembatan:

Mari kita telusuri lebih dalam, cari sekarang semua tepi dari vertex V. Lalu jika tepi saat ini (V, U) sedemikian rupa sehingga dari vertex U dan dari salah satu turunannya di pohon traversal, tidak ada inversi. jalur ke puncak V atau salah satu leluhurnya, tepi yang dianggap adalah jembatan.

Untuk mempelajari cara memverifikasi fakta ini untuk vertex V, kami memperkenalkan waktu masuk ke dalam vertex disc [V](dari bahasa Inggris. ditemukan). Dalam variabel ini, langkah algoritma tempat simpul telah diproses akan direkam. Juga, dengan setiap titik V, variabel [V] terendah akan dikaitkan , di mana kita menulis waktu masuknya titik paling awal U, yang dapat dicapai dari titik V. Selama pemrosesan awal dari titik terendah [V] = disc [V] (Ke titik lebih awal dari Anda tidak mendapatkan diri Anda sendiri), tetapi kemudian dalam proses pencarian secara mendalam, kami dapat menemukan beberapa putra V, salah satu ujungnya mengarah ke leluhur V (Sebut saja dia S). Dalam hal ini, kami akan memperbarui terendah [V]: terendah [V] = disc [S]. Dan kapan kita bisa menghubungkan jembatan? Kemudian, ketika kami mencari secara mendalam, kami mencapai puncak, yang tidak memiliki putra yang belum dipertimbangkan (Sekali lagi, kami menyebutnya U). Dalam hal ini, kami akan memeriksa titik awal mana yang dapat dicapai dari U, dan jika titik awal ini terjadi lebih lambat dari induk langsung U (Ini dimungkinkan, misalnya, ketika U tidak memiliki anak laki-laki, maka terendah [U] = cakram [U] ] ), maka koneksi U dengan induk adalah jembatan.

Kode algoritma yang diterapkan dengan komentar terlampir di bawah ini. Lebih mudah untuk tidak membuat variabel terpisah untuk disk dan terendah dari setiap titik, tetapi untuk menempatkan array untuk setiap nilai, di mana indeks adalah jumlah titik yang menjadi nilai.

Kode

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)

Berikut sumber membantu saya mengatasi masalah dalam banyak hal , jadi saya menganggap perlu untuk meninggalkan link untuk itu. Layak ditonton dan inilah video ini - ada animasi algoritma yang bagus.

Kesimpulan

Ini adalah tugas yang harus diselesaikan oleh spesialis yang magang di Yandex. Set tugas di atas diberikan 5 jam - waktu yang cukup singkat, menurut saya, tetapi semua orang bekerja dengan kecepatan mereka sendiri.

Keputusan saya telah diuji dan mereka memberikan jawaban yang benar, namun saya tidak ragu bahwa ada cara yang lebih efektif untuk mengatasi tugas yang diusulkan. Jika Anda siap untuk menawarkan solusi yang lebih cepat atau lebih dapat dimengerti atau jika Anda menemukan kesalahan dengan saya, jangan ragu untuk menulis tentang itu.

Saya berharap semua orang menemukan posisi untuk diri mereka sendiri!

Analis magang di Yandex: analisis tugas tes

Tugas 1. Batas waktu

Tugas

Keputusan

Tugas 2. Nasib hamster

Tugas

Keputusan

Tugas 3. Distribusi analitis

Tugas

Keputusan

Tugas 4. Penelitian hadiah

Tugas

Keputusan

Tugas 5. Pelancong yang sama

Tugas

Keputusan

Tugas 6. Keadaan Distribusi Linier

Tugas

Masukkan format

Keputusan

Kesimpulan

More articles: