Soluție HackerRank pentru Dice Stats, subdomeniul Probability, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Dice Stats
  • Domeniu: Probability
  • Limbaj: C++14

Challenge: Dice Stats

Subdomeniu: Probability (probability)

Scor cont: 60.0 / 60

Submission status: Accepted

Submission score: 1.0

Submission ID: 464756122

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/dice-stats/problem

Cerință

The [expected value](https://en.wikipedia.org/wiki/Expected_value) is the weighted average of all possible outcomes of an experiment, weighted with the probabilities of each particular outcome. For a [random variable](https://en.wikipedia.org/wiki/Random_variable) X, the expected value is written as E[X].

Intuitively, the expected value is the long run average value of repetitions of the experiment.

The [variance](https://en.wikipedia.org/wiki/Variance) is the expected value of the outcome's squared deviation from its expected value. For a random variable X, the variance is written as text{Var}[X] and is defined as the expected value of (X - E[X])^2.

Intuitively, the variance is a measure of how far the outcomes of an experiment are spread out. The higher the variance, the more spread out the outcomes.

Let's say we perform the following experiment involving throwing a [die](https://en.wikipedia.org/wiki/Dice):

Throw the die, and record the outcome as d[1].

For i from 2 to N:
Repeatedly throw the die until the outcome is different from d[i-1].
Record the outcome as d[i].

Output d[1] + d[2] + ... + d[N].

The die used in this experiment is a standard 6-sided die with outcomes 1, 2, …, 6. However, it is *biased*. In each throw, the probability of i appearing is p_i for i = 1, 2, … 6.

Find the expected value and variance of the outcome of this experiment.

*Note:* Certain formulas for variance are not fit for computation because of [loss of significance](https://en.wikipedia.org/wiki/Loss_of_significance)/[numerical instability](https://en.wikipedia.org/wiki/Numerical_stability). [This link](https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Na.C3.AFve_algorithm) contains a discussion about how to avoid/mitigate this problem.

Input Format

The first six lines contain the probabilities of the die's outcomes. Specifically, the ith line contains p_i, for i = 1, 2, … 6.
The seventh (and final) line contains N, the number of times the die is thrown.

Constraints
0.1 ≤ p_i ≤ 0.2
p_1 + p_2 + … + p_6 = 1

For test cases worth 25% of the total points: 1 ≤ N ≤ 8
For test cases worth 25% of the total points: 1 ≤ N ≤ 3000
For test cases worth 50% of the total points: 1 ≤ N ≤ 100000

Output Format

The first line of output contains the expected value.

The second line contains the variance.

The answer will be accepted if it is within an absolute error of 10^-5 of the true answer.

Cod sursă

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

struct Dist {
    long double w = 0.0L;   // total probability mass
    long double mean = 0.0L;
    long double m2 = 0.0L;  // weighted second central moment (w * variance)
};

static inline void mergeDist(Dist &a, long double w, long double mean, long double m2) {
    if (w <= 0.0L) return;
    if (a.w <= 0.0L) {
        a.w = w;
        a.mean = mean;
        a.m2 = m2;
        return;
    }
    long double newW = a.w + w;
    long double delta = mean - a.mean;
    long double newMean = a.mean + delta * (w / newW);
    long double newM2 = a.m2 + m2 + delta * delta * (a.w * w / newW);

    a.w = newW;
    a.mean = newMean;
    a.m2 = newM2;
}

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

    vector<long double> p(6);
    for (int i = 0; i < 6; ++i) cin >> p[i];
    long long N;
    cin >> N;

    long double ps = 0.0L;
    for (auto x : p) ps += x;
    if (ps > 0) {
        for (auto &x : p) x /= ps;
    }

    long double trans[6][6];
    for (int a = 0; a < 6; ++a) {
        long double den = 1.0L - p[a];
        for (int b = 0; b < 6; ++b) {
            trans[a][b] = (a == b ? 0.0L : p[b] / den);
        }
    }

    vector<Dist> cur(6), nxt(6);

    // Step 1: S = face value.
    for (int x = 0; x < 6; ++x) {
        cur[x].w = p[x];
        cur[x].mean = (long double)(x + 1);
        cur[x].m2 = 0.0L;
    }

    for (long long step = 2; step <= N; ++step) {
        for (int y = 0; y < 6; ++y) nxt[y] = Dist{};

        for (int prev = 0; prev < 6; ++prev) {
            if (cur[prev].w <= 0.0L) continue;
            long double varPrev = cur[prev].m2 / cur[prev].w;
            for (int y = 0; y < 6; ++y) {
                if (y == prev) continue;
                long double t = trans[prev][y];
                long double wComp = cur[prev].w * t;
                if (wComp <= 0.0L) continue;

                long double meanComp = cur[prev].mean + (long double)(y + 1);
                long double m2Comp = wComp * varPrev; // adding a constant does not change variance
                mergeDist(nxt[y], wComp, meanComp, m2Comp);
            }
        }

        cur.swap(nxt);
    }

    Dist all;
    for (int x = 0; x < 6; ++x) {
        mergeDist(all, cur[x].w, cur[x].mean, cur[x].m2);
    }

    long double expected = all.mean;
    long double variance = (all.w > 0.0L ? all.m2 / all.w : 0.0L);
    if (variance < 0.0L && fabsl(variance) < 1e-14L) variance = 0.0L;

    cout.setf(std::ios::fixed);
    cout << setprecision(15) << expected << '\n';
    cout << setprecision(15) << variance << '\n';
    return 0;
}
HackerRank Probability – Dice Stats