hackercupai/hackercup huggingface dataset:
Let \(C_i\) be the maximum number of raindrops which can fall in the first \(i\) columns without causing any water to settle atop column 1. We can compute \(C_{1..N}\) in \(O(N)\) time by iterating over the columns from left to right, looking for each new highest (least deep) column, and considering filling the columns before it (back to the previous highest column) with water up to the depth of that previous highest column.

Then, let \(\textit{DP}_{i,d}\) be the number of different ways for \(d\) raindrops to fall in the first \(i\) columns without causing any water to settle atop column 1. \(\textit{DP}_{0,0}\) = 1, with the remaining values computable using dynamic programming as follows. We can consider all triples \((i, d, d')\) in increasing order of \(i\) such that \(d\) drops have fallen in the first \(i\) columns (such that \(d \le C_i\)) and \(d'\) drops will fall in column \(i + 1\) (such that \(d + d' \le C_{i+1}\)). This allows us to increase \(\textit{DP}_{i+1,d+d'}\) by \(\textit{DP}_{i,d} * {d+d' \choose d'}\), given that the new \(d'\) drops may be mixed in anywhere amongst the total \(d+d'\) drops. Overall, this process takes \(O(N * \sum(D_{1..N})^2)\) time.

Finally, let \(S_d\) be the probability that, once \(d\) drops have fallen, no water has yet settled atop column 1. Note that \(S_d = \textit{DP}_{N,d} / N^i\). The answer may then be computed as \(\sum(S_{0..C_N})\).