Can someone please help me solve the problem?
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.
1 Like
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.
2 Likes
#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 :
-
start = min(x_l,x_w) , end = min(x_l,x_w)
-
calculate middle = (start + end )/2
-
find the time taken for position (middle-0.000001) , (middle) ,(middle + 0.000001) by using the formula ;
-
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
1 Like