Help in Expected Distance

Can someone explain the logic of this problem : http://www.codechef.com/CLASH14/problems/CREDDIST
I have tried to figure it out, have no idea about its logic. I don’t want the final solution, just a hint or basic idea behind its logic

You basically want to find out the expected value of a function . Here the function is the distance of the isolated point from an arbitrary point P(coordinate1 , coordinate2) on the circle . For simplicity you may express the point P in terms of parametric equation of a circle (Rcos(phi) , Rsin(phi)) . Now write the distance of the isolated point from the arbitrary point P on the circumference of the circle . This is the function that you want to find the average of . The average value is given by (Integral(distance function) from 0 to 2pi) / 2pi .

2 Likes

how to integrate sqrt(5+4cos x)

// This is my commented code. I think this must be enough to understand how expected value is calculated for the question.

#include<stdio.h>
int main()
{
long long int r,d;
scanf("%lld",&r);

/***

  • The distance of the isolated point from the arbitrary point P on the circumference of the circle .

  • This is the function that you want to find the average of .

  • The average value is given by (Integral(distance function) from 0 to 2pi) / 2pi .

  • Let choosen centre be (-R,0) and

  • arbitrary point choosen on other circle be ((R+ Rcos(x)),(0+ Rsin(x))) -> These are coordinates written in polar form

  • Distance function = f(x) = (from 0 to 2pi) Integral( sqrt( (Rsin(x)-0)^2 + (R + Rcos(x) - (-R))^2 ) -> This is distance between centre and arbitrary point.

  • which on solve become - f(x) = (R * Integral( sqrt( 5 + 4*(cos(x)) ) ) ) from 0 to 2pi

  • after solving this definite integral it comes out to be about 13.364893*R

  • and finally find average value = (13.364893 * R )/2pi

***/

d=r*2.1270888;

printf("%lld",d);

return 0;
}

2 Likes

Mainly this problem was about how to find the integral!

One (wrong) way is to use the Wolfram Alpha! which gives the answer upto many digits.

Other (good) way is to evaluate the definite integral!

this function is non integratable. So, we use the first principle of definite integrals to solve the problem.

Basically we divide the line between 0 and 2pi into 10^6 partitions and compute the area under each small integral as dxF(0+i*(dx)) when dx = (2*pi-0)/(10^6) and i goes from 0 to 10^6.

Dividing the sum of these smaller areas with 2*pi gives the constant 2.127…

1 Like
//