4
$\begingroup$

I am interested resolving a programming challenge problem, but I'm struggling obtaining an efficient solution.

Consider yourself as a point located on the origin $(0,0)$ of an infinite two-dimensional flat world. There are $n$ sea waves surrounding you, each one modeled as a circle with center $(x_i, y_i)$, initial radius $r_i$, and propagation speed $s_i$, so that the radius of wave $i$ as a function of the time $t ≥ 0$ is $r_i + s_i \cdot t$. You choose any fixed direction and run “forever” at speed $p$. Will you be able to scape?

Some helpful restrictions given as assumptions are provided:

  • $1 ≤ p ≤ 1000$
  • $3 ≤ n ≤ 10^4$ [the number of circles $c_i$]
  • $−1000 ≤ x_i,\;y_i ≤ 1000$
  • $1 ≤ r_i ≤ 1000$
  • $0 ≤ s_i < p$
  • Except for $n$, all numbers are real, with at most three digits after the decimal point.
  • Initially, you are strictly outside all the waves.
  • There are not precision errors.

My solution so far is quite simple (I have programmed it in C++):

  • Each "fixed direction" to run forever is solely determined by the angle of that line with the X axis, namely $0 \leq \theta < 2 \pi$.
  • For each $\theta \in [0, 0.001, 0.002, \dots, 2\pi)$:
    • Recall that the map is within the square $[-1000, -1000]$ to $[1000, 1000]$, and the furthest distance between $(0,0)$ and any point in the map has distance $1000\sqrt{2}$. We advance at $p$ speed, so at most we will compute $1000\sqrt{2}/p \approx 1414/p$ iterations.
    • For each $t \in [0, 0.001, 0.002, \dots, 1414/p]$:
      • My position at time $t$ in line $\theta$ is $pos_t = (\cos \theta \cdot t \cdot p, \sin \theta \cdot t \cdot p)$.
      • Check whether $pos_t$ is inside any sea wave at moment $t$. Basically, check if the distance between $pos_t$ and the center of each circle is less than that circle's radius at moment $t$, namely $r_i + s_i \cdot t$. If so, bad luck; we're done with this $\theta$ and we continue the search.
      • If not, try with next $t$.
    • If no intersection is found after iterating all $t$s, then you will be able to scape (through line with angle $\theta$).
  • If all $\theta$s got some intersections, then we are not able to scape.

This solution has cost $\Theta(6000 \times 1400 \times n)$, which is impractical for $n \leq 10^4$. Informally, and without being precise, the multiplicative term may be $O(n^3)$ if $n \leq 10^4$ is considered. Plus, it may not be correct, as I am assuming that $\Delta t = 0.001$ is fine; same for the angle.


I have thought about another idea, which is reducing systematically $\theta$. For instance, let's imagine that we've got a circle at $C = (5, 5)$ (in the line of $\theta = \pi/2$) with some small radius. From the beginning, we know that angles $\theta = \pi/2 \pm \alpha$ will never be an option, being $\alpha$ determined by tangent lines from $(0, 0)$ to $C$ and $t$; the more time passes, the higher $\alpha$ will be and thus the wider will be this range of restricted angles.

So, at moment $t$ we have a set of ranges of possible $\theta$s, and that range is reduced as long as $t$ increases (unless all waves have speed 0, for sure).

But how to continue from there? I see the same problems as with my implementation: determining $\Delta t$ and $\Delta \theta$.


I ask for your help to find a better algorithm. I suspect that there may be an algorithm that is just $O(k n)$ or $O(k \cdot n \log n)$ with $k$ being reasonably small.

$\endgroup$
4
$\begingroup$

The solution outline:

Step 1. Verify, that all the initial (at the moment $t=0$) wave circles don't contain your starting point $(0,0)$. If yes, then continue - otherwise exit, no escape.

Step 2. For each wave circle $W_i$ you need to find an escape sector - the range of directions, where the escape is guaranteed.

Imagine a circle of your possible positions at moment $t$ with center in $(0,0)$ and radius $pt$ - we'll call it the circle $C$. Let's consider what will happen with circles $C$ and $W_i$ with time. Originally (when $t=0$) the circle $C$ is just a point at $(0,0)$. Then, with time increasing, the expanding circle $C$ will at first touch the expanding circle $W_i$ at a single point, then intersect it at two points. Moving further, at some point of time the expanding circle $C$ will touch the circle $W_i$ again at a single point, then it will contain the circle $W_i$ completely (because $p \gt s_i$).

Two intersection points between circles $C$ and $W_i$ define a no-escape sector. This sector angle $\alpha$ grows from zero to some maximal value and then decreases to zero again. Cosine of this half-angle at the moment of time $t$ can be found from the triangle with all known sides:

$$\cos(\frac {\alpha} {2}) = \frac {(pt)^2+d_i^2-(r_i+s_it)^2} {2d_ipt}$$

where $d_i = \sqrt{x_i^2+y_i^2}$.

You need to find positions of intersection points, which will give you this maximal angle value. In order to do that you can take first derivative of the non-escape sector half-angle by time and set it to zero - that will give you the moment of time when the non-escape sector is maximally wide. This moment of time $T_i$ will be:

$$T_i = \sqrt{\frac{d_i^2-r_i^2}{p^2-s_i^2}}$$

Knowing the non-escape sector you'll easily find the escape sector.

Step 3. If intersection of all the escape sectors is non-empty, then the escape is possible.

The algorithm time is obviously $O(n)$.

$\endgroup$
  • $\begingroup$ Thank you so much again. Tomorrow I give it a look. $\endgroup$ – JnxF Aug 15 at 2:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.