I got a nice problem from Korean OI : https://www.acmicpc.net/problem/2300 .

Since deriving recurrence is not the point of this topic, I will give you the formula :

N <= 10000

0 <= Xi <= X(i+1) <= 10^9, (1 <= i < N), 0 <= Yi <= 10^9 (1 <= i <= N)

DP[i] = Min(DP[j] + Cost(j+1, i))for all j < i. when Cost(s, e) = Max(X[e] — X[s], Max(Y[s], Y[s+1] ... Y[e]))

The goal is to calculate DP[N] — and O(N^2) solution is quite straightforward.

However, I heard that there is a subquardatic solution to this problem! I tried various strategies to solve it, but failed.

Does anyone have a hint / idea to the subquadratic solution?

Seems too easy, maybe you missed some constraint. For sure we can say that lower bound on DP[N] is X[N]-X[1] because of the cost function. Now we have two cases, let Ym = max(Y1, Y2, .., YN): Ym <= X[N]-X[1] -> then we can achieve the lower bound by saying DP[N] = DP[0] + cost(1, N) = X[N]-X[1]. Ym > X[N]-X[1] -> now that also means Ym > X[j]-X[i], for every i,j pair. So at least one of the cost functions on our path from 0 to N will be equal to Ym. That means lower bound on DP[N] is Ym. But again we can achieve that by DP[N] = DP[0] + cost(1, N) = Ym.

I think I've just read the problem, and, if I uderstood right, in the formula of Cost (s, e) should be the minimum length of a square containing those points, so Cost (s, e) = max (X[e] — X[s], max (Y[s], Y[s + 1], ..., Y[e]) — min (Y[s], Y[s + 1], ..., Y[e]))

We don't have to subtract minimum since every square's center should be fixed at x-axis. With slight modification we can get the above recurrences.

Thanks for replying!

However, the lower bound of DP[N] is not X[n] — X[1]. since the formula is DP[j] + Cost(j+1, i) — not DP[j] + Cost(j, i). for example, if Ym = 0, then the answer is zero.

You're right, I saw cost(j, i) in the dp recurrence. But even then, is it the cost function geniucos wrote or the one in the blog post?

No, the cost function is same as the blog post. (it doesn't subtract minimum)

Sorry for misunderstanding. Still, none of the recurrences I've tried returned the right answer on the sample. Is dp[0] = 0? Is it really maximum of y or of |y| ? I implemented your reccurence and I'm getting the answer 4...

dp[0] is zero.

since we will cover the points with rectangle [X, X+P] x [Y-P/2, Y+P/2], it is the maximum of 2|y|.

Accepted code at acmicpc.net : http://ideone.com/w7ERW0

Thanks. I've just got AC(I hope I'm not that sure because it is in korean, but it is some green writing :)) ). Are you sure there exist a subqudratic solution? It seems interesting, but in this case, why didn't they put some bigger constraints?

I guess it's a green writing with "맞았습니다!!" ( = Accepted.). No other green writing will appear as a verdict :)

This problem appeared as an "easiest" problem to KOI (specifically, high school division) at that time. So probably they had lower the constraint to match the difficulties (and propose another problem at "hardest" level.)

I'm not 100% sure that subquadratic solutions exist, but AFAIK this problem had appeared in an old IOI Korean team selection test. I remember that I heard it in a Slack chatgroup of Korean problem solvers.

The problem is that you really can't say that lower bound is x[N] — x[1]. You cand choose the partition (1, 2) (3, 4) and, if y = 0 for all, it gives you a cost lower with x[3] — x[2] than X[N] — X[1]

Seems that I could solve it in O(n log^2 n). Main idea that problem for Cost(s, e) = X[e] — X[s], could be solved easily by keeping DP[j]-X[j+1], for Cost(s, e) = Max(Y[s], Y[s+1] ... Y[e]) by segment tree with maximum on DP[j]+Max(Y[j+1], ... Y[i]) and multi-addition operation (when maximums on current suffixes of Y increases you should add difference on suffix of suffixes. Invariant is that if two maximums became same they became same forever and all future adds could be done as multi-adds). So we need separate cases where X[e] — X[s] < Max(Y[s], Y[s+1] ... Y[e]. It could be done by two-dimentional segment tree in the similar manner as described above for case Cost(s, e) = Max(Y[s], Y[s+1] ... Y[e]).

Thanks for sharing your ideas! btw I have some questions for your algorithm.

If we can separate every value into X[e] — X[s] <= Max(Y[s] .. Y[e]), we can solve this problem. However, I think some value will "oscillate" for O(N) times — like, X[e] — X[s] <= Max(Y[s] .. Y[e]) but X[e+1] — X[s] >= Max(Y[s] .. Y[e]) and so on.. this will require O(N^2) updates.

If we don't separate every value into X[e] — X[s] <= Max(Y[s] .. Y[e]), It's not clear how can we solve this problem.

Also, I don't get why 2d segment tree is needed for such operation. Can you tell me what am I missing?

Disclaimer that it's 4am here, so my idea may make sense or not:

Let's write

max(Y_{j},Y_{j + 1}, ...,Y_{i}) =Y(j,i). When we are processingi, for everyjwe want to know ifY(j,i) > =X_{i}-X_{j}, orY(j,i) -X_{j}≥X_{i}. So we can use two trees: one stores min value ofdp[j] +X_{j}-X_{i}for every interval ofY(j,i) -X_{j}, the other one stores min value ofdp[j] +Y(j,i) for every interval ofY(j,i) -X_{j}, and then finding the optimal value ofdp[j] can be reduced to simply querying both trees (you can do it in a single tree of course, but I'm saying two for simplicity).Of course,

Y(j,i) can change when we changei. We can fix this by updating our trees, removingjfrom both trees, calculating the new value ofY(j,i) -X_{j}, and adding it again. But wait, everyY(j,i) can changentimes, so this is even worse than if you simply do the loop.So let's exploit one property of

Y(j,i) mentioned by zeliboba -- namely that once two maximums become equal they become equal forever. Every timeY(j,i) changes, group ofkwithY(k,i) =Y(j,i) necessarily increases size. If this group becomes larger than , let's create separate trees specifically for this group, remove alljinside group from the global trees and add alljin group to these group trees.Now we have interesting property: whenever

Y(j,i) changes for one element in the group, it changes for all other elements of the group, so the order in the group tree remains the same. That means that group tree will never need to be updated again (unless a newjenters the group, in which case it should be added to the group tree). Whenever you're querying for the bestjfor a certaini, you now need to check the generic tree and all group trees for the optimal value.Complexity analysis: Because each change increases group size, each element

jchangesY(j,i) at most times before it enters a group of more than elements. When querying for the minimum value, we will need to query at most trees (general trees and group trees). So we can see both queries and updates are bound by .Cool solution, it is easier to implement, than what I've suggested.