×

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

This question is marked "community wiki".

719436377
accept rate: 0%

19.6k349497539

 1 There is a mistake in the tutorial. They defined x[p[i]] = a = f[i] + h[i]^2 and y[p[i]] = b = -2h[i] Then it is written that f[i] = min{y[j]+x[j] . h[i]} + h[i]^2 + a[i] for all js such that j < p[i]. It should be f[i] = min{y[j] . h[i]+x[j]} + h[i]^2 + a[i] for all js such that j < p[i], or interchange the definitions of x and y. answered 12 Oct '15, 19:35 130●7 accept rate: 0%
 1 The full dynamic variant of convex-hull trick can be solved using divide-and-conquer without any data structures. In order to build the convex offline, use divide and conquer, and the sub-problem 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 divide-and-conquer in the sub-problem, 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 11●2 accept rate: 0%
 0 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 sub-task answered 12 Oct '15, 16:32 26●1 accept rate: 16% 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)
 0 instead of segtree you can use a BIT also https://www.codechef.com/viewsolution/8424830 answered 12 Oct '15, 17:05 1.0k●1●13 accept rate: 4%
 0 They said that the data structure should do two things: 1. Update x[i] = a and y[i] = b. 2. Find min(a[i]. x + b[i]) for some x, and L < i < R . Then when we are calculating f[i], we need to consider min(a[j]. h[i] + b[j]) for 0 < j < p[i], and then set a[p[i]] = -2*h[i] and b[p[i]] = h[i]^2 + f[i]. Now we are ready to calculate f[i+1]. So why do we need a Segment Tree now? answered 12 Oct '15, 19:33 130●7 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,182
×2,022
×1,322
×142
×103

question asked: 05 Oct '15, 04:33

question was seen: 6,545 times

last updated: 15 Jan '16, 16:01