Prerequisites: Constructive Algorithm, Implementation

At first, as you cannot make $a_1$ or $a_n$ the highest pillar after the arrangment, it's a nice observation that you don't need to increase the height of $a_1$ of $a_n$ in any time. So, $a_2$ needs to be $max(a_1+1,a_2)$ to satisfy the $1^{st}$ property. Similarly, $a_{n-1}$ needs to be $max(a_n+1,a_{n-1})$. So, you can calculate $lcost_i$ as the cost needed to make $a_1, a_2, ..., a_i$ strictly increasing and same goes for $rcost_i$ to make $a_i, a_{i+1}, ..., a_n$ strictly decreasing.

So, we check for each index $i$ to be the highest pillar $h$ after the arrangement if possible. The cost for an index $i$ to satisfy the properties is $lcost_{i-1} + rcost_{i+1} + (h - a_i)$ if $a_i \leq h$, $lcost_{i-1} < h$ and $rcost_{i+1} < h$. You just check all the possibilities and take the minimum.

Time Complexity: O(n)

74% Solution Ratio

Fizzz_83Earliest,

prodip_bsmrstuFastest, 0.0s

riyad000Lightest, 4.2 MB

Sumaya_1703110Shortest, 752B

Toph uses cookies. By continuing you agree to our Cookie Policy.