Temotoloraia's blog

IMPACT Olympiad for teachers and coaches 2021 Problem F
By Temotoloraia, history, 4 years ago, In English

Hi guys. Let's discuss this problem:

An array is good if the maximum element is no longer than the length.

The cost of the array is the length squared.

Divide the given array into several disjoint continuous parts so that each part is good and the total cost of all parts is the lowest possible.

Input In the first line, the positive integer n (1≤n≤100000) — the size of the array.

The next line contains n integers a1,a2,…,an(1≤ai≤n) Output Print the minimum possible total cost of all parts.

  • Vote: I like it
  • +25
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

You can register on contest here: https://impact21.contest.codeforces.com/enter

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

The problem was at the PreROI contest in Kazakhstan.

The main idea was D&C. Call recursion $$$calc(l, r)$$$ — that solves the problem for this range. Call recursion for the left side. For all elements on the right, let's find the optimal transition from the left side. Calculate prefix/suffix maximums for the right/left side respectively. Obvious that it will be monotonic. For each $$$r$$$ on the right, find all left borders — $$$l$$$, such that $$$[l; r]$$$ is good and make the transition from them. The possible values of $$$l$$$ will be an interval, so we can use some Convex Tree stuff + Segment Tree. Then call the recursion for the right side. There is actually a lot more to explain, but I think it's best to share the code. Because it's hard to explain in simple words :)

Code

→ Reply