H: Witchwood

https://open.kattis.com/problems/witchwood

Let $C_i$ be the optimal expected time to build a house with $i$ logs. When building a house with $i+1$ logs, we first need to place $i$ logs successfully, then place the last log; if the last log fails, then we must start the process over. The probability that the first $i$ logs fail does not matter, only the expected time it takes to place them; therefore, we should just choose the strategy with least expected time, i.e. the strategy that takes $C_i$ time in expectation.

Suppose we choose log from location $j$ last and let $C$ be the overall expected time with this strategy (follow the optimal strategy for the first $i$ logs, then choose log $j$ as the $i+1$th). We spend time $C_i+T_j$ in expectation to collect the first $i$ logs and attempt log $j$, and with probability $P_j$ it fails and forces us to spend an additional $K+ C$ in expectation to redo the process. So

$C = C_i + T_j + P_j(K + C)$

and solving

$C = \frac{1}{1-P_j}(C_i + T_j + P_jK)$

Computationally, we have enough time to check all possible $j$ to find the one which minimizes the expected time, so we can write a program that computes

$C_{i+1}= \min_j\frac{1}{1-P_j}(C_i + T_j + P_jK)$