Project Euler Problem 732
N trolls are in a hole that is DN cm deep.
Solution
Answer: 45609
Let
- $H=\sum_{n=0}^{N-1} h_n$,
- $D_N=\dfrac{H}{\sqrt2}$.
Suppose some trolls have already escaped. Let the total shoulder-height removed so far be $R$.
For troll $i$ to escape at that moment, the remaining trolls can stack beneath him with total shoulder-height $H-R-h_i$, so his hands reach
$$(H-R-h_i)+h_i+l_i = H-R+l_i.$$
Thus troll $i$ can escape iff
$$H-R+l_i \ge D_N$$
which rearranges to
$$R \le H-D_N+l_i.$$
Define the “deadline”
$$d_i=\left\lfloor H-D_N+l_i \right\rfloor.$$
If troll $i$ escapes, it increases $R$ by $h_i$. Therefore the problem becomes a classic weighted scheduling/knapsack problem:
- job length $=h_i$,
- deadline $=d_i$,
- value $=q_i$.
We maximize total IQ of scheduled jobs.
Using the generated troll data for $N=1000$ and dynamic programming over total removed height gives:
$$Q(1000)=45609.$$
Answer: 45609