HackerRank Probability – Connect the country

Challenge: Connect the country

Subdomeniu: Probability (probability)

Scor cont: 60.0 / 60

Submission status: Accepted

Submission score: 1.0

Submission ID: 464755747

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/connect-the-country/problem

Cerinta

We have a country containing _N _cities. Each day we choose 2 cities such that there is no road between them and build a road between them. We choose each pair of nonadjacent cities with equal probability. Let X be the number of days before we obtain a connected country. What is the expected value of X? Output the integer part of answer.

Input Format

First line of input as an integer N.

Output Format

Print an integer being the result of the test.

Constraints

+ $N <= 30$

Cod sursa

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    int maxM = N * (N - 1) / 2;

    // Binomial coefficients up to C(maxM, *), stored as long double.
    vector<vector<long double>> C(maxM + 1, vector<long double>(maxM + 1, 0.0L));
    for (int i = 0; i <= maxM; ++i) {
        C[i][0] = C[i][i] = 1.0L;
        for (int j = 1; j < i; ++j) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }

    vector<int> M(N + 1, 0);
    for (int n = 0; n <= N; ++n) M[n] = n * (n - 1) / 2;

    // conn[n][m] = number of connected labeled graphs with n vertices and m edges.
    vector<vector<long double>> conn(N + 1);
    for (int n = 0; n <= N; ++n) conn[n].assign(M[n] + 1, 0.0L);
    conn[1][0] = 1.0L;

    for (int n = 2; n <= N; ++n) {
        int Mn = M[n];
        for (int m = 0; m <= Mn; ++m) {
            long double val = C[Mn][m]; // all graphs with n vertices and m edges

            // Subtract disconnected graphs by fixing component containing vertex 1.
            for (int k = 1; k <= n - 1; ++k) {
                long double pick = C[n - 1][k - 1];
                int Mk = M[k];
                int Mr = M[n - k];

                int eL = max(0, m - Mr);
                int eR = min(m, Mk);
                if (eL > eR) continue;

                long double sum = 0.0L;
                for (int e = eL; e <= eR; ++e) {
                    sum += conn[k][e] * C[Mr][m - e];
                }
                val -= pick * sum;
            }

            if (val < 0.0L && fabsl(val) < 1e-12L) val = 0.0L;
            conn[n][m] = val;
        }
    }

    int Mn = M[N];
    long double expected = 0.0L;
    for (int m = 0; m < Mn; ++m) {
        long double pConnected = conn[N][m] / C[Mn][m];
        if (pConnected < 0.0L) pConnected = 0.0L;
        if (pConnected > 1.0L) pConnected = 1.0L;
        expected += (1.0L - pConnected);
    }

    long long ans = (long long)floor(expected + 1e-12L);
    cout << ans << '\n';
    return 0;
}