Editorial for SAC '22 Code Challenge 1 P5 - That Wall

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: maxcruickshanks

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., $dp[i][j]$ ~dp[i][j]~ represents the minimum cost to get to the $i^\text{th}$ ~i^\text{th}~ pillar and use a total of $j$ ~j~ 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: $\mathcal{O}(N^3 K)$ ~\mathcal{O}(N^3 K)~

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: $\mathcal{O}(N^2 K \log(\max(H_i)))$ ~\mathcal{O}(N^2 K \log(\max(H_i)))~

Comments

5

SourSpinach commented on Nov. 4, 2021, 12:47 a.m.

Also, the factor of $\log(N)$ ~\log(N)~ can be dropped from my previous solution to yield $O(N^3 + N^2 K)$ ~O(N^3 + N^2 K)~ by noting that there's no need to re-sort the heights for each $l..r$ ~l..r~ interval - we can instead just pre-sort all heights in $O(N \log(N))$ ~O(N \log(N))~ time, and iterate through them in that order to perform each interval's line sweep in just $O(N)$ ~O(N)~ time.

5

SourSpinach commented on Nov. 2, 2021, 5:46 a.m. ← edited →

The slightly better time complexity of $O(N^3 \log(N) + N^2 K)$ ~O(N^3 \log(N) + N^2 K)~ is also achievable by optimizing the intended solution. For each of the $O(N^2)$ ~O(N^2)~ pillar intervals $l..r$ ~l..r~, the minimum cost to set them all to some equal height can be computed by sorting their heights (in $O(N \log(N))$ ~O(N \log(N))~ 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 $O(K)$ ~O(K)~ DP transitions involving that interval. My first in-contest submission used this approach.