ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1726. Visits

please give an idea
Posted by melkiy 18 Oct 2009 01:38

I use the fomula to find average of n values X[i], i=1...n  if I know the average of (n-1) values X[i], i=1...(n-1):

AVE(X, n) = ((n-1)AVE(X, n-1) + X[n]) / n

This doesn't help.
Re: please give an idea
Posted by svr 18 Oct 2009 11:00
1.sort(X[]).
2.add (X[i+1]-X[i])*i*(n-i).
Re: please give an idea
Posted by melkiy 18 Oct 2009 20:05
Brilliant idea. I've got it.
Thanks.
Re: please give an idea
Posted by lerh 4 Apr 2011 03:26
i've got smth similar but i don't understand how to sort it... pls help
Re: please give an idea
Posted by catalin_oancea 6 Apr 2011 22:38
I don't have any ideea... how did you solve this problem? I've got TLE ... I use brute force.. LOL
Re: please give an idea
Posted by Master Joda 7 Apr 2011 01:24
Doesn't work with 4 10 10 10 20 20 10 20 20!

1.sort(X[]).
2.add (X[i+1]-X[i])*i*(n-i).

Edited by author 07.04.2011 01:25
Re: please give an idea
Posted by lerh 7 Apr 2011 05:44
how do you sort it, what is min and what is max after sort... i've got WA for 3 20 20 30 30 50 10
Re: please give an idea
Posted by svr 7 Apr 2011 07:41
must work!
segment[X[i],X[i+1]] is passed by all pairs from [1..i]*[i+1,..n] or i*(n-i) times
where i in[1..n-1]
Re: please give an idea
Posted by lerh 8 Apr 2011 02:03
i still don't get it... pls send me your source at lerh_91@live.com
Re: please give an idea
Posted by panhantao 26 Sep 2012 22:00
Because for a given point i we can only go to another point vertically or horizontally and that's a great hint.

Consider an input file that contains 7 points (index from 1 to n), and now we have sorted them by x[] in ascending order.

Now let's consider the segment between point 5 and point 6, denoted by S(S=x[6]-x[5], remember that we have sorted the points by x[]). Now if we want to go from point 2 to point 6, we must pass through S, and likewise, if we want to go from point 1,2,3,4,5 to point 6,7, we have to pass through S. Inversely, from point 6,7 to point 1,2,3,4,5, we must pass through S. Actually, for a given segment x[i+1]-x[i], we have to pass through this segment i*(n-i)*2 times, for there are i points before and including the ith point and (n-i) points after the ith point, and we have to go from left to right and from right to left. This analysis is also true for the y coordinate.

By this method we can get the total distance from every point to every other point.

Finally just divide the total distance by (n*(n-1)) to get the average distance because there are n points and each point has (n-1) road to the other points.

In conclusion, the solution would be :
for(i = 1 to n-1)
{
    ans += (x[i+1]-x[i]) * i * (n-i) * 2;
    ans += (y[i+1]-y[i]) * i * (n-i) * 2;
    // or ans += (x[i+1]-x[i] + y[i+1]-y[i]) * i * (n-1) * 2;
}
ans /= ( n*(n-1) )

Be careful about the data type of ans, int is not enough, use long long
Re: please give an idea
Posted by Snayde 26 Apr 2013 19:37
thank
Re: please give an idea
Posted by Kirill Chernega [ONPU] 20 Jan 2016 01:45
really good explanation