You have $$$n+m$$$ points: ($$$x_i$$$, $$$y_i$$$, $$$\text{val}_i$$$). Each point satisfies $$$0 \le x_i \lt n$$$ and $$$0 \le y_i \lt m$$$. $$$\text{val}_i$$$ can be anything from $$$-10^9$$$ to $$$10^9$$$. You are at point $$$(0, 0)$$$ and you want to get to point $$$(n, m)$$$ maximizing your score. You get $$$\text{val}_i$$$ points if the path you go through contains point $$$i$$$ 'below' it. What is the maximum obtainable score?
For further clarification, by a point being 'below' a path, I mean: suppose your path was $$$(0, 0) \rightarrow (x_1, y_1) \rightarrow ... (x_k, y_k) \rightarrow (n, m)$$$. A point $$$(x', y')$$$ will be below this path if there exists a point in the path such that $$$x_i = x'$$$ and $$$y' \le y_i$$$.
Or refer to this image. The red points are below the path and the blue points are above it.
Naive dynamic programming on a grid is an option, of course, but this is at least $$$O(nm)$$$. In this problem, $$$n, m \le 1,000,000$$$ (however, there is a subtask with $$$n, m \le 200,000$$$). I'm looking for a solution with better time complexity, maybe something like $$$O((n + m) \log(n + m))$$$ using some kind of sweepline with segment trees. However, I can't figure out how to do this. Can somebody help?
Do you have a link to the problem? I would like to help, but I am afraid of making some suggestion without being able to test my code :)
This problem is the result of a reduction from JOISC 2019 — Two Dishes. Here's the link: https://oj.uz/problem/view/JOI19_dishes.
Here's a comment by ainta explaining how the reduction works (although you may not want to see this if you wanna try solving the original problem yourself!)
I haven't done the problem because the reduction seems kinda long, but I thought the following implementation:
Sort the points by $$$(x,y)$$$ coordinates. For implementation simplicity, assume there is only one point at each $$$x$$$ coordinate.
Let $$$dp[h]$$$ be the greatest value you can get by currently being at height $$$h$$$. At the start $$$dp[h]$$$ = 0 for every $$$h$$$. Then, at point $$$i$$$:
$$$ dp[y_i] = val_i + max_{h \leq y_i} dp[h] $$$
Also you must forcefully pick the point $$$i$$$ for every height $$$ \gt y_i$$$:
$$$ dp[h] $$$ += $$$ val_i $$$ for $$$h \gt y_i$$$.
You can solve this with a Lazy segtree. I thought about something like
Where the merge operation of the segtree is the
maxoperation and the update issum. Hope this made sense.I am not 100% confident this works by the way, sorry ;-; . Also you have to handle points at same $$$ x_i $$$.
Maybe sorting by $$$(x, -y)$$$ solves the multiple points in the same $$$x$$$ coordinate problem.
Finally the answer is
segTree.query(0,MAX_M).I’m pretty sure this is correct! Looks quite similar to what tfg is doing.
If you think of the dp transition as 2 steps then it's easy to see how to optimize the problem:
dp[i][j] = max score at x = i with y <= j
First step: dp[i][j] = dp[i-1][j] + a[i][j]. a[i][j] is the sum of scores of points at x = i and y <= j.
Second step: dp[i][j] = max(dp[i][j], dp[i][j-1]). We take the prefix max after doing the sum above.
To do the first step we can simply do suffix sum updates. To do the second update we can do something like while there's some dp[i][j] < dp[i][j-1], we do max range update for the suffix. It's easy to see that the points that that will happen are exactly where we do the suffix sum updates. A segment tree can easily support operations of range sum update, range max update, range max query (no seg tree beats necessary if the query is just range max). I think it's also doable with a single map that represents the difference array, for negative values you nullify positive values ahead of it until it gets to 0 and it works out.
I got it, thanks a lot! Yeah, after the range max operations you get a non-decreasing array, so the points where you update it will exactly be the points where the value is the maximum. Then you can use lazy propagation to range set to max, and at the end you just need to query the max.
Hey, so I did end up solving the original question with this:
In your comment, you mentioned that segment tree beats is not necessary for just this much. However, I can't see how I'd code a range
chmax()without beats. It'd be great if you could link me to an article or resource that does this. Thanks a lot.I might write a blog about this just to make it cleaner but there's not much to it. My standard way of doing this is looking at the lazy update as a tuple and doing the updates in sequence. Let's say the lazy update is (MAX, SUM) so we do a[i] = max(MAX, a[i]) + SUM. When doing (a, b) followed by (c, d) we have x = max(c, max(x, a) + b) + d = max(x + b, a + b, c) + d = max(x, a, c — b) + b + d so we can summarize it with (max(a, c — b), b + d). As an exercise I suggest trying to figure out how it works for (SUM, MAX) which iirc also works.
For $$$(\text{SUM}, \text{MAX})$$$, you have $$$x = \max(x + SUM, MAX)$$$. Can two operations be composed? Consider $$$(a, b)$$$ then $$$(c, d)$$$. This is $$$x = \max(\max(x + a, b) + c, d) = \max(\max(x + a + c, b + c), d) = \max(x + [a + c], \max(b + c, d))$$$, which is the operation $$$(a + c, \max(b + c, d))$$$.
Is that correct?
Would you also need to compose $$$(\text{SUM}, \text{MAX})$$$ with $$$(\text{MAX}, \text{SUM})$$$? All $$$4$$$ cases? I'm assuming for updates, you'll use $$$(x, -\infty)$$$ for
+=and $$$(x,0)$$$ formax=.Edit: there was a mistake I made that you corrected.
Slightly wrong, it should be (a+c, max(b+c, d)). You don't need to compose (SUM, MAX) with (MAX, SUM), just define one order and keep it like that in the code. You should use (x, -inf) for +=x and (0, x) for max=x for (SUM, MAX). But ig you could convert (SUM, MAX) to (MAX, SUM). max(MAX, x+SUM) = max(MAX-SUM, x) + SUM.
Thank you so much, that worked spectacularly. For what it's worth, I definitely think you should make a blog post on this, doesn't seem like it's a super well-known trick (although maybe I'm wrong, and this could just be my lack of experience showing)
Can someone suggest me good resources to study graphs, trees and dp?