DP with Expected Value

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Solve expected steps to reach any sink in a DAG.
5
// Each node u has outgoing edges (u -> v) with probabilities that sum to 1 (if outdegree>0).
6
// Sink nodes have outdegree 0 and E[u] = 0.
7
// For non-sink u: E[u] = 1 + sum_{v} p(u->v) * E[v].
8
9
int main() {
10
    ios::sync_with_stdio(false);
11
    cin.tie(nullptr);
12
13
    int n, m; // n nodes (0..n-1), m directed edges
14
    if (!(cin >> n >> m)) return 0;
15
    vector<vector<pair<int, double>>> adj(n);
16
    vector<int> indeg(n, 0), outdeg(n, 0);
17
    vector<pair<int,int>> edges(m);
18
19
    for (int i = 0; i < m; ++i) {
20
        int u, v; double p;
21
        cin >> u >> v >> p; // edge u->v with probability p
22
        edges[i] = {u, v};
23
        adj[u].push_back({v, p});
24
        indeg[v]++;
25
        outdeg[u]++;
26
    }
27
28
    // Verify DAG via Kahn's algorithm (optional, but good safety for this example)
29
    vector<int> topo;
30
    queue<int> q;
31
    vector<int> indeg_copy(n);
32
    for (int i = 0; i < n; ++i) indeg_copy[i] = indeg[i];
33
    for (int i = 0; i < n; ++i) if (indeg_copy[i] == 0) q.push(i);
34
    while (!q.empty()) {
35
        int u = q.front(); q.pop();
36
        topo.push_back(u);
37
        for (auto [v, p] : adj[u]) {
38
            (void)p; // unused here
39
            if (--indeg_copy[v] == 0) q.push(v);
40
        }
41
    }
42
    if ((int)topo.size() != n) {
43
        cerr << "Error: Graph has cycles; use a linear solver instead.\n";
44
        return 0;
45
    }
46
47
    // Normalize probabilities per node (in case input wasn't normalized)
48
    for (int u = 0; u < n; ++u) {
49
        if (outdeg[u] == 0) continue;
50
        double sum = 0.0;
51
        for (auto &e : adj[u]) sum += e.second;
52
        if (sum <= 0) {
53
            cerr << "Invalid probabilities at node " << u << "\n";
54
            return 0;
55
        }
56
        for (auto &e : adj[u]) e.second /= sum;
57
    }
58
59
    // Compute expectations in reverse topological order
60
    vector<double> E(n, 0.0);
61
    for (int i = n - 1; i >= 0; --i) {
62
        int u = topo[i];
63
        if (outdeg[u] == 0) { E[u] = 0.0; continue; }
64
        double val = 1.0; // immediate cost per step
65
        for (auto [v, p] : adj[u]) val += p * E[v];
66
        E[u] = val;
67
    }
68
69
    cout.setf(std::ios::fixed); cout << setprecision(10);
70
    for (int i = 0; i < n; ++i) {
71
        cout << E[i] << "\n";
72
    }
73
    return 0;
74
}
75

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute expected number of draws to collect all n coupons.
5
// State k = how many distinct coupons already collected.
6
// Recurrence: E[k] = n/(n-k) + E[k+1], with E[n] = 0.
7
// This follows from: E[k] = 1 + (k/n) E[k] + ((n-k)/n) E[k+1].
8
9
int main() {
10
    ios::sync_with_stdio(false);
11
    cin.tie(nullptr);
12
13
    int n; if (!(cin >> n)) return 0;
14
    vector<long double> E(n + 1, 0.0L);
15
    E[n] = 0.0L;
16
    for (int k = n - 1; k >= 0; --k) {
17
        E[k] = (long double)n / (long double)(n - k) + E[k + 1];
18
    }
19
20
    cout.setf(std::ios::fixed);
21
    cout << setprecision(10) << (double)E[0] << "\n";
22
23
    // Optional cross-check using harmonic numbers: E[T] = n * H_n
24
    long double H = 0.0L;
25
    for (int i = 1; i <= n; ++i) H += 1.0L / (long double)i;
26
    long double expected = (long double)n * H;
27
    cerr.setf(std::ios::fixed);
28
    cerr << setprecision(10) << "Check (n*H_n): " << (double)expected << "\n";
29
    return 0;
30
}
31

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Solve E[i] for expected steps to hit any terminal state in a general Markov chain.
5
// States: 0..n-1. Given terminals set T. For non-terminals N, equations are:
6
//   E[i] = 1 + sum_j P[i][j] * E[j],  i in N
7
// with E[t] = 0 for t in T. Rearranged over N:
8
//   (I - P_NN) * x = 1, where x are E[i] for i in N.
9
// We'll build and solve the linear system with partial pivoting.
10
11
int main() {
12
    ios::sync_with_stdio(false);
13
    cin.tie(nullptr);
14
15
    int n; if (!(cin >> n)) return 0;
16
    vector<int> terminal(n, 0);
17
    int k; cin >> k; // number of terminal states
18
    for (int i = 0; i < k; ++i) { int t; cin >> t; terminal[t] = 1; }
19
20
    vector<vector<long double>> P(n, vector<long double>(n, 0.0L));
21
    for (int i = 0; i < n; ++i) {
22
        for (int j = 0; j < n; ++j) {
23
            long double p; cin >> p; P[i][j] = p; // row i should sum to 1 if i non-terminal; row of terminal can be anything but E[t]=0
24
        }
25
    }
26
27
    // Map non-terminal indices to columns
28
    vector<int> idx(n, -1), ridx; ridx.reserve(n);
29
    for (int i = 0; i < n; ++i) if (!terminal[i]) { idx[i] = (int)ridx.size(); ridx.push_back(i); }
30
    int m = (int)ridx.size();
31
32
    if (m == 0) {
33
        // All states are terminal; expectations are zero
34
        for (int i = 0; i < n; ++i) cout << fixed << setprecision(10) << 0.0 << (i+1==n?'\n':' ');
35
        return 0;
36
    }
37
38
    // Build augmented matrix A|b of size m x (m+1)
39
    vector<vector<long double>> A(m, vector<long double>(m + 1, 0.0L));
40
    for (int r = 0; r < m; ++r) {
41
        int i = ridx[r];
42
        // Left side: I - P_NN
43
        for (int j = 0; j < n; ++j) {
44
            if (terminal[j]) continue; // E[j]=unknown only if non-terminal
45
            int c = idx[j];
46
            long double coeff = (i == j ? 1.0L : 0.0L) - P[i][j];
47
            A[r][c] += coeff;
48
        }
49
        // Right side: b = 1
50
        A[r][m] = 1.0L;
51
    }
52
53
    // Gaussian elimination with partial pivoting
54
    const long double EPS = 1e-15L;
55
    for (int col = 0, row = 0; col < m && row < m; ++col) {
56
        int sel = row;
57
        for (int i = row; i < m; ++i) if (fabsl(A[i][col]) > fabsl(A[sel][col])) sel = i;
58
        if (fabsl(A[sel][col]) < EPS) continue; // singular or nearly singular; skip
59
        swap(A[sel], A[row]);
60
        long double div = A[row][col];
61
        for (int j = col; j <= m; ++j) A[row][j] /= div; // make pivot 1
62
        for (int i = 0; i < m; ++i) if (i != row) {
63
            long double factor = A[i][col];
64
            if (fabsl(factor) < EPS) continue;
65
            for (int j = col; j <= m; ++j) A[i][j] -= factor * A[row][j];
66
        }
67
        ++row;
68
    }
69
70
    // Extract solution x (if a column was skipped due to near-singularity, default 0)
71
    vector<long double> x(m, 0.0L);
72
    for (int i = 0; i < m; ++i) x[i] = A[i][m];
73
74
    // Compose full E[0..n-1]
75
    vector<long double> E(n, 0.0L);
76
    for (int i = 0; i < n; ++i) if (!terminal[i]) E[i] = x[idx[i]]; // terminals remain 0
77
78
    cout.setf(std::ios::fixed); cout << setprecision(10);
79
    for (int i = 0; i < n; ++i) cout << (double)E[i] << (i+1==n?'\n':' ');
80
    return 0;
81
}
82