Authors: Anton Trygub
Lucian Bicsi
Solved by:
First to solve: RAF Penguins
The set of operations might sound very daunting; let's try to find some properties about the resulting fence designs, to make it more tractable.
First of all, notice that if h_i < h_j and i<j, then h_j can never appear on a position smaller than or equal to . Similarly, if h_j < h_k with j < k, then h_j can never appear on a position greater than or equal to .
In particular, this tells us the rough structure of the resulting requences: they must be subsequences of (possibly repeating) numbers, but the unique values must appear in the same order as in the input. This is because for all i<j, if h_i < h_j then h_j can never before any occurence of h_i, and, conversely, if h_i > h_j, then h_i can never appear after any occurence of h_i.
This ultimately yields a simple dynamic programming strategy: consider dp[i][j] the number of output sequences such that b_i=h_j. We also compute for each two arrays:
lf_i tells us the rightmost position j<i such that h_j < h_i (or );
rt_i tells us the leftmost position j>i such that h_j < h_i (or n+1).
Initially, dp[0][0] = 1. At each step in our dp(i,j) computation, we assert that lf_i<j<rt_i (otherwise, dp[i][j] = 0). After that, we have the following recurrence:
which can be easily computed using prefix sums. Indeed, this approach works because all arrays such that each unique value in corresponds to a (potentially empty) range [l_i...r_i] of values in and lf_i \leq l_i and r_i \leq rt_i can be obtained. The valid reconstruction is by cutting the planks in decreasing order of heights.
The complexity of this solution is O(n^2).
Bonus: Solve the general version of the problem, where the plank lengths do not have to by distinct.