Detailed mathematical approach

Problem Summary

For each dimension \(d\) and roll cost \(c\), the problem first asks for the best expected net profit of the ordinary Ramvok game on a fixed non-empty subset \(A\subseteq\{1,\dots,d\}\). Those profits are then averaged over all subsets of the same size, and the averaged values are used in a second process whose state depends only on the current subset size. The resulting quantity is denoted \(S(d,c)\), and the final target is

$F(n)=\sum_{d=4}^{n}\sum_{c=0}^{n} S(d,c).$

The implementation verifies two checkpoints along the way:

$R(\{1,2,3,4\},0.2)=2.65,\qquad S(6,1)=208.3.$

Mathematical Approach

Fix \(d\ge 4\), a cost \(c\), and a non-empty subset

$A=\{v_1,\dots,v_k\}\subseteq\{1,\dots,d\},\qquad v_1<\dots<v_k.$

The exact method implemented by the programs has three layers: optimize the ordinary game on one subset, average over all subsets with the same cardinality, then solve a one-dimensional Bellman system for the super-game.

Step 1: Finite-Horizon Value on a Fixed Subset

Let \(h_t\) be the best expected gross reward when the available values are exactly the elements of \(A\) and at most \(t\) further rolls are allowed. The recurrence used by the implementation is

$h_0=0,\qquad h_t=\frac{1}{k}\sum_{i=1}^{k}\max(v_i,h_{t-1}).$

This recurrence is an optimal-stopping equation. On the first roll we see one of the \(v_i\), each with probability \(1/k\). After seeing \(v_i\), we either stop immediately and keep \(v_i\), or continue and replace it by the continuation value \(h_{t-1}\). Therefore the contribution of outcome \(v_i\) is \(\max(v_i,h_{t-1})\), and averaging over all outcomes gives the displayed formula.

Step 2: Convert Gross Reward into Net Profit

If each roll costs \(c\), then using exactly \(t\) allowed rolls gives expected net profit

$h_t-c t.$

Hence the subset profit is

$R(A,c)=\max_{t\ge 0}\bigl(h_t-c t\bigr).$

The code exploits two useful bounds. If \(c=0\), the value is simply the largest available reward, so \(R(A,0)=\max(A)\). If \(c\ge 1\) and \(A\subseteq\{1,\dots,d\}\), then \(h_t\le \max(A)\le d\), so for \(t>d\) we have

$h_t-c t\le d-t<0.$

Since \(t=0\) yields profit \(0\), no horizon larger than \(d\) can be optimal for the integer costs used in the main sum. That is why the exact search stops at \(t=d\).

Step 3: Average over Subset Size

For fixed \(d\) and \(c\), define the average subset profit at level \(k\) by

$a_k(c)=\frac{1}{\binom{d}{k}}\sum_{\substack{A\subseteq\{1,\dots,d\}\\ |A|=k}} R(A,c),\qquad 1\le k\le d.$

This is the key compression step. The super-game does not need the identity of the subset once we average over all \(k\)-subsets; it only needs the current size \(k\). All detailed subset structure is absorbed into the scalar quantity \(a_k(c)\).

Step 4: Bellman Equation for the Super-Game

Let \(x_k\) denote the expected total super-value when the current subset has size \(k\). The linear system in the implementations shows that the next transition depends only on whether the next uniformly chosen label is already present or absent. From a state of size \(k<d\):

$\Pr(k\to k-1)=\frac{k}{d},\qquad \Pr(k\to k+1)=1-\frac{k}{d}=\frac{d-k}{d}.$

Conditioning on that next step gives

$x_k=a_k(c)+\frac{k}{d}x_{k-1}+\left(1-\frac{k}{d}\right)x_{k+1},\qquad 1\le k<d.$

The state \(k=0\) is an implicit zero boundary, so no separate unknown is needed there. At the top state \(k=d\), the next move must go to \(d-1\), hence

$x_d=a_d(c)+x_{d-1}.$

Rearranging these equations produces a tridiagonal linear system, and the desired super-value for the pair \((d,c)\) is

$S(d,c)=x_d.$

Step 5: Final Aggregation

Once \(S(d,c)\) is known for every \(d\) and every integer cost \(0\le c\le n\), the problem asks for their double sum:

$F(n)=\sum_{d=4}^{n}\sum_{c=0}^{n} S(d,c).$

This is exactly the quantity accumulated by the implementations before the final rounding step.

Worked Example: \(A=\{1,2,3,4\}\) and \(c=0.2\)

Here \(k=4\). The recurrence gives

$h_1=\frac{1+2+3+4}{4}=2.5,$

$h_2=\frac{\max(1,2.5)+\max(2,2.5)+\max(3,2.5)+\max(4,2.5)}{4}=3,$

$h_3=\frac{3+3+3+4}{4}=3.25,$

$h_4=\frac{3.25+3.25+3.25+4}{4}=3.4375.$

The corresponding profits are

$h_1-0.2=2.3,\qquad h_2-0.4=2.6,\qquad h_3-0.6=2.65,\qquad h_4-0.8=2.6375.$

So the optimum is attained at \(t=3\), proving

$R(\{1,2,3,4\},0.2)=2.65.$

The second checkpoint, \(S(6,1)=208.3\), verifies that the averaging stage and the tridiagonal solve are also assembled correctly.

How the Code Works

The C++, Python, and Java implementations follow the same mathematical pipeline. For each \(d\), they enumerate every non-empty subset of \(\{1,\dots,d\}\) with a bitmask. The chosen bits already determine the subset in sorted order, so no expensive reordering is needed.

For each subset, the implementation computes the best net profit for every integer cost \(c=0,1,\dots,n\). The \(c=0\) case is handled immediately by taking the largest element of the subset. For \(c\ge 1\), the implementation advances the recurrence for \(h_t\) only up to \(t=d\), updating the best value \(h_t-c t\) for all costs in parallel.

These profits are accumulated in buckets indexed by subset size \(k\). After all subsets have been processed, each bucket sum is divided by the number of subsets of that size, producing the averages \(a_k(c)\).

Then, for each fixed cost \(c\), the implementation builds the tridiagonal system corresponding to the Bellman equations above and solves it by forward elimination followed by back substitution. The last component gives \(S(d,c)\). Finally it sums all \(S(d,c)\) over \(d=4,\dots,n\) and \(c=0,\dots,n\), and rounds the total to the nearest integer.

Complexity Analysis

For a fixed \(d\), there are \(2^d-1\) non-empty subsets. Processing one subset takes \(O(d)\) time to decode its elements, \(O(dk)\) time to advance the recurrence over \(t=1,\dots,d\), and \(O(dn)\) time to update all integer costs, where \(k\le d\). Thus one subset costs \(O(d(d+n))\) in the worst case, and the dominant cost for that dimension is

$O\bigl(2^d\,d(d+n)\bigr).$

The tridiagonal solve contributes only \(O(nd)\) time for that same \(d\), which is much smaller than the subset enumeration. Summing over \(d=4,\dots,n\) gives an overall exponential exact algorithm, dominated by the largest dimension; for \(d\) on the order of \(n\), this is roughly \(O(2^n n^2)\). The working memory is \(O(d(n+1))\) for the level averages plus \(O(d)\) for the linear-system arrays, with additional copies only when parallel workers are used.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=470
2. Optimal stopping and Bellman recurrences: Wikipedia — Bellman equation
3. Tridiagonal linear systems: Wikipedia — Tridiagonal matrix algorithm
4. Birth-death chains: Wikipedia — Birth-death process