You are not logged in. Please login at www.codechef.com to post your questions!

×

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

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.

asked 17 Jun, 14:12

algmyr's gravatar image

7★algmyr
1.1k13
accept rate: 37%

edited 17 Jun, 16:16

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 :D

(17 Jun, 18:02) vijju123 ♦5★

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

(17 Jun, 20:37) aryanc4036★

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

link

answered 17 Jun, 16:16

njha1999's gravatar image

3★njha1999
995
accept rate: 16%

1

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.

(17 Jun, 16:48) algmyr7★

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

link

answered 17 Jun, 14:57

likecs's gravatar image

6★likecs
3.7k1978
accept rate: 9%

2

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

(17 Jun, 15:55) algmyr7★

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

link

answered 17 Jun, 16:55

samsep10l's gravatar image

2★samsep10l
283
accept rate: 25%

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

link

answered 21 Jun, 00:09

panik's gravatar image

4★panik
563
accept rate: 20%

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.

link

answered 17 Jun, 20:01

rounak217's gravatar image

4★rounak217
1025
accept rate: 20%

edited 17 Jun, 20:02

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

link

answered 17 Jun, 20:21

ionstring's gravatar image

3★ionstring
974
accept rate: 20%

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.

link

answered 21 Jun, 12:11

abhihacker02's gravatar image

5★abhihacker02
313
accept rate: 0%

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

link

answered 23 Jun, 14:45

jaybansal's gravatar image

4★jaybansal
1
accept rate: 0%

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.

link

answered 24 Jun, 11:15

mohitchandrak's gravatar image

4★mohitchandrak
182
accept rate: 33%

edited 24 Jun, 11:16

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×179
×9
×8
×8
×8

question asked: 17 Jun, 14:12

question was seen: 1,097 times

last updated: 24 Jun, 11:16