Probability DP

Let $f_{i,j}$ be the probability that the princess wins when it is her turn and the bag contains $i$ white mice and $j$ black mice. Initialize the boundary conditions: $f_{0,j}=0$, because with no white mice the dragon wins, and $f_{i,0}=1$, because the next mouse drawn is white. Consider the transition for $f_{i,j}$:

• The princess draws a white mouse and wins, with probability $\dfrac{i}{i+j}$.
• The princess draws a black mouse and the dragon draws a white mouse, so the dragon wins, with probability $\dfrac{j}{i+j}\cdot\dfrac{i}{i+j-1}$.
• The princess draws a black mouse, the dragon draws a black mouse, and another black mouse escapes; transition to $f_{i,j-3}$ with probability $\dfrac{j}{i+j}\cdot\dfrac{j-1}{i+j-1}\cdot\dfrac{j-2}{i+j-2}$.
• The princess draws a black mouse, the dragon draws a black mouse, and a white mouse escapes; transition to $f_{i-1,j-2}$ with probability $\dfrac{j}{i+j}\cdot\dfrac{j-1}{i+j-1}\cdot\dfrac{i}{i+j-2}$.

The second case does not contribute to the princess's winning probability. The last two cases must also be legal: check the sizes of $i,j$; the third requires at least 3 black mice, while the fourth requires at least 1 white mouse and 2 black mice.

#include <cstring>
#include <iomanip>
#include <iostream>
using namespace std;

using ll = long long;
int w, b;
double dp[1010][1010];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> w >> b;
  memset(dp, 0, sizeof(dp));
  for (int i = 1; i <= w; i++) dp[i][0] = 1;  // Initialize the boundary
  for (int i = 1; i <= b; i++) dp[0][i] = 0;
  for (int i = 1; i <= w; i++) {
    for (int j = 1; j <= b; j++) {  // Probability transitions from the statement
      dp[i][j] += (double)i / (i + j);
      if (j >= 3) {
        dp[i][j] += (double)j / (i + j) * (j - 1) / (i + j - 1) * (j - 2) /
                    (i + j - 2) * dp[i][j - 3];
      }
      if (i >= 1 && j >= 2) {
        dp[i][j] += (double)j / (i + j) * (j - 1) / (i + j - 1) * i /
                    (i + j - 2) * dp[i - 1][j - 2];
      }
    }
  }
  cout << fixed << setprecision(9) << dp[w][b] << '\n';
  return 0;
}

Let $f_{i,j}$ be the expected number of days needed to reach the target after $i$ bug categories and bugs in $j$ subsystems have been found. The target state is finding all $n$ categories and all $s$ subsystems, so $f_{n,s}=0$. Starting from the target state, compute the transitions backwards; the answer is $f_{0,0}$.

Consider the transitions from $f_{i,j}$:

• The new bug belongs to one of the $i$ already discovered categories and one of the $j$ already discovered subsystems: $f_{i,j}$, with probability $p_1=\dfrac{i}{n}\cdot\dfrac{j}{s}$.
• It belongs to one of the $i$ discovered categories but to an undiscovered subsystem: $f_{i,j+1}$, with probability $p_2=\dfrac{i}{n}\cdot(1-\dfrac{j}{s})$.
• It belongs to an undiscovered category and one of the $j$ discovered subsystems: $f_{i+1,j}$, with probability $p_3=(1-\dfrac{i}{n})\cdot\dfrac{j}{s}$.
• It belongs to an undiscovered category and an undiscovered subsystem: $f_{i+1,j+1}$, with probability $p_4=(1-\dfrac{i}{n})\cdot(1-\dfrac{j}{s})$.

By linearity of expectation, the transition equation is

#include <iomanip>
#include <iostream>
using namespace std;
int n, s;
double dp[1010][1010];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> s;
  dp[n][s] = 0;
  for (int i = n; i >= 0; i--) {
    for (int j = s; j >= 0; j--) {
      if (i == n && s == j) continue;
      dp[i][j] = (dp[i][j + 1] * i * (s - j) + dp[i + 1][j] * (n - i) * j +
                  dp[i + 1][j + 1] * (n - i) * (s - j) + n * s) /
                 (n * s - i * j);  // Probability transition
    }
  }
  cout << fixed << setprecision(4) << dp[0][0] << '\n';
  return 0;
}

For this undirected connected graph, first use Floyd–Warshall to compute all-pairs shortest paths. Treat the movement from slot $i$ to slot $i+1$ as one stage. At each stage, the destination is $d_i$ with probability $p_i$ (if the change is applied) and $c_i$ with probability $1-p_i$. At most $m$ changes may be applied; only m of the $d_i$ destinations may be selected. The goal is the minimum expected total distance over the $n$ stages.

Let $f_{i,j,0/1}$ be the minimum expected distance after reaching the classroom for slot $i$, having used $j$ classroom-change opportunities including this slot, and choosing not to change (0) or to change (1) in this slot. The answer is $\min \{f_{n,i,0},f_{n,i,1}\} ,i\in[0,m]$. The boundary conditions are $f_{1,0,0}=f_{1,1,1}=0$.

Consider the transitions for $f_{i,j,0/1}$:

• If this stage does not use a change, $f_{i,j,0}$ may come from the previous non-change state, giving $f_{i-1,j,0}+w_{c_{i-1},c_{i}}$, or from the previous change state. Using conditional probability and the law of total probability, the latter is $f_{i-1,j,1}+w_{d_{i-1},c_{i}}\cdot p_{i-1}+w_{c_{i-1},c_{i}}\cdot (1-p_{i-1})$. Thus,

• If this stage uses a change, giving $f_{i,j,1}$, it may likewise come from either the previous non-change state or the previous change state. Multiply by $(1-p_i)$ when the previous application fails and by $p_i$ when it succeeds, then enumerate all possible cases. The resulting transitions follow directly from the preceding example.

#include <algorithm>
#include <iomanip>
#include <iostream>

using namespace std;

constexpr int MAXN = 2010;
int n, m, v, e;
int f[MAXN][MAXN], c[MAXN], d[MAXN];
double dp[MAXN][MAXN][2], p[MAXN];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m >> v >> e;
  for (int i = 1; i <= n; i++) cin >> c[i];
  for (int i = 1; i <= n; i++) cin >> d[i];
  for (int i = 1; i <= n; i++) cin >> p[i];
  for (int i = 1; i <= v; i++)
    for (int j = 1; j < i; j++) f[i][j] = f[j][i] = 1e9;

  int u, V, w;
  for (int i = 1; i <= e; i++) {
    cin >> u >> V >> w;
    f[u][V] = f[V][u] = min(w, f[u][V]);
  }

  for (int k = 1; k <= v; k++)
    for (int i = 1; i <= v; i++)  // Transfer the preceding DP as described above
      for (int j = 1; j < i; j++)
        if (f[i][k] + f[k][j] < f[i][j]) f[i][j] = f[j][i] = f[i][k] + f[k][j];

  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= m; j++) dp[i][j][0] = dp[i][j][1] = 1e9;

  dp[1][0][0] = dp[1][1][1] = 0;
  for (int i = 2; i <= n; i++)  // Transition with future dependence
    for (int j = 0; j <= min(i, m); j++) {
      dp[i][j][0] = min(dp[i - 1][j][0] + f[c[i - 1]][c[i]],
                        dp[i - 1][j][1] + f[c[i - 1]][c[i]] * (1 - p[i - 1]) +
                            f[d[i - 1]][c[i]] * p[i - 1]);
      if (j != 0) {
        dp[i][j][1] = min(dp[i - 1][j - 1][0] + f[c[i - 1]][d[i]] * p[i] +
                              f[c[i - 1]][c[i]] * (1 - p[i]),
                          dp[i - 1][j - 1][1] +
                              f[c[i - 1]][c[i]] * (1 - p[i - 1]) * (1 - p[i]) +
                              f[c[i - 1]][d[i]] * (1 - p[i - 1]) * p[i] +
                              f[d[i - 1]][c[i]] * (1 - p[i]) * p[i - 1] +
                              f[d[i - 1]][d[i]] * p[i - 1] * p[i]);
      }
    }

  double ans = 1e9;
  for (int i = 0; i <= m; i++) ans = min(dp[n][i][0], min(dp[n][i][1], ans));
  cout << fixed << setprecision(2) << ans;

  return 0;
}

When $m=1$, the robot stays in place with probability $\dfrac{1}{2}$ and moves down one cell with probability $\dfrac{1}{2}$, so the answer is $2\cdot (n-x)$. Let $f_{i,j}$ be the expected number of steps for a robot starting at row i, column j to reach row $n$. The terminal states are $f_{n,j}=0$. Since the robot chooses to stay, move left, move right, or move down with equal probability, the transitions for $f_{i,j}$ are:

• $f_{i,1}=\dfrac{1}{3}\cdot(f_{i+1,1}+f_{i,2}+f_{i,1})+1$
• $f_{i,j}=\dfrac{1}{4}\cdot(f_{i,j}+f_{i,j-1}+f_{i,j+1}+f_{i+1,j})+1$
• $f_{i,m}=\dfrac{1}{3}\cdot(f_{i,m}+f_{i,m-1}+f_{i+1,m})+1$

Movement between rows only goes down, so it has no future dependence. Movement between columns can go left or right and may create cycles, so it does have future dependence. Rearranging the equations gives:

• $2f_{i,1}-f_{i,2}=3+f_{i+1,1}$
• $3f_{i,j}-f_{i,j-1}-f_{i,j+1}=4+f_{i+1,j}$
• $2f_{i,m}-f_{i,m-1}=3+f_{i+1,m}$

Because the recurrence is evaluated backwards, every $f_{i+1,j}$ is already known. There are $m$ columns, so the right-hand side is an $m$-row column vector, while the left-hand side is an $m$-row, $m$-column matrix. The augmented matrix therefore has $m$ rows and $m+1$ columns; applying Gaussian elimination solves for the answer.

#include <cstdio>
#include <cstring>
using namespace std;

constexpr int MAXN = 1e3 + 10;

double a[MAXN][MAXN], f[MAXN];
int n, m;

void solve(int x) {
  for (int i = 1; i <= m; i++) {
    if (i == 1) {
      a[i][i] = 2;
      a[i][i + 1] = -1;
      a[i][m + 1] = 3 + f[i];
      continue;
    } else if (i == m) {
      a[i][i] = 2;
      a[i][i - 1] = -1;
      a[i][m + 1] = 3 + f[i];
      continue;
    }
    a[i][i] = 3;
    a[i][i + 1] = -1;
    a[i][i - 1] = -1;
    a[i][m + 1] = 4 + f[i];
  }

  for (int i = 1; i < m; i++) {
    double p = a[i + 1][i] / a[i][i];
    a[i + 1][i] = 0;
    a[i + 1][i + 1] -= a[i][i + 1] * p;
    a[i + 1][m + 1] -= a[i][m + 1] * p;
  }

  f[m] = a[m][m + 1] / a[m][m];
  for (int i = m - 1; i >= 1; i--)
    f[i] = (a[i][m + 1] - f[i + 1] * a[i][i + 1]) / a[i][i];
}

int main() {
  scanf("%d %d", &n, &m);
  int st, ed;
  scanf("%d %d", &st, &ed);
  if (m == 1) {
    printf("%.10f\n", 2.0 * (n - st));
    return 0;
  }
  for (int i = n - 1; i >= st; i--) {
    solve(i);
  }
  printf("%.10f\n", f[ed]);
  return 0;
}