> For the complete documentation index, see [llms.txt](https://solutions.icpc.uclaacm.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://solutions.icpc.uclaacm.com/2021-tryout-solutions/tryout-2-solutions/h-witchwood.md).

# 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)$$