SRM 623, D2, 250-Pointer (CatchTheBeatEasy)
James S. Plank
Mon Aug 29 16:37:09 EDT 2016
This problem is all about using the right data structure for the job, and I can only
imagine that the high number of incorrect answers comes from the fact that the programmers
were not comfortable with multimaps. At least, that's my best guess. So, this will be
a good problem for you if you are learning maps/multimaps.
Suppose you are
at the starting point. Which candy do you have to get next? It has to be the lowest
one. So you move to the x value of the lowest one, if you can. At that point,
you care about the next lowest one, and so on.
Let's walk example 0. The candies are at (-1,1), (1,3) and (0,4).
Solving the problem works exactly in this manner. You first need to arrange the candies
in increasing order of y values. To do this, insert the points into a multimap.
Why a multimap? Because there may points with duplicate y values. When you insert
a point, make the y value the first part of the entry, make the
x value the second part.
- You start at (0,0). You care about the lowest candy, which is (-1,1).
- Your x distance to the candy is 1, as is the y distance. That means that
you can move to x=-1 in time to get the candy.
- You are now at (-1,1). You care about the next lowest candy, which is (1,3).
- Your x distance to the candy is 2, and the y distance is also 2.
That means that you can move to x=1 in time to get the candy.
- You are now at (1,3). You care about the next lowest candy, which is (0,4).
- Your x distance to the candy is 1, and the y distance is also 1.
That means that you can move to x=0 in time to get the candy.
- You're done, so you can return "Able to catch."
Now, simulate the game. Let's call your current x value cx, and your
current y value cy. You'll start with both of these equal to zero.
Now, you traverse the multimap. Calculate
your x distance from the point in the multimap to cx and
your y distance from the point in the multimap to cy. If the x distance
is greater than the y distance, then you're done -- you are "Not able to catch."
Otherwise, update cx and cy, and continue. If you reach the end of the
multimap, you can return "Able to catch."
Here's a picture of example 4, which shows all of the points that make the
answer "Not able to catch."