Hackerrank головоломка. Сколько ребер необходимо для случайного графа подключиться

Это головоломка Interviewstreet:

У нас есть страна, в которой есть N городов. Каждый день мы выбираем 2 города, чтобы между ними не было дороги и строили дорогу между ними. Выбираем каждую пару несмежных городов с равной вероятностью. Пусть X - число дней, прежде чем мы получим связанную страну. Каково ожидаемое значение X? Выведите целочисленную часть ответа.

То, что они действительно задают, - это то, какое число ребер m необходимо (в среднем) для случайного графа G (n, m), чтобы подключиться.

После написания программы, которая фактически выполнила эксперимент, я придумал это "решение", которое проходит 9/10 тестов

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

Так может ли это быть разрешено с помощью одной формулы? Каков правильный способ нахождения вероятности связности случайного графа?

Ответы

Ответ 1

Вы должны проверить классическую статью Эрдоса и Реньи от 1960 года под названием "Об эволюции случайных графов" . Он содержит полные вероятностные оценки количества компонентов, размер наибольших компонентов и т.д.

Вот немного математической настройки, чтобы вы начали.

Пусть G(n,m) - простой случайный граф на вершинах n с ребрами m. Пусть X_k - количество добавленных ребер, в то время как есть k связанные компоненты, пока не будет k-1 связанных компонентов. Например, изначально есть n связанные компоненты, поэтому добавление первого ребра приводит к n-1 компонентам связи, поэтому X_n = 1. Аналогично, второе ребро также удаляет компонент (хотя это происходит одним из двух способов), поэтому X_n-1 = 1. Определение

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

Цель состоит в том, чтобы вычислить E(X), ожидаемое значение X. По аддитивности имеем

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

Не слишком сложно показать, что вероятность добавления ребра при наличии компонентов k уменьшает количество компонентов, имеет нижнюю границу (k-1)/(n-1). Так как X_k - случайная величина с вероятностью успеха, заданная этой величиной, нижняя граница дает оценку сверху для ожидания X_k:

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

Объединяя это, получаем асимптотическую верхнюю оценку для E(X) через n log n.

С немного дополнительной работой и некоторыми подсказками из бумаги Erdos-Renyi вы можете, вероятно, вывести точную формулу.

Ответ 2

OP - отличное решение и с небольшой модификацией формулы всегда будет проходить.

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