Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Pyramid form (increasing then decreasing) consecutive array using reduce operations

Revision en1, by wish_me, 2017-09-30 21:14:57

We have N (where N > 2) stones of various heights laid out in a row. Task is to make a pyramid from given array of stones. In a pyramid, height of the stones start from 1, increase by 1, until it reaches some value x, then decreases by 1 until it reaches 1 again i.e. the stones should be 1, 2, 3, 4…x – 1, x, x – 1, x – 2 … 1. All other stones not part of the pyramid should have a height 0. We cannot move any of the stones from their current position, however, by paying a fee of 1, we can reduce the heights of the stones. We wish to minimize the cost of building a pyramid. Output the minimum cost to build this pyramid.

N<10^3 height<10^4

Examples:

Input : 1 2 3 4 2 1

Output : 4

The best pyramid that can be formed in this case is:

1 2 3 2 1 0

The cost is thus:

(4 — 2) + (2 — 1) + (1 — 0) = 4

Input : 1 5 2

Output : 4

We make a pyramid 1 2 1

Input : 1 2 1

Output : 0

We already have a pyramid, we do not need to do any

further construction.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English wish_me 2017-09-30 21:14:57 1105 Initial revision (published)