Lifeguard Problem - CodeVita

Can someone please help me solve the problem?

https://codeofgeeks.com/lifeguard-probe/

I have given my best and I think this problem really requires some advanced concept.

Please!

1 Like

I think a ternary search for the answer would be okay here, as the time function will be kinda unimodal having only one minima.

Can anyone throw a light on it? I am very curious to know how to solve it.

If you look below, the code in python is already given, but I am not sure how this works. Can anyone explain?

    import math
    x1 = int(input())
    y1 = int(input())
    x2 = int(input())
    y2 = int(input())
    f = float(input())
    if y1+y2 == 0:
        a = x1*f
    a = int(a)
    print("{0 : .6f}".format(a))

This can be solved using calculus as below:

  • step1: consider any point P1(x,0) on the beach-sea interface
  • step2: calculate the time taken from source to point P(x,0) = T1(function of x)
  • step3: calculate the time take from P(x,0) to destination = T2(function of x)
  • step4: let Y = T1 + T2 (now Y becomes a function of x)
  • step5: now u just need to minimize Y for which differentiate it w.r.t x(i.e. find d(Y)/dx)
  • step6: solve for d(Y)/dx = 0 (at this step the value “V” will cancel out so do not worry about
    that).
  • step7: after step 6 u will get a value of x(may be more than one) then u need to varify whether
    this value of x corresponds to minimum or maximum(i.e. u need to find second order
    derivative of Y w.r.t x).

I hope this helps u ,all the steps are pretty standard(12th class syllabus).
happy learning!..

sea interface

But to solve that, we must know how to find the roots of f(x)=0, where degree is 4.

Anyone, please suggest how to move further.

X_solution=[(-y_l)*( (x_l-x_w) / (y_l-y_w) )]+x_l
Apply this solution,it will definitely work

this is from codeofgeeks right? it is totally incorrect…

Even I am unable to understand the logic. but in my opinion It has been uploaded by some user not the site

doesn’t seem so…i tried ur logic…still getting a wa

Yes, I realised its incorrect. So how to solve this problem?

Ternary search bro i said it earlier… you will find it a bit similar to

The only problem here in this codevita problem is that they are asking an accuracy upto 6 digits after decimal… its troublesome to keep that level of precision using square root function.

1 Like

#include <iostream>

#include <cmath>

using namespace std;

long double xl, yl, xw, yw, f;

long double calculate_it(long double i)

{

return sqrt(((xl - i) * (xl - i)) + (yl * yl)) / f + sqrt((xw - i) * (xw - i) + yw * yw);

}

long double search_it(long double start, long double end)

{

long double mid, current, prev, next;

long double ans = -1;

while (true)

{

    mid = (start + end) / 2;

    prev = calculate_it(mid - 0.000001);

    current = calculate_it(mid);

    next = calculate_it(mid + 0.000001);

    if (prev > current && next > current)

    {

        ans = mid;

        break;

    }

    else if (prev > current)

    {

        start = mid + 0.000001;

    }

    else

    {

        end = mid - 0.000001;

    }

}

return ans;

}

int main()

{

cin >> xl >> yl >> xw >> yw >> f;

long double count;

if (xl > xw)

{

    count = search_it(xw, xl);

}

else

{

    count = search_it(xl, xw);

}

printf("%.6lf", (double)count);

return 0;

}

/*

Explanation

(time)

 ^    

 |     *                            * 

 |       *                       *  

 |          *                 *

 |              *          *  

 |                    *           <--------(time_min )

 |

(0,0)--------------------------------------->(position)

       |                          |

     (x_l)                      (x_w)

       

       |___________________________|

       (x_min is between this point)    

we can use binary search by using the following condition :

  1. start = min(x_l,x_w) , end = min(x_l,x_w)

  2. calculate middle = (start + end )/2

  3. find the time taken for position (middle-0.000001) , (middle) ,(middle + 0.000001) by using the formula ;

  4. let the calucated time be prev, current and next respectively.

we can find direct our binary search using following condition ;

if( time taken in middle position is smaller than both prev and next )

then this is the required position 

else if( time taken in middle position is >time taken n prev postion )

 then move right  

else

move left

*/

//brute force soution

#include <iostream>

#include <cmath>

using namespace std;

long double xl, yl, xw, yw, f;

long double calculate_it(long double i)

{

return sqrt(((xl - i) * (xl - i)) + (yl * yl)) / f + sqrt((xw - i) * (xw - i) + yw * yw);

}

long double find_it(long double start, long double end)

{

long double i, mini, ans, count, prev = 0;
mini = 10000000000;
ans = i = start;

for (i = start; i <= end; i += 0.000001)

{
    count = calculate_it(i);
    if (count < mini)

    {
        mini = count;
        ans = i;

    }

}

return ans;

}

int main()

{

cin >> xl >> yl >> xw >> yw >> f;
long double count;

if (xl > xw)

{

    count =find _it(xw, xl);

}

else

{

    count =find_it(xl, xw);

}

printf("%.6lf", (double)count);

return 0;

}

//Here we increment the for loop by 0.000001 because it is given the the accuracy is checked upto 6 digit

the solution of this problem uses the logic of this problem