| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | AC in 0.09 ... a hint | Христо Попов (B&W) | 1726. Кто ходит в гости… | 9 апр 2023 18:52 | 3 | 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 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) | | for wa#10 | vahan | 1726. Кто ходит в гости… | 5 апр 2021 18:00 | 6 | 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. | | Accepted simple way how to compute sum of distances | Gleb Dubosarskii | 1726. Кто ходит в гости… | 29 мар 2021 20:43 | 2 | 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? | | WA #12? | index | 1726. Кто ходит в гости… | 2 мар 2017 13:25 | 2 | solved. you should calculate everything in int64 not doubles | | What 's on Test 2? Help me plz | quangduytr | 1726. Кто ходит в гости… | 22 фев 2017 07:54 | 1 | #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;
} | | No subject | Felix_Mate | 1726. Кто ходит в гости… | 20 янв 2016 14:52 | 1 |
Edited by author 09.04.2016 11:42 | | please give an idea | melkiy | 1726. Кто ходит в гости… | 20 янв 2016 01:45 | 12 |
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 | | test | ivailo chernev | 1726. Кто ходит в гости… | 25 окт 2012 20:19 | 6 | test ivailo chernev 4 апр 2011 03:00 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!! Re: test ivailo chernev 5 апр 2011 01:59 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) Re: test DR. Zhihua Lai 25 окт 2012 20:19 no, the correct answer for this test is 13. | | For WA2 | MOPDOBOPOT (USU) | 1726. Кто ходит в гости… | 29 авг 2012 23:53 | 1 | For WA2 MOPDOBOPOT (USU) 29 авг 2012 23:53 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 | Arsenal911 (Samara) | 1726. Кто ходит в гости… | 5 авг 2012 07:33 | 3 | Why time limit exceeded on test#9? Maybe you use O(n^2) algo? You can do it in linear time. | | Нахождение расстояния | daminus | 1726. Кто ходит в гости… | 24 апр 2012 13:27 | 2 | Я думаю что расстояние между x1,y1 и x2,y2 вычисляется с помощью sqrt(sqr(x1-x2)+sqr(y1-y2))???????????????????????????????/ no, you can only go by road, so no sqrt and sqr | | AC 0.078s!!!!!!!!!!!!!!!!!!!!! | Hrayr | 1726. Кто ходит в гости… | 4 мар 2012 01:06 | 2 |
Edited by author 03.07.2011 19:23 Congratulations!!!!!!!!!!!! | | who have WA 10??? | Rudolf [Sumy SU] | 1726. Кто ходит в гости… | 4 фев 2012 18:09 | 4 | 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 );
=) | | Why isn't my solution working? | NikolaV994 | 1726. Кто ходит в гости… | 26 ноя 2011 15:26 | 1 | 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. | | No subject | Ar7 [Perm SU] | 1726. Кто ходит в гости… | 3 авг 2011 19:46 | 1 |
Edited by author 03.08.2011 20:09 | | Test #10 | Gumzi | 1726. Кто ходит в гости… | 26 апр 2011 01:55 | 2 | 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 | | Need help | Jasmin Rahimic | 1726. Кто ходит в гости… | 11 апр 2011 11:36 | 3 | 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). | | Answer to this test | electroNik | 1726. Кто ходит в гости… | 10 апр 2011 20:04 | 1 | 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. | | Give some more tests... | mastermana | 1726. Кто ходит в гости… | 8 апр 2011 15:21 | 1 | 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? | | WA #3? | Nenad Zivic | 1726. Кто ходит в гости… | 4 апр 2011 00:13 | 1 | WA #3? Nenad Zivic 4 апр 2011 00:13 What's #3 like? I keep getting this WA.. |
|
|
