Editorial for Show Off!

Prerequisites: Constructive Algorithm, Implementation

At first, as you cannot make a1a_1 or ana_n the highest pillar after the arrangment, it's a nice observation that you don't need to increase the height of a1a_1 of ana_n in any time. So, a2a_2 needs to be max(a1+1,a2)max(a_1+1,a_2) to satisfy the 1st1^{st} property. Similarly, an1a_{n-1} needs to be max(an+1,an1)max(a_n+1,a_{n-1}). So, you can calculate lcostilcost_i as the cost needed to make a1,a2,...,aia_1, a_2, ..., a_i strictly increasing and same goes for rcostircost_i to make ai,ai+1,...,ana_i, a_{i+1}, ..., a_n strictly decreasing.

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

Time Complexity: O(n)


74% Solution Ratio

Fizzz_83Earliest, Jul '20

prodip_bsmrstuFastest, 0.0s

riyad000Lightest, 4.2 MB

Sumaya_1703110Shortest, 752B

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