JUMP - Editorial

editorial
, , , ,
1

Problem Link

Practice

Contest

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

3 Likes
2

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

3

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

4

instead of segtree you can use a BIT also https://www.codechef.com/viewsolution/8424830

5

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?
6

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.

1 Like
7

so there is no DP solution for the 3rd subtask ?

8

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.

1 Like