VSN - Editorial

editorial
, , , , , , ,
21

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

22

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
23

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: http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html

24

To be pedantic, itā€™s not only dependent on t_\text{max} either. Itā€™s more like O(\log(t_\text{max}/\epsilon)).

1 Like
25

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
26

Yes my two solutions giving different outputs passed.

27

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

28

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

29

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:

30

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 Ā©. 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 : https://www.codechef.com/viewsolution/18820388

1 Like
31

Find the fastest codes with 100 points in submissionsā€¦ Youā€™ll get your desired solutions :slight_smile:

32

i.e. sort them according to run time and select ā€œACā€

33

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

34

here is my solution without binary search :slight_smile:

35

The test data is wrong. It is clearly mentioned that the point Q is not visible at time = 0 from P.

2 Likes
36

Thanks for pointing out. Updated info.

1 Like
37

I donā€™t think test data is wrongā€¦
because distance from line PQ to center is 1.5756771943166707 , you can find out and correct me if i am wrong :slight_smile:

38

5 start again :smiley: @birjesh_1998

39

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

40

Hi @adzo261, I have followed a similar approach but getting WA. Can you show me your correct submission?