HackerRank Probability – Dice Stats – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

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

Cerinta

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, \ldots, 6$. However, it is *biased*. In each throw, the probability of $i$ appearing is $p_i$ for $i = 1, 2, \ldots 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 $i$th line contains $p_i$, for $i = 1, 2, \ldots 6$.  
The seventh (and final) line contains $N$, the number of times the die is thrown.  

**Constraints**  
$0.1 \leq p_i \leq 0.2$  
$p_1 + p_2 + \ldots + p_6 = 1$  

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

Output Format

The first line of output contains the expected value. <br>
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 sursa

#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