These are the notes for Competitive Programming episode 40, part nine of the dynamic programming section. At the village mela, Rohan's dice game has cells 0 … n: you roll a fair die and move forward, but a roll that would pass cell n is wasted. An original problem, Exact Finish, asks for the expected (average) number of rolls, with an error of at most 10^−6. Simulating a million games is close but wrong in the 4th decimal, and far too slow for n = 10^6. The expected value splits into one roll plus the average of the possible futures: E[i] = 1 + (1/6) Σ E[next], filled from the finish backwards. The trap: a wasted roll leads back to the same cell, so E[i] depends on itself. Recursion then never ends (SIGSEGV) and a plain loop uses E[i] = 0. A line of algebra solves it: E[i] = (6 + sum) / (6 − stay). Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook
Rohan charges per roll at his mela stall. Players start at cell 0 and must land exactly on cell n; a roll that overshoots is wasted and the player stays. Players want to know how many rolls a game takes on average, so they know what it will cost.
Problem Q · Exact Finish
(Written for this course, in the style of an AtCoder Beginner Contest problem.)
Cells 0 … n; start at 0. Each turn roll a fair six-sided die showing d: if i + d ≤ n move to i + d, otherwise stay at i. Print the expected number of rolls until you stand on cell n.
- Input: n (1 ≤ n ≤ 10^6).
- Output: the expected number of rolls; an absolute error of at most 10^−6 is accepted.
| Input | Output |
|---|---|
1 |
6.000000 |
8 |
7.166667 |
10 |
7.587963 |
1000000 |
285719.047619 |
Expected value = the average over infinitely many games. If an outcome x happens with probability p(x), the expected value is Σ p(x) · x.
Attempt 1: simulate a million games (not exact, and TLE)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
mt19937 rng(40);
int games = 1000000;
ll rolls = 0;
for (int g = 0; g < games; g++) { // play a million games
int at = 0;
while (at < n) {
int d = rng() % 6 + 1;
if (at + d <= n) at += d; // overshoot: stay
rolls++;
}
}
printf("%.6f\n", (double)rolls / games);
return 0;
}
n = 10 prints 7.587807, but the exact answer is 7.587963: wrong in the 4th decimal (an error of 1.6 · 10^−4, far above 10^−6). A simulation's error shrinks like 1/√games, so a million games give about three correct digits. For n = 10^6 each game is about 2.9 · 10^5 rolls: Time Limit Exceeded.
Step 1: one roll plus the rest
Like a bus ride (time home = this stop + time from the next stop), the rolls needed from cell i are one roll now plus the average of the six equally likely futures:
E[i] = 1 + (1/6) · Σ over d = 1 … 6 of E[next(i, d)], next(i, d) = i + d if i + d ≤ n, else i
Base: E[n] = 0 (finished). Every move goes forward, so fill from the finish backwards. This uses linearity of expectation (episode 28): the expectation of "1 + rolls from the next cell" is 1 + the average of the next cells' expectations.
The self-loop trap
Near the end some faces are wasted, so next(i, d) = i: E[i] appears on both sides. On a track of 8, cell 7 moves only on a 1:
E[7] = 1 + (1/6) · (E[8] + 5 · E[7])
A dependency that points back at itself is a self-loop: there is no smaller state to compute first.
Recursion straight from the formula (infinite recursion)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
vector<double> memo;
vector<bool> seen;
double E(int i) { // expected rolls from cell i
if (i == n) return 0;
if (seen[i]) return memo[i];
double sum = 0;
for (int d = 1; d <= 6; d++)
sum += E(i + d <= n ? i + d : i); // overshoot: stay at i
seen[i] = true;
return memo[i] = 1 + sum / 6;
}
int main() {
cin >> n;
memo.assign(n + 1, 0);
seen.assign(n + 1, false);
printf("%.6f\n", E(0));
return 0;
}
n = 8: Runtime Error (SIGSEGV). E(7) rolls a 2 (wasted), calls E(7) again before it is marked as seen, and so on until the stack is exhausted.
A backwards loop that uses E[i] = 0 for itself (wrong)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<double> E(n + 1, 0); // E[n] = 0
for (int i = n - 1; i >= 0; i--) {
double sum = 0;
for (int d = 1; d <= 6; d++)
sum += E[i + d <= n ? i + d : i]; // E[i] is still 0 here!
E[i] = 1 + sum / 6;
}
printf("%.6f\n", E[0]);
return 0;
}
n = 8 prints 2.775231 (expected 7.166667): every wasted roll was treated as "zero more rolls", as if the game had ended.
Step 2: solve for E[i]
Let stay be the number of faces that overshoot and sum the total of E over the faces that move. Then
E[i] = 1 + (sum + stay · E[i]) / 6 6 · E[i] − stay · E[i] = 6 + sum E[i] = (6 + sum) / (6 − stay)
stay ≤ 5 (a roll of 1 always moves when i < n), so we never divide by zero, and E[i] now depends only on cells after i.
Trace for n = 8:
| cell | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| wasted faces | 0 | 0 | 0 | 1 | 2 | 3 | 4 | 5 | – |
| E | 43/6 ≈ 7.166667 | 7 | 6 | 6 | 6 | 6 | 6 | 6 | 0 |
Cells 2 … 7 all give exactly 6: from each, exactly one face lands on 8 and the other moves keep you within six cells of the end. Cell 1: (6 + 6 · 6) / 6 = 7. Cell 0: (6 + 7 + 5 · 6) / 6 = 43/6.
The accepted solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<double> E(n + 1, 0); // E[n] = 0: already finished
for (int i = n - 1; i >= 0; i--) { // from the finish backwards
double sum = 0;
int stay = 0; // rolls that overshoot
for (int d = 1; d <= 6; d++) {
if (i + d <= n) sum += E[i + d];
else stay++;
}
// E[i] = 1 + (sum + stay * E[i]) / 6 → solve for E[i]
E[i] = (6 + sum) / (6 - stay);
}
printf("%.6f\n", E[0]);
return 0;
}
| Input | Output |
|---|---|
8 |
7.166667 |
10 |
7.587963 |
1 |
6.000000 |
1000000 |
285719.047619 (instant) |
For large n the answer is close to n / 3.5 (the average roll is 3.5) plus a small end correction: 10^6 / 3.5 ≈ 285714.3.
Checking doubles: compare with a tolerance
A stress test with doubles cannot demand an exact match. Here the formula is compared with 2 · 10^6 simulated games for boards 1 … 8:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
// the formula against a long simulation, for small boards
mt19937 rng(7);
for (int n = 1; n <= 8; n++) {
vector<double> E(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
double sum = 0;
int stay = 0;
for (int d = 1; d <= 6; d++) { if (i + d <= n) sum += E[i + d]; else stay++; }
E[i] = (6 + sum) / (6 - stay);
}
ll rolls = 0;
int games = 2000000;
for (int g = 0; g < games; g++)
for (int at = 0; at < n; rolls++) {
int d = rng() % 6 + 1;
if (at + d <= n) at += d;
}
printf("n=%d dp %.4f simulated %.4f\n", n, E[0], (double)rolls / games);
}
}
Output:
n=1 dp 6.0000 simulated 5.9946
n=2 dp 6.0000 simulated 6.0006
n=3 dp 6.0000 simulated 6.0037
n=4 dp 6.0000 simulated 5.9928
n=5 dp 6.0000 simulated 6.0026
n=6 dp 6.0000 simulated 5.9940
n=7 dp 7.0000 simulated 6.9992
n=8 dp 7.1667 simulated 7.1625
They agree to about two decimals, which is all a simulation can give; the DP gives every digit.
A second question: forward probability DP
Cell k has a chai stall. What is the probability that you ever stand on cell k? Expected values flow backwards from the finish; probabilities flow forwards from the start (p[0] = 1). Wasted rolls only repeat the turn, so when you finally move, each of the moves = min(6, n − i) real moves is equally likely:
p[i + d] += p[i] / moves for d = 1 … moves
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n, k;
cin >> n >> k;
vector<double> p(n + 1, 0); // p[i] = chance to ever stand on cell i
p[0] = 1;
for (int i = 0; i < n; i++) {
int moves = min(6, n - i); // rolls that really move
for (int d = 1; d <= moves; d++)
p[i + d] += p[i] / moves; // wasted rolls just repeat: each real move is equally likely
}
printf("%.6f\n", p[k]);
return 0;
}
10 7 prints 0.296489. Far from the start the chance tends to 1 / 3.5 ≈ 0.2857, because you land on about one cell in every 3.5.
Complexity vs the constraints
| Approach | Time | Verdict |
|---|---|---|
| simulate 10^6 games | ≈ 3 · 10^11 rolls at n = 10^6 | TLE, and only ~3 digits |
| recursion as written | never ends | Runtime Error (SIGSEGV) |
| loop with E[i] = 0 for itself | O(6n) | wrong (2.775231) |
| solved backwards DP | O(6n) = 6 · 10^6 | accepted, exact |
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| simulate and average | 7.587807 (exact 7.587963) |
random error ~1/√games | compute the expectation |
| E(i) calls E(i) on a wasted roll | Runtime Error (SIGSEGV) |
infinite recursion | solve for E[i] first |
| E[i] = 0 inside its own formula | 2.775231 (expected 7.166667) |
the self term is not known yet | E[i] = (6 + sum) / (6 − stay) |
printf("%.2f") or plain cout |
7.17 / 7.16667 |
too few digits | printf("%.6f") or cout << fixed << setprecision(6) |
int division 1 / 6 |
0 |
integer division | 1.0 / 6 |
| forward DP for an expectation with a fixed end | hard to set up | expectations depend on the future | expectations backwards, probabilities forwards |
Mini project
Build a "board game analyser": a track of n cells with snakes and ladders (jump[i] = where you end up after landing on i). Compute the expected number of rolls to finish with the backwards DP when all jumps go forward. When a snake goes back, the equations form a system with cycles: solve it with Gaussian elimination for n ≤ 100, and compare with a simulation of 10^6 games.
Practice
-
Add snakes: landing on cell s sends you back to t < s.
Answer
Now E[s] = E[t] and the dependencies have cycles bigger than one cell, so the backwards loop no longer works. For small n write the n linear equations and solve them with Gaussian elimination (O(n³)); with special structure (few snakes) iterate value updates until they converge. -
A die with faces 1 … k.
Answer
E[i] = (k + Σ_{valid d} E[i + d]) / (k − stay), with a sliding-window sum to keep it O(n) for large k. With k = 2 and n = 1: <b>2</b> (wait for a 1). -
The answer modulo 998244353 (as P · Q^−1).
Answer
Replace division by multiplication with a modular inverse (episode 22): E[i] = (6 + sum) · inv(6 − stay). For n = 1 the answer is <b>6</b>; for n = 8 it is 43 · inv(6) mod 998244353 = <b>166374066</b>. -
The probability of finishing within m rolls.
Answer
Forward DP over (rolls used, cell): P[r + 1][next] += P[r][i] / 6, wasted rolls staying at i. The answer is P[m][n] (cell n absorbs). For n = 1, m = 1: <b>1/6 ≈ 0.166667</b>.
Quick quiz
You toss a fair coin. Heads: you are done. Tails: the toss is wasted and you toss again. How many tosses on average?
A) 1 · B) 1.5 · C) 2 · D) it never ends
Answer
C. E = 1 + (1/2) · 0 + (1/2) · E, so E/2 = 1 and E = 2. The same self-loop trick.
Interview questions
- What is an expected value? The probability-weighted average of the outcomes, Σ p(x) · x; the long-run average over many trials.
- Why compute expectations backwards? E at a state is defined by the states after it; the end state has a known value (0 more steps).
- What is the self-loop trick? When E[i] depends on itself with coefficient c/k, move that term to the left: E[i] · (1 − c/k) = rest, then divide.
- When do you use forward probability DP? For "probability of reaching/visiting a state": start with probability 1 at the start and push it along the transitions.
- How do you print doubles for a 10^−6 tolerance?
printf("%.6f")orcout << fixed << setprecision(6)(or more digits; never the default 6 significant digits). - Why not simulate? Monte Carlo error falls like 1/√trials: 10^12 games for 6 digits.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Probability | How often an outcome happens, from 0 to 1 | a die shows 6: 1/6 |
| Expected value | The probability-weighted average outcome | E[0] = 7.166667 rolls |
| Linearity of expectation | E[a + b] = E[a] + E[b] | 1 roll + E[next] |
| Expected-value DP | DP whose states store expectations, usually filled backwards | E[i] |
| Probability DP | DP whose states store probabilities, usually pushed forwards | p[i] |
| Self-loop | A state whose formula contains itself | E[7] uses E[7] |
| Monte Carlo simulation | Estimating by playing many random games | 7.587807 |
| Absolute error | |your answer − true answer| | ≤ 10^−6 |
| Modular inverse | x with a · x ≡ 1 (mod p), used to divide mod p | inv(6) |
setprecision / %.6f |
Print a fixed number of decimals | 7.166667 |
Summary
- Simulation is approximate (~3 digits) and slow; compute the expectation exactly.
- E[i] = 1 + average of E over the next states; fill backwards from E[end] = 0.
- A wasted roll is a self-loop: recursion never ends, a loop with E[i] = 0 is wrong. Move the self term to the left: E[i] = (6 + sum) / (6 − stay).
- Probabilities flow forwards from p[start] = 1.
- Print enough digits (
%.6f). O(6n) for n = 10^6. - Real bugs: SIGSEGV from the self-loop,
2.775231from E[i] = 0,7.587807from simulation.
Solutions in C++, Java and Python
Problem Q · Exact Finish
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<double> E(n + 1, 0); // E[n] = 0: already finished
for (int i = n - 1; i >= 0; i--) { // from the finish backwards
double sum = 0;
int stay = 0; // rolls that overshoot
for (int d = 1; d <= 6; d++) {
if (i + d <= n) sum += E[i + d];
else stay++;
}
// E[i] = 1 + (sum + stay * E[i]) / 6 → solve for E[i]
E[i] = (6 + sum) / (6 - stay);
}
printf("%.6f\n", E[0]);
return 0;
}
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
int n = new Scanner(System.in).nextInt();
double[] E = new double[n + 1]; // E[n] = 0
for (int i = n - 1; i >= 0; i--) { // from the finish backwards
double sum = 0;
int stay = 0; // rolls that overshoot
for (int d = 1; d <= 6; d++) {
if (i + d <= n) sum += E[i + d];
else stay++;
}
E[i] = (6 + sum) / (6 - stay); // solved for E[i]
}
System.out.printf("%.6f%n", E[0]);
}
}
Python (6 · 10^6 steps take a few seconds in Python; fine for the samples)
def main():
n = int(input())
E = [0.0] * (n + 1) # E[n] = 0
for i in range(n - 1, -1, -1): # from the finish backwards
s, stay = 0.0, 0
for d in range(1, 7):
if i + d <= n:
s += E[i + d]
else:
stay += 1
E[i] = (6 + s) / (6 - stay) # solved for E[i]
print(f"{E[0]:.6f}")
main()
All three print 6.000000, 7.166667, 7.587963 and 285719.047619 for n = 1, 8, 10 and 10^6.
Next episode: DP optimisation 1: monotonic queue and prefix-min tricks (a sliding-window minimum inside a DP).