VSN - Editorial

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

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

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

    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

    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.

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

    code snippet is same as the one mentioned in editorial

    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

    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

    Yes, that was exactly my point! :slight_smile:

    Seems Ok. Will update it in a while.

    Thanks :slight_smile: :smiley:

    was expecting this… PS: I have tried many solutions for this one… one of them luckily worked…

    |PC x PQ'| / |PQ'| == r
    

    You are comparing float here!

    1 Like

    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

    Yes my two solutions giving different outputs passed.

    Find the fastest codes with 100 points in submissions… You’ll get your desired solutions :slight_smile:

    i.e. sort them according to run time and select “AC”

    here is my solution without binary search :slight_smile:

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

    2 Likes