VSN has a closed form solution

general
, , , ,
1

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. :stuck_out_tongue:

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
2

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

2 Likes
3

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. :stuck_out_tongue:

2 Likes
4

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
5

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
6

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

1 Like
7 
 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 :smiley:

8

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.

9

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

10

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

11

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 :slight_smile:
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.
Link: https://www.codechef.com/viewsolution/18760242link text

1 Like
12

Solved using formula only in python…
link-> https://www.codechef.com/viewsolution/18795709
Don’t know what’s great in finding out that it has a closed form solution.I mean it is so obvious.

13

I don’t think you require to do that much of work, you can easily find the coordinates of point Q at any time t, now this will result in a time-dependent equation of line PQ. Just set the perpendicular distance of this line with the center of the sphere to the radius, since you have only one unknown(time, t), you will get a quadratic in t, which will give two solutions of t(one positive and one negative). link–> https://www.codechef.com/viewsolution/18868704

14

At first I’ve tried taking the arbitrary line equation of PQ and substituting in the sphere equation and check for tangency. Although the sample testcase passed I’ve got a WA.
Here’s that Solution!
After that I’ve done taking the projection of PC on PQ and equated it with sqrt(PC^2 - r^2). Then it passed. Deep Sighs! Here’s that Solution!

Couldn’t figure out why my first approach was wrong.