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

×

VSN - Editorial

Problem Link

Practice

Contest

Author: Rahim Mammadli

Tester: Misha Chorniy

Editorialist: Bhuvnesh Jain

Difficulty

EASY-MEDIUM

Prerequisites

Cross Product, Binary Search

Problem

Given a stationary point $P$ and a point $Q$ moving in straight line, indicate the time when $Q$ is visible from $P$, given that there am opaque sphere between them.

Explanation

We will try to find the solution in 2-D and then extend the idea to 3-D as well.

From the above figure, the first idea which can be clearly concluded is that, once point $Q$ becomes visible from $P$, it will remain visible forever. Before that, it will always remain invisible. This, the function (whether $Q$ is visible $P$ at given time $t$) follows the idea that it is false initially and after a certain point, it always remains true. This hints that we can binary search on the answer and just need to check whether the point $Q$ is visible from $P$ at given time $t$ or not. For more ideas on "Binary search" on such type of problem, refer to this awesome tutorial on topcoder. Hence, solution template looks like:


    double low = 0, high = 10^18
    for i in [1, 100]:
        double mid = (low + high) / 2
        if visible(P, Q, C, r, mid):
            high = mid
        else:
            low = mid
    double ans = (low + high) / 2

So, given a particular time $t$, we can first calculate the position of point $Q$. Join $P$ and $Q$ by a straight line. If the line doesn't pass through the circle, the point $Q$ is visible from $P$ else it is not visible. To check if a given line passes through the circle or not, it is enough to check that the perpendicular distance of the line from the centre, $C$, of the circle is greater than the radius, $r$, of the circle. For this, we first complete the triangle $PCQ$ and let the perpendicular distance of $PQ$ from $C$ be denoted by $CO$. Using the formula,

$$\text{Area of triangle} = \frac{1}{2} * \text{Base} * \text{Height} = \frac{1}{2} * CO * PQ$$

Since the area of the triangle can be found given 3 points in 2-D, and $PQ$ is the Euclidean distance between $P$ and $Q$, we can find the value of $CO$ efficiently. Finally, we just need to compare it to $r$, the radius of the circle.

For extending the solution in 3-D, the idea is same and we just need to find the area of a triangle in 3-D. For details, one can refer here. It can be clearly seen that the above formula holds for the 2-D case as well.

$$\text{Area of triangle in 2/3-D} = \frac{|CP X CQ|}{2}$$

where $CP$ and $CQ$ are vectors, $a X b$ denotes cross product of vectors and $|a|$ denotes the magnitude of vector.

Thus, to find the length of $CO$, we have

$$|CO| = \frac{2 * \text{Area of triangle PCQ}}{|PQ|} = \frac{|CP X CQ|}{|PQ|}$$

For more details, you may refer to the editorialist solution which exactly follows the above idea.

Extra Ideas/Caveats

The binary search implementation mentioned in the editorial is different from the one mentioned in Topcoder tutorial. Though both will give AC here, the one in Topcoder needs one to correctly set the Epsilon value for termination condition and sometimes can lead to wrong answers due to precision issues. The editorialist just prefers the above style to implement binary and ternary search involving doubles as calculation of epsilon is not required.

Also, for details regarding the exact number of iterations or complexity analysis for binary search problem on doubles, refer to this blog on codeforces.

Note from the author

Finding the distance of a point from a line in 3-D is a generally common problem and also contains some edge cases where the point may not lie within the line segment region. But given the constraints of the problems, there are no edge cases but we should be aware of it in general.

Feel free to share your approach, if it was somewhat different.

Time Complexity

$O(LogN)$ per test case (around 100 iterations for binary search).

Space Complexity

$O(1)$

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.

Tester's solution can be found here.

Editorialist's solution can be found here.

This question is marked "community wiki".

asked 06 Jun, 01:17

likecs's gravatar image

6★likecs
3.7k1570
accept rate: 9%

edited 17 Jun, 18:29

vijju123's gravatar image

5★vijju123 ♦
14.2k11349

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

(11 Jun, 16:00) schleppel4★

Time Complexity O(1) per test case reminds me of https://codeforces.com/blog/entry/58667 xD

(20 Jul, 01:34) aryanc4034★

What? I think I edited that section out for correction xD. Where is it left now? :p

PS: Great blog you found :p

(20 Jul, 01:36) vijju123 ♦5★

123next »

Want to mention two things:

  1. Complexity is not O(1) per test case (As this will confuse ones who are new to discrete binary search) :The number of iterations (100 in this case) will need to be adjusted if tmax is larger, actual time complexity if $O(log_2{t_{max})}$, (per test case) in this case.

  2. To get precision upto n decimal places, setting epilson as $10^{-n-1}$ will work fine as both low and high will be same upto n decimal places.

link

answered 11 Jun, 16:04

pshishod2645's gravatar image

5★pshishod2645
4779
accept rate: 17%

Yes, that was exactly my point! :)

(11 Jun, 16:06) vijju123 ♦5★
1

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

(11 Jun, 22:07) algmyr6★

Alternative approach to checking whether Q(t) is visible from P or not at a given time t:

Obtain a parametric equation of the line joining P and Q(t) in terms of some parameter (say a) which varies from 0 to 1. Any point (x, y, z) lying on this line can be written in terms of a as:

x = Px.(1-a) + Qx(t).a

y = Py.(1-a) + Qy(t).a

z = Pz.(1-a) + Qz(t).a

At a = 0, you are at point P and at a = 1, you are at point Q(t). At any a between 0 and 1, you are at some point in the line between P and Q(t).

Now we substitute (x, y, z) in terms of the parameter a in the equation of the sphere. We will obtain an equation in terms of t and a, which will be a quadratic in the parameter a. The point of tangency is when this quadratic has exactly one root, so we binary search on t, searching for that t when the quadratic's discriminant becomes zero.

Link to my solution: https://www.codechef.com/viewsolution/18755742

link

answered 11 Jun, 16:04

akamoha's gravatar image

3★akamoha
1264
accept rate: 20%

edited 11 Jun, 17:10

I used simple 3D Coordinate Geometry.
Let the general point on which point Q is traveling be Q'.
Therefore,
Q'x=Qx + Dxt
Q'y=Qy + Dyt
Q'z=Qz + Dzt

Now, the equation of line PQ' in parametric form(with parameter k) is,

X = Px + (Q'x-Px)k
Y = Py + (Q'y-Py)k
Z = Pz + (Q'z-Pz)k

Now, equation of sphere is,
(X-Cx)2 + (Y-Cy)2 +(Z-Cz)2 = R2
Now solve Line PQ' with equation of sphere, and we will get a quadratic equation in parameter k.
For condition of tangency(single solution), delta must be equal to zero.
So calculate delta and make it equal to zero, and here we get another quadratic in t.
Solve for t and consider the postitive value ,since it is time.

link

answered 11 Jun, 16:05

adzo261's gravatar image

4★adzo261
2096
accept rate: 42%

edited 12 Jun, 11:25

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

(14 Jun, 14:56) p1p5_52★

If D is the point upto which Q goes, then

|(PCXPD)/|PD||=r

If k is the time, a quadratic in k can easily be solved.

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

link

answered 11 Jun, 16:15

cloudsandrain's gravatar image

3★cloudsandrain
413
accept rate: 0%

edited 12 Jun, 12:41

I think the time complexity of $O(1)$ per test case is a typo. Although the solutions arent available right now, I can make a guess that the implementation referred to is something like "Binary search at least $100-200$ times." to get the answer, that value of $100-200$ is based on the value of $N$. We know the value of $LogN$ and set a value higher than that as limit.

Can you please share the code snippet you're talking about (I am assuming its not the topcoder one but the one in editorialist solution), if my above argument isnt applicable to your solution?

link

answered 11 Jun, 15:54

vijju123's gravatar image

5★vijju123 ♦
14.2k11349
accept rate: 18%

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

(11 Jun, 15:58) likecs6★

code snippet is same as the one mentioned in editorial

(11 Jun, 15:59) likecs6★
1

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? :)

(11 Jun, 16:03) vijju123 ♦5★

Seems Ok. Will update it in a while.

(11 Jun, 16:09) likecs6★

Thanks :) :D

(11 Jun, 16:10) vijju123 ♦5★

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.

link

answered 11 Jun, 21:12

soham1234's gravatar image

6★soham1234
1.8k614
accept rate: 21%

edited 11 Jun, 22:50

Yes my two solutions giving different outputs passed.

(11 Jun, 23:09) brijesh_19985★
2

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

(12 Jun, 14:37) likecs6★

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

(13 Jun, 12:40) brijesh_19985★

Or Take the Reference of this site to solve this.

http://www.ambrsoft.com/TrigoCalc/Sphere/SpherLineIntersection_.htm

Condition on :B * B-4 * A * C

SInce it is Monotonic.We can use Binary Search

link

answered 11 Jun, 18:43

doramon's gravatar image

1★doramon
865
accept rate: 5%

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.

link

answered 11 Jun, 23:06

brijesh_1998's gravatar image

5★brijesh_1998
202
accept rate: 50%

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

link

answered 12 Jun, 12:56

harbeersamra's gravatar image

3★harbeersamra
112
accept rate: 0%

edited 12 Jun, 12:57

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!!

    link

    answered 16 Jun, 17:37

    zymbio's gravatar image

    4★zymbio
    212
    accept rate: 0%

    1

    @zymbio, I saw your solution and it is totally correct. It will TLE just because python is slow. Try submitting in "pypy" or using the number of iterations as 75 (finding the exact number of iterations has been added as link in the editorial)

    (17 Jun, 14:32) likecs6★

    sure! will also go through the link :) thanks !!

    (17 Jun, 19:46) zymbio4★
    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:

    ×14,850
    ×1,472
    ×918
    ×577
    ×573
    ×179
    ×17
    ×14

    question asked: 06 Jun, 01:17

    question was seen: 3,632 times

    last updated: 20 Jul, 01:36