CLTNIS - Editorial

editorial
, , , , ,
1

PROBLEM LINK

Practice
Contest

Author and Editorialist: Soumik Sarkar
Tester: Avijit Agarwal

DIFFICULTY

Easy-Medium… or so we thought.

PREREQUISITES

Some maths, geometry

PROBLEM

A ball moves in an n-dimensional space with fixed velocity. Given starting position of both ball and Chef, find the minimum velocity required by Chef to intercept the ball before it leaves a given region.

EXPLANATION

Using a straight path is better than a curved path. Using a fixed speed is better than changing speeds. So it is always optimal for Chef to move with constant velocity (speed and direction) starting at t = 0 until he meets the ball at some point.

First, if the position of Chef and the ball already coincide, output should be 0.
If not, we proceed to calculate t_{exit}, the time when the ball moves out of Chef’s court. This is can be done by iterating over each dimension i and checking when the ball moves out the bounds (0 or l_i) of this dimension. The minimum over all dimensions gives t_{exit}.

Beyond this, there can be multiple solutions for this problem. Tester’s solution is easier and requires a bit of geometry and the right perspective. Author’s solution is more analytical and does not require geometry.

Tester’s solution

The problem has only three points of interest: the ball’s position at t = 0, Chef’s position at t = 0, and the ball’s position at t = t_{exit}. So, these points can transferred to a plane where their relative positions are preserved, reducing the problem from n dimensions to 2 dimensions.

Let us denote the ball’s initial position as A, Chef’s initial position as B and the ball’s position at t_{exit} as C. The ball’s velocity is v and Chef’s is u.

Consider the illustration above. When placed as such with both A and B on the X-axis, it is clear that in order to meet sometime at t > 0 it is necessary that u_y = v_y. But what value of u_x should be chosen? Any value in (-\infty, v_x) will allow them to meet eventually. But to minimize the speed, of course we should choose u_x = 0. Thus Chef’s minimum speed is given by v_y = v \sin \theta.

But, this is the answer only when the point D is encountered by the ball before C since the ball has left the court after position C. If C appears before D, Chef must meet the ball at C instead.

A third case arises when the ball is not moving towards Chef, which means v_x \le 0. In this case too, it can be shown that it is best to meet the ball at the exit point C.

Author’s solution

Consider each dimension separately. In the dimension i, the position of the ball after time t is given by b_i + v_i \cdot t. Let the component of Chef’s chosen velocity along dimesnion i be u_i. Then, if Chef’s position coincides with the ball at time t,

c_i + u_i \cdot t = b_i + v_i \cdot t \\ u_i = \frac{b_i - c_i}{t} + v_i

Speed of Chef is given by the magnitude of Chef’s velocity, which is

\begin{aligned} |u| &= \sqrt{u_1^2 + u_2^2 + u_3^2 + \dots + u_n^2} = \sqrt{\sum_{i=1}^n u_i^2}\\ &= \sqrt{\frac{\sum_{i=1}^n (b_i - c_i)^2}{t^2} + 2 \cdot \frac{\sum_{i=1}^n (b_i - c_i) \cdot v_i}{t} + \sum_{i=1}^n v_i^2} \\ &= \sqrt{\frac{p}{t^2} + \frac{q}{t} + r} \end{aligned}

Here p, r > 0. So, Chef’s required speed can be expressed as a function of time. This function gives a curve for t \ge 0 which is monotonic decreasing when q \ge 0 and unimodal with a single minima for q < 0. So, ternary search can be applied to find the minima in the range [0, t_{exit}]. Alternately, the derivative of the function can also be analyzed to get the minima, which is at -2 \frac{p}{q}.
You can play with the function on Desmos.

Time complexity is \mathcal{O}(n) using geometric approach or getting minima of the cost function directly. Using ternary search it is \mathcal{O}(n + \log \frac{t_{exit}}{ \varepsilon}) where \varepsilon is the desired precision in time (around 10^{-8} will work) and t_{exit} \le 50.

AUTHOR’S AND TESTER’S SOLUTIONS

Author’s solution can be found here
Tester’s solution can be found here.

3 Likes
2

https://www.codechef.com/viewsolution/23248822

can anyone tell what’s wrong in the above solution?

3

You should explain what you are trying to do here.

4

@meooow in your solution when using the direct formula -2 \frac{p}{q} you evaluate the expression inside the square root and if that comes out to be negative, you take u to be 0 instead. That thing is not clear to me as the function must not have been defined in that case but you take that to be 0. Here when q is largely negative, the expression inside the square root must not be defined, then how did you take the answer as 0 in that case ?

5

Remember that |u| is the magnitude of a vector, the square root of the sum of squares of its components. Hence it definitely exists as a real number. The values of p, q, r in your example will never occur.
I found that in a certain case where I expect 0, func(t_opt) instead returns a small negative number (like 1e-14 which I cannot use sqrt on) due to precision issues of floating point. This is why I used max(0, func(t_opt)).

2 Likes
6

Alright, so now I get why was max(0, func(t\_opt)) being used since excluding this statement was giving WA, so I thought that the expression inside the square root might be -ve.Thanks a lot. :slight_smile:

1 Like
7

2
10
10