How are velocity vectors calculated when speed and change vector is given?

Question

This is related on an insanely hard geometry problem on Codeforces that I am struggling with:

RC Kaboom Show

The jist of the problem is as follows:

Given an infinite 2D field, you can place $n$ cars at any position so as they are not same as some other car's position.

You are also given a change vector $[d_x,d_y]$ which if you add it to the car's current position will result in the new changed position.

For example:

Initial position: $[3,0]$ + $[1,1]$ (Change vector) = $[4,1]$ (This is the new position of the car).

Pretty easy to understand so far.

Now is where things go haywire:

You are also given a speed $s$ for each car, along with its change vector. The car is suppose to move at this constant speed $s$. What does speed even mean in this context ?

Should I multiply the change vector with the speed ? In the solution the speed is actually put to use by calculating a separate velocity vector $[v_x,v_y]$. Technique for that is as follows:

1. Calculate $d_i$ as $\sqrt{(d_x)^2 + (d_y)^2}$. Please note that this would use the change vector for that particular car $i$.

One would think that is the distance between 2 points of a line, but I have no idea how that works here for by using the change vector. I mean the change vector does not represent the final position of the car, it just represents the change, thus I don't think $d$ is distance here.

2. $v_x = (d_x /d)s_i $
3. $v_x = (d_y /d)s_i $

So my question is simple - What on earth is going on here ? Is there method to this madness ?

Does this technique of calculating velocity vectors have a name, so I can study it ?

Do these problems fall under a type so maybe I can look at easier problems before this ?

Thanks.

Answer 1

Here's the actual definition from the link, with a couple of typos fixed and a change of variables for the direction:

To be formal, for each car $i$ ($1 \le i \le n$) you choose its initial position $(x_i,y_i)$ and a direction vector $(X_i,Y_i)$. Moreover, each car has a constant speed $s_i$ units per second. So after car $i$ is launched, it starts moving from $(x_i, y_i)$ in the direction $(X_i, Y_i)$ with constant speed $s_i$.

This means that only the direction of $(X_i , Y_i)$ affects the movement per time step, not its magnitude. The distance of each movement is specified solely by $s_i$.

In other words, the change in location per time step for car $i$ is $(\chi_i, \gamma_i)$, $$\left\lbrace ~ \begin{aligned} \chi_i &= \displaystyle s_i \frac{X_i}{\sqrt{X_i^2 + Y_i^2}} \\ \gamma_i &= \displaystyle s_i \frac{X_i}{\sqrt{X_i^2 + Y_i^2}} \\ \end{aligned} \right.$$ where the right side of $s_i$ is the direction vector $x$ and $y$ components scaled so that the length of the direction vector is $1$.

(In other words, if you have vector $(x, y)$, and you want to scale it to unit length, you get $(x / \sqrt{x^2 + y^2}, y / \sqrt{x^2 + y^2})$. Your assumption that the car change vector would be $(X_i, Y_i)$ is incorrect; the rest of the confusion stems from that. $(X_i, Y_i)$ only specifies the direction, not the "length" of each step.)

Does this technique of calculating velocity vectors have a name, so I can study it ?

It is common to use a vector to indicate direction, with its length (as long as nonzero!) irrelevant. In such cases, combined with speed as above, yields the velocity vector, which contains both direction and length.

So, this kind of construction, being given direction vector $(X_i, Y_i)$ and speed $s_i$, and constructing velocity vector $(\chi_i, \gamma_i)$ using the above, is actually rather common.

You encounter similar things in basic vector algebra and linear algebra, if you do for example 3D rotations and transforms. You use cross product between some two vectors (typically directions at different times) to find an axis vector; and many rotation methods require you to first normalize that axis vector to unit length in exactly the same way (well, without a "speed").

You could ask why not specify the direction using an unit vector in the first place, or why not specify the direction as an angle $\varphi$ counterclockwise from the positive $x$ axis (in which case $X_i = \cos\varphi$, and $Y_i = \sin\varphi$, and they form an unit vector, $X_i^2 + Y_i^2 = 1$). The answer to that is an unsatisfying "we must work with the input we get, not with the input we'd prefer". That, too, is very common.

---

In the problem, the input contains $x_i$, $y_i$, $X_i$, $Y_i$, and $s_i$ for $n$ cars ($i = 1, 2, \dots, n-1, n$ or $i = 0, 1, \dots, n-2, n-1$, whichever you prefer), and the user is to find their launching times $t_i \ge 0$ so that the first collision occurs as soon (at as small time $t$ as possible).

It is very important to realize that using the velocity vectors $(\chi_i, \gamma_i)$ calculated as above, at time $t$ the position of car $i$ is $$\left\lbrace ~ \begin{aligned} x_i^\prime &= \begin{cases} x_i, & t \le t_i \\ x_i + (t - t_i) \chi_i, & t \ge t_i \end{cases} \\ y_i^\prime &= \begin{cases} y_i, & t \le t_i \\ y_i + (t - t_i) \gamma_i, & t \ge t_i \end{cases} \\ \end{aligned} \right .$$ noting that none of these have to be integers, they can be reals (floating-point values) instead. (I couldn't think of any new $x$- and $y$-looking letters to use for the position coordinate variables, so I used the prime mark, $\,^\prime$, to indicate these are new variables; these read as "x-prime i" and "y-prime i", respectively.)

So, there are no steps in time here, really; a time "step" is just one unit of time.

Furthermore, the problem states a collision between car $i$ and car $k$ occurs at time $t$ if the coordinates differ by at most $10^{-6} = 0.000001$, i.e. $$\left\lbrace ~ \begin{aligned} \left\lvert x_i^\prime - x_k^\prime \right\rvert & \le 10^{-6} \\ \left\lvert y_i^\prime - y_k^\prime \right\rvert & \le 10^{-6} \\ \end{aligned} \right.$$ but you are better off using a slightly tighter limit, distance between the coordinates less than $10^{-6}$, or better yet, squared distance between the coordinates less than $(10^{-6})^2 = 10^{-12}$.

Therefore, the actual problem is to find $i$, $k$, $t_i$, and $t_k$, such that at the smallest $t$, $t \ge 0$, $$(x_i^\prime - x_k^\prime)^2 + (y_i^\prime - y_k^\prime)^2 \le 10^{-12}$$

Hint:

One of the cars must start at time $t = 0$, the other can start at the same time or later. If we pick $t_i = 0$, and solve for cars $i$ and $k$ having the same coordinates ($x_i^\prime = x_k^\prime$, $y_i^\prime = x_k^\prime$) at time $t$ for $t$ and $t_k$, we get $$\left\lbrace ~ \begin{aligned} \Delta &= \chi_k \gamma_i - \chi_i \gamma_k \\ t &= \displaystyle \frac{ \gamma_k ( x_i - x_k ) - \chi_k ( y_i - y_k ) }{\Delta} \\ t_k &= \displaystyle \frac{ (\gamma_k - \gamma_i)(x_i - x_k) - (\chi_k - \chi_i)(y_i - y_k) }{\Delta} \\ \end{aligned} \right.$$ where $\Delta = 0$ if the two cars cannot intersect, and $t \ge t_k$ for the coordinates of car $k$ to be valid.

Collision between stationary car $k$ and car $i$ started at $t_i = 0$ occurs at $t = (x_k - x_i) / \chi_i$ if $t \ge 0$ and $\lvert y_i + t \gamma_i - y_k \rvert \le 10^{-6}$; or at $t = (y_k - y_i) / \gamma_i$ if $t \ge 0$ and $\lvert x_i + t \chi_i - x_k \rvert \le 10^{-6}$, whichever gives the smaller nonnegative $t$, using the rules of this problem.

---

I recommend you install yourself the free and open source computer algebra system Maxima. I found the above solutions using the text-only interface, via

display2d:false;

solve([ x_i + t*chi_i = x_k + (t - t_k)*chi_k,
        y_i + t*gamma_i = y_k + (t - t_k)*gamma_k ], [ t, t_k ]);

solve( x_i + t*chi_i = x_k, t);

and it gives

[[t = -(chi_k*(y_i-y_k)+gamma_k*x_k-gamma_k*x_i)
    /(chi_k*gamma_i-chi_i*gamma_k),
  t_k = -(chi_i*(y_k-y_i)+chi_k*(y_i-y_k)+(gamma_k-gamma_i)*x_k
                         +(gamma_i-gamma_k)*x_i)
      /(chi_k*gamma_i-chi_i*gamma_k)]]

[t = (x_k-x_i)/chi_i]

It has a nice GUI too, but I do not often use that, as I have a very old and slow computer, and prefer the text interface. There are others like Maxima too, like Sagemath.

Having such math tools is very important for every programmer, because while fine-tuning the code can give you a few percent increase in efficiency, using a better algorithm can make the program an order of magnitude (10×) more efficient (in run time and/or memory use).

Good luck with solving the problem!