Problem Link
Difficulty
Hard
Pre-requisites
DP, Convex-hull trick
Problem
Find the maximal score that is possible for Chef to obtain in the jumping competition
How to get 20 points
As 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 ith 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 ith hill. These hills’ numbers are all possible js such that j < i and p[j] < p[i]. Therefore,
- f[1] = a[1]
- f[i] = min{f[j] + (h[i] - h[j])2} + a[i] for all j < i, p[j] < p[i].
If you do the calculation of each f[i] naively, this results in the total complexity of O(N2).
How to get 100 points
The main idea remains the same as for the 20-point solution. Now we need to calculate **f[i]**s in a faster way.
First of all, let’s rewrite the recurrent formula a bit:
- f[i] = min{f[j] + (h[i] - h[j])2} + a[i] = min{f[j] + h[i]2 + h[j]2 - 2h[i]h[j]} + a[i]
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:
- Modification: set x[i] = a and y[i] = b. This routine will be called exactly once for each i.
- Query: get the minimal value of x[i] * z + y[i] for all i such than L ≤ i ≤ R for the given L, R, and z.
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 convex-hull 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:
- To add a linear function of the form ax+b to the set
- Find min{ax+b} for the given x among all the functions that are present in the set
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 convex-hull trick structure described right above.
In this case, the operations on out desired data structure will look like this:
- Modification: add the sought line to all the nodes that contain the position of this line. Since this is a segment tree, there won’t be more than O(log N) such nodes. An addition to the single node’s data structure is O(log N). So, we get the modification complexity of O(log2 N).
- Query: it works just in the standard segment tree. The initial query segment will be covered by O(log N) query nodes, and in each of them we can find the minimal value of all included functions in O(log N) too. So, we get the query complexity of O(log2 N).
You can refer the tester’s commented solutions for more details.
Setter’s Solution
Can be found here
Tester’s Solution
Can be found here