Problem LinkDifficultyHard PrerequisitesDP, Convexhull trick ProblemFind the maximal score that is possible for Chef to obtain in the jumping competition How to get 20 pointsAs usual, we won't consider the solutions that doesn't lead to the complete solution in any way. The solution to a problem is based on the following dynamic programming idea. Let's denote the maximal score that we can get by the time we stand at the i^{th} hill by f[i]. Clearly, we need to calculate the value of f[N]. Let's denote the rules for the calculation of f[i]. Clearly, f[1] will be equal to a[1] because we can't jump on the first hill from any other hill. For i ≥ 2, we can find all the hills, from which we can jump to the i^{th} hill. These hills' numbers are all possible js such that j < i and p[j] < p[i]. Therefore,
If you do the calculation of each f[i] naively, this results in the total complexity of O(N^{2}). How to get 100 pointsThe main idea remains the same as for the 20point solution. Now we need to calculate f[i]s in a faster way. First of all, let's rewrite the recurrent formula a bit:
It gives us a new idea. If we can somehow maintain the data structure, capable of answering two following types of queries fast enough, we solve the problem:
Indeed. On one hand, after the new value of f[i] is calculated, we can do a modification at the position p[i] with the parameters x[p[i]] = a = f[i] + h[i]^{2} and y[p[i]] = b = 2h[i]. And on the other hand, when we need to calculate the value of the new f[i], it will be equal to min{y[j]+x[j]*h[i]} + h[i]^{2} + a[i] for all js such that j < p[i]. So now we can concentrate on the implementation of the data structure described above. This is actually a well known problem and it is called convexhull trick. Here is the comprehensive and detailed tutorial on it. The variation you need is a fully dynamic variant. The approach described by the link above enables us to have a data structure that maintains the following operations:
Both these operations can be done in amortized O(log N) time. But this is still not what we want, because we need range queries. But we can create a segment tree. In each node of this segment tree we can store a dynamic convexhull trick structure described right above. In this case, the operations on out desired data structure will look like this:
You can refer the tester's commented solutions for more details. Setter's SolutionCan be found here Tester's SolutionCan be found here
This question is marked "community wiki".
asked 05 Oct '15, 04:33

There is a mistake in the tutorial. answered 12 Oct '15, 19:35

The full dynamic variant of convexhull trick can be solved using divideandconquer without any data structures. In order to build the convex offline, use divide and conquer, and the subproblem is to calculate dp transition from all points i from [L, mid] to [mid + 1, R], still this is not complete, we have to consider the p[i] < p[j] constraint, so we use a second divideandconquer in the subproblem, then the questions changes to calculate dp transition from all points i from [L, mid] and at the same time p[i] in [L2, mid2], to all points from [mid + 1, R] and p[i] in [mid2 + 1, R2], then we can build the convex offline for the first half, and do a binary search on the second half. answered 13 Oct '15, 13:23

Can you explain how to do the 3rd (and 4th) subtask(s) even without knowing the above solution. Lots of people have solved upto the 3rd subtask and not the whole question. I was thinking there might be a DP solution for the 3rd subtask answered 12 Oct '15, 16:32
the testdata for the 3rd subtask was not so strong , i wrote some SQRT decomposition solution for the 3rd subtask https://www.codechef.com/viewsolution/8371300 but its very slow in worst case so i switched to convex hull trick
(12 Oct '15, 17:03)
so there is no DP solution for the 3rd subtask ?
(13 Oct '15, 11:01)

instead of segtree you can use a BIT also https://www.codechef.com/viewsolution/8424830 answered 12 Oct '15, 17:05

They said that the data structure should do two things: answered 12 Oct '15, 19:33
