Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 7 / c / Solution

Whenever an update improves $F[x]$, store choice[x] = i. Starting at x = m, repeatedly increment count[choice[x]] and subtract that denomination from x, stopping at zero. The invariant is that the selected stamps plus an optimal representation of the residual total attain the original optimum; every step reduces $F[x]$ by one. Reconstruction uses $F[m]\le m$ steps and $O(n)$ output counters, preserving the $O(mn)$ total time bound.