Fence Job#12840

Fence Job (Editorial)

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:

dp[i][j] = dp[i - 1][0] + dp[i - 1][1] + \ldots + dp[i - 1][j]

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.