SRM 623, D2, 250-Pointer (CatchTheBeatEasy)

James S. Plank

Mon Aug 29 16:37:09 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: June, 2014
Competitors who opened the problem: 609
Competitors who submitted a solution: 496
Number of correct solutions: 282
Accuracy (percentage correct vs those who opened): 46.31%
Average Correct Time: 24 minutes, 5 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

You are playing a video game which works in discrete 1-second time steps.
At the start of the game, you are at the point (0,0), and there is a collection of fruit at various (x,y) points above you.
The fruit is given to you in two vectors x and y, which are the same size. Fruit i starting location is in (x[i], y[i]).
At each time step, the fruit will move one point lower -- (x,y) becomes (x,y-1).
You may only move horizontally, one unit per time step. In other words, you (x,0) may become (x-1,0), (x,0) or (x+1,0).
You can "catch" fruit if you are at the fruit's x position when the fruit's y position becomes zero.
Your goal is to catch all of the fruit. If you can do this, return the string "Able to catch". If you cannot, return the string "Not able to catch".
Although the topcoder constraints limit you to 50 fruit, I'm bumping that up to 10,000.
The fruits' x locations will be between -1,000,000 and 1,000,000.
The fruits' y locations will be between 0 and 100,000.

The examples

Example 0:

x = {-1, 1, 0}
y = {1, 3, 4}
Returns: "Able to catch"

Example 1:

x = {-3}
y = {2}
Returns: "Not able to catch"

Example 2:

x = {-1, 1, 0}
y = {1, 2, 4}
Returns: "Not able to catch"

Example 3:

 
x = {0, -1, 1}
y = {9, 1, 3}
Returns: "Able to catch"

Example 4:

 
x = {70,-108,52,-70,84,-29,66,-33}
y = {141,299,402,280,28,363,427,232}
Returns: "Not able to catch"

Example 5:

 
x = {-175,-28,-207,-29,-43,-183,-175,-112,-183,-31,-25,-66,-114,-116,-66}
y = {320,107,379,72,126,445,318,255,445,62,52,184,247,245,185}
Returns: "Able to catch"

Example 6:

{0,0,0,0}
{0,0,0,0}
Returns: "Able to catch"

Testing yourself

Like the Cryptography Problem, I have a shell script tests.sh, that you can use to test your program. When you run tests.sh, your answer should be identical to answers.txt, and the running time should be less than a second, total (mine was 0.67 seconds).

Hints

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:

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

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