# VSN has a closed form solution

I’m not sure to class this as an editorial or whatever, but it’s interesting. A well spent few hours digging into this.

I figured during the competition that VSN should have a closed form expression, a quadratic equation in something like 13 variables. It turns out that that is indeed true. After some mathematica magic I derived a “beautiful” formula that solved the problem. As mentioned in another question python3 has TLE problems with the binary search method, with the closed form solution python3 actually passes, albeit with a struggle: 18916971.

The formula in python form is

2*cy**2*dx*px + 2*cz**2*dx*px - 2*cx*cy*dy*px - 2*cx*cz*dz*px +
2*cy*dy*px**2 + 2*cz*dz*px**2 - 2*cx*cy*dx*py + 2*cx**2*dy*py +
2*cz**2*dy*py - 2*cy*cz*dz*py - 2*cy*dx*px*py - 2*cx*dy*px*py +
2*cx*dx*py**2 + 2*cz*dz*py**2 - 2*cx*cz*dx*pz - 2*cy*cz*dy*pz +
2*cx**2*dz*pz + 2*cy**2*dz*pz - 2*cz*dx*px*pz - 2*cx*dz*px*pz -
2*cz*dy*py*pz - 2*cy*dz*py*pz + 2*cx*dx*pz**2 + 2*cy*dy*pz**2 -
2*cy**2*dx*qx - 2*cz**2*dx*qx + 2*cx*cy*dy*qx + 2*cx*cz*dz*qx -
2*cy*dy*px*qx - 2*cz*dz*px*qx + 4*cy*dx*py*qx - 2*cx*dy*py*qx +
2*dy*px*py*qx - 2*dx*py**2*qx + 4*cz*dx*pz*qx - 2*cx*dz*pz*qx +
2*dz*px*pz*qx - 2*dx*pz**2*qx + 2*cx*cy*dx*qy - 2*cx**2*dy*qy -
2*cz**2*dy*qy + 2*cy*cz*dz*qy - 2*cy*dx*px*qy + 4*cx*dy*px*qy -
2*dy*px**2*qy - 2*cx*dx*py*qy - 2*cz*dz*py*qy + 2*dx*px*py*qy +
4*cz*dy*pz*qy - 2*cy*dz*pz*qy + 2*dz*py*pz*qy - 2*dy*pz**2*qy +
2*cx*cz*dx*qz + 2*cy*cz*dy*qz - 2*cx**2*dz*qz - 2*cy**2*dz*qz -
2*cz*dx*px*qz + 4*cx*dz*px*qz - 2*dz*px**2*qz - 2*cz*dy*py*qz +
4*cy*dz*py*qz - 2*dz*py**2*qz - 2*cx*dx*pz*qz - 2*cy*dy*pz*qz +
2*dx*px*pz*qz + 2*dy*py*pz*qz - 2*dx*px*r**2  - 2*dy*py*r**2  -
2*dz*pz*r**2  + 2*dx*qx*r**2  + 2*dy*qy*r**2  + 2*dz*qz*r**2  +
sqrt((-2*cy**2*dx*px - 2*cz**2*dx*px + 2*cx*cy*dy*px + 2*cx*cz*dz*px -
2*cy*dy*px**2 - 2*cz*dz*px**2 + 2*cx*cy*dx*py - 2*cx**2*dy*py -
2*cz**2*dy*py + 2*cy*cz*dz*py + 2*cy*dx*px*py + 2*cx*dy*px*py -
2*cx*dx*py**2 - 2*cz*dz*py**2 + 2*cx*cz*dx*pz + 2*cy*cz*dy*pz -
2*cx**2*dz*pz - 2*cy**2*dz*pz + 2*cz*dx*px*pz + 2*cx*dz*px*pz +
2*cz*dy*py*pz + 2*cy*dz*py*pz - 2*cx*dx*pz**2 - 2*cy*dy*pz**2 +
2*cy**2*dx*qx + 2*cz**2*dx*qx - 2*cx*cy*dy*qx - 2*cx*cz*dz*qx +
2*cy*dy*px*qx + 2*cz*dz*px*qx - 4*cy*dx*py*qx + 2*cx*dy*py*qx -
2*dy*px*py*qx + 2*dx*py**2*qx - 4*cz*dx*pz*qx + 2*cx*dz*pz*qx -
2*dz*px*pz*qx + 2*dx*pz**2*qx - 2*cx*cy*dx*qy + 2*cx**2*dy*qy +
2*cz**2*dy*qy - 2*cy*cz*dz*qy + 2*cy*dx*px*qy - 4*cx*dy*px*qy +
2*dy*px**2*qy + 2*cx*dx*py*qy + 2*cz*dz*py*qy - 2*dx*px*py*qy -
4*cz*dy*pz*qy + 2*cy*dz*pz*qy - 2*dz*py*pz*qy + 2*dy*pz**2*qy -
2*cx*cz*dx*qz - 2*cy*cz*dy*qz + 2*cx**2*dz*qz + 2*cy**2*dz*qz +
2*cz*dx*px*qz - 4*cx*dz*px*qz + 2*dz*px**2*qz + 2*cz*dy*py*qz -
4*cy*dz*py*qz + 2*dz*py**2*qz + 2*cx*dx*pz*qz + 2*cy*dy*pz*qz -
2*dx*px*pz*qz - 2*dy*py*pz*qz + 2*dx*px*r**2 + 2*dy*py*r**2 +
2*dz*pz*r**2 - 2*dx*qx*r**2 - 2*dy*qy*r**2 - 2*dz*qz*r**2)**2 -
4*(cy**2*dx**2 + cz**2*dx**2 - 2*cx*cy*dx*dy + cx**2*dy**2 +
cz**2*dy**2 - 2*cx*cz*dx*dz - 2*cy*cz*dy*dz + cx**2*dz**2 +
cy**2*dz**2 + 2*cy*dx*dy*px - 2*cx*dy**2*px + 2*cz*dx*dz*px -
2*cx*dz**2*px + dy**2*px**2 + dz**2*px**2 - 2*cy*dx**2*py +
2*cx*dx*dy*py + 2*cz*dy*dz*py - 2*cy*dz**2*py - 2*dx*dy*px*py +
dx**2*py**2 + dz**2*py**2 - 2*cz*dx**2*pz - 2*cz*dy**2*pz +
2*cx*dx*dz*pz + 2*cy*dy*dz*pz - 2*dx*dz*px*pz - 2*dy*dz*py*pz +
dx**2*pz**2 + dy**2*pz**2 - dx**2*r**2 - dy**2*r**2 - dz**2*r**2)*
(cy**2*px**2 + cz**2*px**2 - 2*cx*cy*px*py + cx**2*py**2 +
cz**2*py**2 - 2*cx*cz*px*pz - 2*cy*cz*py*pz + cx**2*pz**2 +
cy**2*pz**2 - 2*cy**2*px*qx - 2*cz**2*px*qx + 2*cx*cy*py*qx +
2*cy*px*py*qx - 2*cx*py**2*qx + 2*cx*cz*pz*qx + 2*cz*px*pz*qx -
2*cx*pz**2*qx + cy**2*qx**2 + cz**2*qx**2 - 2*cy*py*qx**2 +
py**2*qx**2 - 2*cz*pz*qx**2 + pz**2*qx**2 + 2*cx*cy*px*qy -
2*cy*px**2*qy - 2*cx**2*py*qy - 2*cz**2*py*qy + 2*cx*px*py*qy +
2*cy*cz*pz*qy + 2*cz*py*pz*qy - 2*cy*pz**2*qy - 2*cx*cy*qx*qy +
2*cy*px*qx*qy + 2*cx*py*qx*qy - 2*px*py*qx*qy + cx**2*qy**2 +
cz**2*qy**2 - 2*cx*px*qy**2 + px**2*qy**2 - 2*cz*pz*qy**2 +
pz**2*qy**2 + 2*cx*cz*px*qz - 2*cz*px**2*qz + 2*cy*cz*py*qz -
2*cz*py**2*qz - 2*cx**2*pz*qz - 2*cy**2*pz*qz + 2*cx*px*pz*qz +
2*cy*py*pz*qz - 2*cx*cz*qx*qz + 2*cz*px*qx*qz + 2*cx*pz*qx*qz -
2*px*pz*qx*qz - 2*cy*cz*qy*qz + 2*cz*py*qy*qz + 2*cy*pz*qy*qz -
2*py*pz*qy*qz + cx**2*qz**2 + cy**2*qz**2 - 2*cx*px*qz**2 +
px**2*qz**2 - 2*cy*py*qz**2 + py**2*qz**2 - px**2*r**2 -
py**2*r**2 - pz**2*r**2 + 2*px*qx*r**2 - qx**2*r**2 +
2*py*qy*r**2 - qy**2*r**2 + 2*pz*qz*r**2 - qz**2*r**2)))
/
(2*(cy**2*dx**2 + cz**2*dx**2 - 2*cx*cy*dx*dy + cx**2*dy**2 +
cz**2*dy**2 - 2*cx*cz*dx*dz - 2*cy*cz*dy*dz + cx**2*dz**2 +
cy**2*dz**2 + 2*cy*dx*dy*px - 2*cx*dy**2*px + 2*cz*dx*dz*px -
2*cx*dz**2*px + dy**2*px**2 + dz**2*px**2 - 2*cy*dx**2*py +
2*cx*dx*dy*py + 2*cz*dy*dz*py - 2*cy*dz**2*py - 2*dx*dy*px*py +
dx**2*py**2 + dz**2*py**2 - 2*cz*dx**2*pz - 2*cz*dy**2*pz +
2*cx*dx*dz*pz + 2*cy*dy*dz*pz - 2*dx*dz*px*pz - 2*dy*dz*py*pz +
dx**2*pz**2 + dy**2*pz**2 - dx**2*r**2 - dy**2*r**2 - dz**2*r**2))


One problem is that the formula actually isn’t defined at r, which can be worked around by evaluating the function at some r-\epsilon. Maybe it’s possible to rewrite the equation so that this limit problem isn’t an issue, but I will not touch that.

I would insert the LaTeX formula in my post, but that would probably break something… I tried to make an image of the formula but my tools failed to create the resolution needed to get a crisp image (>30k wide image). In lieu of that here is a pdf version of the beautiful formula and even that required some work since LaTeX really doesn’t like super wide equations.

Edit: Like I expected there are nicer solutions when you decide to not just hammer the problem with mathematica. @tanmay28’s solution 18811243 is a great example. Although I think most of my unwieldy expression is just expansions of cross products.

4 Likes

Such patience. Hats off. Could you describe a small explanation for the same?

2 Likes

There really isn’t much to it. The distance between the line and the center of the sphere is d = \frac{|(\vec{C} - \vec{P})\times(\vec{C} - (\vec{Q}+t\vec{D}))|}{|\vec{P} - (\vec{Q}+t\vec{D})|} we wish to solve the equation d=r or equivalently d^2=r^2. From there it’s just some mathematica magic to solve the equation (some replacements, solve and whatnot). I don’t doubt there exist neater expressions than this.

2 Likes

If we shift the center of sphere to origin, the equations get simplified a lot i guess! I used the same approach , using parametric equations for the q’(the point where q reaches after time t) and some algebraic manipulations.
Link to the solution : https://www.codechef.com/viewsolution/18751165

2 Likes

Yeah, I was mostly curious if there actually was a closed form solution. I really didn’t care whether or not it was a nice one or not. Most of what I have is likely massively expanded cross products and the like. If I were to solve for things by hand I could have simplified things a lot.

1 Like

Even I solved this problem with a bit of math magic It felt so satisfying to get AC after typing such a huge formula. https://www.codechef.com/viewsolution/18854101

1 Like
 a quadratic equation in something like 13 variables.


O…M…G…13?!

Actually, Square rot thing wont fit in screen if you use latex xD. PDF was a wise option

I too used the same approach. I considered a parametric equation of Q in terms of time t, found the equation of line PQ and put it in the equation of the sphere. You will then get a quadratic equation whose discriminant must be zero. Equating the discriminant to zero gives you the required value of t. If the formula is first solved on a paper then it can be simplified a lot. Here is my solution in c++:
https://www.codechef.com/viewsolution/18807019
Also, it takes much less time than the solutions in python.

Even i used the same approach and follow the equation number 6 from here : http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html

Using numpy array it becomes a lot easier to implement and even the code looks cleaner and easier to debug.

My solution :
https://www.codechef.com/viewsolution/18851138

I tried something on lines of this. But failed miserably. https://www.codechef.com/viewsolution/18753251 .

even I used a similar strategy, as the usual one didn’t strike me at that time.
I simplified it a quite a bit.
I hope this would be more easy to understand
Ps: mine only took 1.25 sec in python 2, I didn’t understand your code(for obvious reasons), but I can figure out that you used almost the same method as mine, but what causes such a big time difference is yet to be figured.

1 Like

Solved using formula only in python…