Hackerrank puzzle. Come molti bordi necessari per un grafo casuale di diventare collegato

Question

Questo è Interviewstreet di puzzle:

Abbiamo un paese che contiene N città. Ogni giorno scegliamo 2 città in modo tale che non ci sia alcuna strada tra loro e costruisca una strada tra di esse. Scegliamo ogni coppia di città non adiacenti con uguale probabilità. Sia X il numero di giorni prima di ottenere un Paese connesso. Qual è il valore atteso di X? Emetti la parte intera della risposta.

Quello che realmente stanno chiedendo è quale numero di lati m è necessario (in media) per un grafico casuale G (n, m) per essere collegato.

Dopo aver scritto un programma che effettivamente eseguita l'esperimento, mi si avvicinò con questa 'soluzione' che passa 9/10 test

$f = fopen('php://stdin', 'r'); 
$n = intval(fgets($f)); 
echo round(1.25 * $n * log($n, 10)); 

Così si può essere risolto con una formula unica? Qual è il modo giusto di trovare la probabilità di connessione di un grafico casuale?

Answer 1

Si dovrebbe controllare il classico documento di Erdos e Renyi dal 1960 intitolato "On the evolution of random graphs". Contiene limiti probabilistici completi per il numero di componenti, la dimensione dei componenti più grandi, ecc.

Ecco un po 'del set up matematico per iniziare.

Lascia il G(n,m) essere il semplice grafico casuale sui vertici n con i bordi m. Lasciare X_k il numero di spigoli aggiunti mentre ci sono componenti connessi k finché non ci sono componenti connessi k-1. Ad esempio, inizialmente ci sono n componenti collegati, quindi aggiungere i primi risultati di bordo nei componenti connessi a n-1 in modo da X_n = 1. Analogamente, il secondo spigolo rimuove anche un componente (sebbene ciò avvenga in uno dei due modi), quindi anche X_n-1 = 1. Definire

X = X_n + X_n-1 + ... + X_2 

L'obiettivo è quello di calcolare E(X), il valore atteso di X. Con l'additività, abbiamo

E(X) = E(X_n) + E(X_n-1) + ... + E(X_2) 

Non è troppo difficile da dimostrare che la probabilità che un vantaggio aggiunto mentre ci sono k componenti riduce il numero di componenti ha un limite inferiore di (k-1)/(n-1). Dal momento che X_k è la variabile casuale con probabilità di successo dato da questo importo, il limite inferiore dà un limite superiore per l'attesa di X_k:

E(X_k) <= (n-1)/(k-1) 

Combinando questo, otteniamo un asintotico limite superiore per E(X) da n log n.

Con un po 'più di lavoro e alcuni suggerimenti dal documento Erdos-Renyi, è possibile dedurre una formula esatta.

Answer 2

L'OP è un'ottima soluzione e con una leggera modifica alla formula, passerà sempre.

$f = fopen('php://stdin', 'r'); 
$n = intval(fgets($f)); 
echo round(1.249 * $n * log($n, 10));// constant factor is changed