SRM 729, D1, 450-Pointer (FrogSquare)

James S. Plank

Tue Oct 2 14:23:43 EDT 2018
Revised: Mon Oct 11 15:44:58 EDT 2021

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
tests.sh for testing yourself.
answers.txt for testing yourself.
Problem Given in Topcoder: February, 2018
Competitors who opened the problem: 220
Competitors who submitted a solution: 195
Number of correct solutions: 42
Accuracy (percentage correct vs those who opened): 19.1
Accuracy (percentage correct vs those who submitted): 21.5
Average Correct Time: 27:18

In case topcoder's servers are down

Here's a summary of the problem:

A frog is on an n X n grid, which is zero indexed. n ≤ 1000.
The frog is on cell (sx,sy) and wants to hop to cell (tx,ty).
The frog may only make hops that are at least of Euclidean length d, and the frog may only hop to cells that are integer indexed, and in the grid.
d ≤ 2000.
What is the fewest number of hops that the frog has to make. Return -1 if it is impossible.

Examples

#    n     d     sx     sy     tx     ty    answer  Comments
------------------------------------------------------------------------------------
0   100    10    0      0      3      4       2     Jump to (99,99) and then to (4,2)
1   100     5    0      0      3      4       1     sqrt(4*4+3*3) = 5
2   100   200    0      0      3      4      -1     Can't jump anywhere from 0,0
3    10     7    4      4      5      5       3
4     1     1    0      0      0      0       0

Testing yourself

Standard -- see "Cryptography" if you need to see the workflow.

Hints

Shortest path through an unweighted graph may be implemented with BFS, and is O(E). The problem here is that E can be 10¹². Here's the realization that allowed me to solve the problem:

If you don't go directly from start to finish, there is a shortest path that only involves nodes on the edges of the square.

Now you only have 4000 potential nodes, and your BFS can complete in time. If you're presenting this problem in CS494, I want you to prove the realization (and of course illustrate it very nicely graphically). That's how I solved it when I did the problem for topcoder. I constructed the graph on the fly, while I did the BFS.

I'll also state that if you're solving this in a programming competition like Topcoder, stop here and don't think about it any more. The thinking is more likely to get you into trouble, and this solution is fast enough.

However, if you're presenting this for CS494/594, read on:

But There's More

You can break it into cases and solve it in O(1) time:

Identify when the answer is 0. You can do that easily in O(1) time.
Identify when the answer is 1. You can do that also easily in O(1) time.
Identify when the answer is 2. You can do that by calculating the set of border points that are reachable by s, and then the set of border points that are reachable by t, and calculating their intersection. If it is non-empty, then the answer is two. Although the number of points in these sets is O(n) (or even O(n²)), you can represent and calculate them in O(1). How? Do intersection with a line and a circle, four times. There are four potential points that matter on each line.
We're now in the place where the two sets of border points don't intersect. You'll note that each set contains at least one point in a corner of the grid. Let's label the corner points A, B, C and D, and their connecting lines AB, BC, CD and DA. So now, there are four cases:
1. Without loss of generality, suppose A is in the s set and C is in the t set. Then you can hop from A to C, guaranteed. The answer is three.
2. We're left with A in the s set and B in the t set. There are only four points that matter -- A, B, the point on AD in the s set that is closest to D (call this point E), and the point on BC in the t set that is closest to C (call this point F). If you can hop from A to F or B to E, then the answer is three. You can calculate all of these in O(1) time.
3. Now, there's one last hope -- You can hop from A to the midpoint of CD to B. (If there are two midpoints because n is even, then choose either). If that's possible, then your answer is four.
4. Otherwise, it's impossible.
If s or t contain more than two corner points, you'll have to do those calculations separately for each unique pair of corner points in s and t.

Thanks to CS594 students Adam Tutko, who first saw an O(1) solution, and to Everett Rush for helping me think more about the solution.