I will skip Div1-300, because it can be solvable after carefully thinking/coding.
Div1-450
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 1stquadrant.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 p is not in the 1stquadrant, we ignore (continue).
- We put p.y (y-coordinate) into a multiset, then we remove the first element (if exists in the set) which is greater than p.y.
- After finish looping, the size of this set will be the maximum number of pieces of fruit we can get.
Here are the problems: SRM 623 | Problems
No comments:
Post a Comment