Editorial for SAC '22 Code Challenge 1 P5 - That Wall
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Intended Solution
First, realize that a valid, optimal solution can always be generated by only using the changes with the heights already given (this is where the intended and alternative solutions differ).
Second, find the DP state (e.g., represents the minimum cost to get to the
pillar and use a total of
changes).
Third, find the transition state:
Loop through the pillar (r) that we are currently at
Loop through all possible values of K (k) for the number of changes we have currently done (including this one)
Loop through all potential heights in the pillars
Loop through the pillar (l) that we start setting the height at while maintaining the cost to do so (this must be before the pillar that we selected in step 1)
Set the DP values (e.g., dp[r][k] = min(dp[r][k], dp[l - 1][k - 1] + cost)).
The implementation details are left as an exercise to the reader.
Time Complexity:
Alternative Solution
For this solution, we do not have the first realization (or assume it's false).
Instead, realize that the cost to set the suffix is a concave function.
For the intended solution above, replace looping through the potential heights with a binary search for the optimal height.
Again, the implementation details are left as an exercise to the reader.
Time Complexity:
Comments
Also, the factor of
can be dropped from my previous solution to yield
by noting that there's no need to re-sort the heights for each
interval - we can instead just pre-sort all heights in
time, and iterate through them in that order to perform each interval's line sweep in just
time.
The slightly better time complexity of
is also achievable by optimizing the intended solution. For each of the
pillar intervals
, the minimum cost to set them all to some equal height can be computed by sorting their heights (in
time) and performing a line sweep over those heights, while maintaining the cost to use the current height. That result can then be used for all
DP transitions involving that interval. My first in-contest submission used this approach.