I’m skipping Division 1 P300, because it can be solvable after carefully thinking/coding.
Division 1 P450
I would like to introduce a technique used to solve this problem. The technique is to apply a transformation (rotate the graph 45-degree clockwise) to the original graph. With the original graph, if we are at (0, 0) we can move to get any points that drop from the area above the blue lines. After applying the transformation, the claim stays true. So what is the maximum number of points we can get? Of course, we can only get the points that are in the 1st quadrant.
The transformation matrix is [[1, 1], [-1, 1]]. What can we do with this new graph? First, we can notice that if we are at (x, y), the next fruit position that we can get to must be (u, v), where u >= x, v >= y. This means an optimal sequence of pieces of fruits we get will be ascending by x-coordinates. We can think of this problem as a different problem that all the points stay still, but we are the one who moves right or up to collect the points. So let’s sort all the points by their x-coordinate first. Then we name a multiset to store y-cooridnates and loop through all the points in the ascending order and do the following:
- If the point
pis not in the 1st quadrant, we ignore. - We put
p.y(y-coordinate) into a multiset, then we remove the first element (if exists in the set) which is greater thanp.y. - After finish looping, the size of this set will be the maximum number of pieces of fruit we can get.
Why does this give us an optimal solution? Consider this example, suppose now our optimal sequence is (1, 1), (2, 3) (our multiset will be [1, 3]) and the next point is (4, 5). From (2, 3), we can get the fruit at (4, 5) next. So we can put this new point into our map. The other case is that the next point is (4, 2) (its y-coordinate is less than the current position’s). If we are at (2, 3), we cannot get the fruit at (4, 2). We need to pick either (4, 2) or (2, 3), but we can’t really tell which point we should go right now. What we know is that the number of piece of fruit will not increase. We choose to add 2 into our multiset and remove 3 because (4, 2) will allow more spaces we can go next. In other words, we pick (4, 2) as a ‘shadow’ of (2, 3). If sometimes later, we know that (2, 3) is not a good choice, this will be fine. At (4, 2), we can go to all the points we can go from (2, 3), so there is no harm to pick (4, 2) instead. But if (2, 3) is a good choice, we would already remove 3 (the y-coordinate of (2, 3)) from our set which is what we expect. It can be more clear if you draw some pictures of both cases.