VSN - Editorial

editorial
, , , , , , ,
12

Can you prove that binary search will give the correct answer in max 100 iterations?

My submission: TLE submission

Source of condition: Line Sphere intersection

13

Hi. Both Author’s and Editorialist’s solution fail in this test case:

1
4 0 0 -10 6 0 1 0 0 0 0 0 3

I mailed the testcase to Misha 2 days before the contest ended but it wasn’t updated. Any reason why?

Edit:He mailed . He was busy for his exams so didn’t see my mail before.

3 Likes
14

I think the below link is enough to solve the Question in just half an hour.
Here,they provided full proof of of dot product as well as cross product formula…its became really helpful to me :slight_smile:

link: Point-Line Distance--3-Dimensional -- from Wolfram MathWorld

15

I think test cases were weak during contest as per given case by @soham1234

1
4 0 0 -10 6 0 1 0 0 0 0 0 3

this solution gives output 19.2915 which is wrong (this is my code accepted during contest)
many submissions giving different outputs passed during contest.

this solution gives output 8.7085 which is correct (i submitted after contest)

Mistake in my code was to find minimum positive t.

1 Like
16

I did not use binary search.

Point P will make an enveloping cone (cone by tangents) C to sphere. Find equation of C.

Point Q with vector d, will make a straight line (ray) L. Find equation of L.

Now the point of intersection of C and L is the required point, which will give minimum time t after solving.

Per test case O(1) solution:
https://www.codechef.com/viewsolution/18861170

17

my solution
Could anyone please tell me what is the mistake in my code?
I’m getting the most precise answer;

18

Anyone having solution without binary search ??? my solution

Anyone with a similar approach and working well please post your solution in the comment section :slight_smile:

19

I solved it in O(1) for every test case.
My approach was initializing P to [x1,y1,z1], Q to [x2 + tdx, y2 + tdy, z2 + tdz] and C to [x3,y3,z3].

And applying formula |PC X PQ| / |PQ| (considering vectors).

This formula will give us shortest distance between line PQ and centre of Circle (c). Since for time t to be minimum, this distance should be equal to R (radius).

SO, r = |PC X PQ| / |PQ|.

Substitute values for P, Q and C and at end you will get an quadratic equation of the form b^2 - 4ac = 0,

Solve it and take the minimum positive root(incase we get both positive roots).

Easy solution : CodeChef: Practical coding for everyone

1 Like
20

This approach is different from binary search approach.
And it works! it is based on forming a quadratic equation based on distance formula and requires very few lines of code :
Here is the link to the code:
https://www.codechef.com/viewsolution/18842935

21

hello,
I tried solving this problem using vector algebra without using binary search technique.I moved the point
Q with time t and then checked the perpendicular distance from the center .My solution was not correct and
I am not able to figure out my mistake.
Here is the link to my submitted code.
https://www.codechef.com/viewsolution/18860135

22

I used the same approach as mentioned in the editorial using python 3.
I am getting TLE for 6 out of 7 tasks.

The link for the code is:

  • https://ideone.com/IZ6ikK

    • Could anyone please check and see whats wrong with my code.
    It will be of great help. Thanks!!

    1 Like
    23

    @p1p5_5 I implemented the same idea. You can see the solution here
    https://www.codechef.com/viewsolution/18824486

    24

    Hello @saurav96 here is your accepted code:Link The only problem was precision since you had used float it was resulting to less precision. Use double or long double to resolve. You can also see this link for more info:gfg

    25

    hello,

    can someone help me understand this concept.

    i want to use this formula as…
    |PC X PQ| / |PQ| = R

    so does PC represents C(x,y,z) - P(x,y,z) ?
    if so…
    how to get values for a,b,c using numerator |PC X PQ| ??
    please help.

    Thanks.

    26

    O notation doesn’t take into account constant factors. Still updated it for reference.

    27

    code snippet is same as the one mentioned in editorial

    28

    I went a different route and used axis rotations and translations to calculate the intersections of the path Q takes and the cone created by the sphere and Point P as the apex of the cone. “long double” precision was good enough - I only had to manually detect the sample test case and output “1” for that one. xD

    29

    What I wanted to say was, that constant was based on your N. You wont be using the same 100 iteration for high={10}^{1000}. The doubt I had is, that, this K (where K is no. of iterations) must be \ge logN. Hence I feel its theoretically wrong to call it O(1). Am I right? Or am I missing something? :slight_smile:

    1 Like
    30

    Yes, that was exactly my point! :slight_smile:

    31

    Seems Ok. Will update it in a while.