After some failed attempts with O(n)=n*n/2, finally I found an O(n)=n solution. In plain C, it took 0.09s and 1.5Mb. (just from curiosity tried the same with C# - 14MB used RAM :)) The arrays of X and Y coordinates can be sorted independently from each other. So basically, this input: 3 1 3 2 1 3 2 will have exactly the same result (which is 2) as 3 1 1 2 2 3 3 can you proof it? Assuming a (x1, y1), b (x2, y2), then the distance from c (x3, y3) to (x1, y1) and (x2, y2) is equivalent to the distance from (x1, y2) and (x2, y1) I had int n,i; and I had wa #10, then I changed them to long long and got ac, but I can't understand why I got wa10 with int n,i; where i and n can't exceed 10^6. It's obviously a mistake in task's text. Program won't be accepted until it will work with n=10e6. thanks for your hint, helped me to get accepted verdict When you divide at the end by n*(n - 1) it gets overflow so you need to have type long long Edited by author 31.10.2020 16:46 Edited by author 31.10.2020 16:46 You need long long n. Because you divide at the end by n*(n - 1),n*(n-1) is overflow. After sorting of array of x and y all you need to do is to compute this two double sums sum(i=1)^n sum(j=1)^(i-1) (x_i-x_j) and sum(i=1)^n sum(j=1)^(i-1) (y_i-y_j). After simplifications one can obtain that they equal sum(i=1)^n x_i*(2*i-1-n) and sum(i=1)^n y_i*(2*i-1-n). After computations you divide final sum by C_n^2=n*(n-1)/2 and get required answer. Can you make your Formulations readable? ??? solved. you should calculate everything in int64 not doubles #include <bits/stdc++.h> using namespace std; struct duy{ long long x,y; }; duy a[100005]; bool cmp1(duy a, duy b){ return a.x>b.x; } bool cmp2(duy a, duy b){ return a.y>b.y; } long long n,dem=0,t=-99,s[100005][2],duoi[100005],res=0; double q; int main() { cin>>n; for(long long i=1; i<=n; i++) cin>>a[i].x>>a[i].y; sort(a+1,a+n+1,cmp1); for(long long i=1; i<=n; i++){ if(a[i].x==t) s[dem][2]++; else{ dem++; s[dem][1]=a[i].x; s[dem][2]=1; t=a[i].x; } } duoi[dem]=0; for(long long i=dem-1; i>=1; i--) duoi[i]=duoi[i+1]+s[i+1][2]; for(long long i=1; i<=dem-1; i++) res=res+s[i][2]*duoi[i]*(s[i][1]-s[i+1][1]); sort(a+1,a+n+1,cmp2); dem=0; for(long long i=1; i<=n; i++){ if(a[i].y==t) s[dem][2]++; else{ dem++; s[dem][1]=a[i].y; s[dem][2]=1; t=a[i].y; } } duoi[dem]=0; for(long long i=dem-1; i>=1; i--) duoi[i]=duoi[i+1]+s[i+1][2]; for(long long i=1; i<=dem-1; i++) res=res+s[i][2]*duoi[i]*(s[i][1]-s[i+1][1]); q=((double)((double)2*(double)res))/((double)((double)n*(double)(n-1))); cout<<roundf(q*1)/1; } Edited by author 09.04.2016 11:42 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. 1.sort(X[]). 2.add (X[i+1]-X[i])*i*(n-i). Brilliant idea. I've got it. Thanks. i've got smth similar but i don't understand how to sort it... pls help I don't have any ideea... how did you solve this problem? I've got TLE ... I use brute force.. LOL 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 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 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] i still don't get it... pls send me your source at lerh_91@live.com 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 can you give me the answer of this test please: 4 10 10 20 20 10 20 20 10 my program writes 20 but I am not sure if this is the right answer I STILL GOT WA!! it's 13 wtf... ???? why can you explain distance between first and second is 20 (|10-20 + 10-20|), between first and third is 10 (|10-10 + 10-20|), between first and fourt is 10 (|10-20 + 10-10|) so average for first is (20+10+10) / 3... do the same for second, third and fourth and result is (average for first + average for second + average for third + average for fourth) / n (in your case it's 4) ... and that is 20. no, the correct answer for this test is 13. Don't forget about rounding down! In pascal use trunc(x) instead of round(x) Example test: 3 1 2 2 1 3 3 output: 2 Edited by author 29.08.2012 23:54 Why time limit exceeded on test#9? Maybe you use O(n^2) algo? You can do it in linear time. Я думаю что расстояние между x1,y1 и x2,y2 вычисляется с помощью sqrt(sqr(x1-x2)+sqr(y1-y2))???????????????????????????????/ no, you can only go by road, so no sqrt and sqr Edited by author 03.07.2011 19:23 Congratulations!!!!!!!!!!!! I have WA 10 i use BigInteger ( it's exact true) :-) what's the problem...can somebody help me This is the first test where n*(n-1)/2 > 2^31 Don't use double, use Int64 only this part of code get WA10 __int64 ans = 0, sum_all_x = accumulate( vx.begin(), vx.end(), 0 ), sum_all_y = accumulate( vy.begin(), vy.end(), 0 ); but this part of code get AC __int64 ans = 0, sum_all_x = accumulate( vx.begin(), vx.end(), 0i64 ), sum_all_y = accumulate( vy.begin(), vy.end(), 0i64 ); =) This is my first solution. I don't know if I am doing everything all right. I use the Free Pacal Compiler. Does the output of my solution have to be real, rounded to an integer, or just integer? This is my solution program Project2; var x,y:array[1..100000] of longint; r:array[1..100000] of longint; d:longint; n,i,j:longint; begin readln(n); for i:=1 to n do readln(x[i],y[i]); for i:=1 to n do r[i]:=0; for i:=1 to n do for j:=1 to n do if i<>j then r[i]:=r[i]+(abs(x[j]-x[i])+abs(y[j]-y[i])); d:=0; for i:=1 to n do begin r[i]:=r[i] div (n-1); d:=d+r[i] end; d:=d div n; writeln(d) end. Edited by author 03.08.2011 20:09 can somebody explain me WTH on test 10 i get WA??? and if there is a possibility to post me ot mail me the test? use long long instead of int Edited by author 10.04.2011 23:53 Edited by author 10.04.2011 23:54 You need 64bit integer. Also, brute force isn't gonna solve this problem. I can't understand what they mean by this. 1.sort(X[]). 2.add (X[i+1]-X[i])*i*(n-i). What do you get when you input this: 100000 1000000 1000000 999999 999999 999998 999998 999997 999997 .... 900004 900004 900003 900003 900002 900002 900001 900001 I get 2154, and I'm not sure if it is OK because I get WA#10. I need more samples... I thought I understood, but when I submitted the task, I got WA, so, can you give some more samples, for me to get an idea? What's #3 like? I keep getting this WA.. |
|