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). So:

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.

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."


My Solution.