Show all threads Hide all threads Show all messages Hide all messages | About WA7 (and some other WAs) | ivanovmp | 1588. Jamaica | 1 Sep 2022 22:28 | 1 | I walked through all topics in discussion, grabbed every test, but still got WA7. I had several mistakes in my solution. First of all, in some versions I forgot to make fixed format of output and forgot to cast my answer to integer type, therefore the solution printed the answer in scientific notation. Test: 25 7217 6651 7358 2764 7034 5638 2431 6831 6550 2019 2334 1524 3375 4802 5960 4579 7078 1798 3176 7335 5872 3950 179 7351 9800 3982 2080 897 9345 2389 6470 6556 8420 9316 1671 7557 922 2613 9464 6735 1865 8925 6701 3365 6519 6665 9458 1535 8792 4383 Answer: 1495422 In some solutions there were rounding issues, I rounded down while should have rounded up. Still I disagree that sometimes one should use floor(ans) instead of int(round(ans)), the latter always works fine in this problem. Test: 3 4826 9656 137 7424 8340 2686 Answer: 22472 In some attempts I accidentally used = instead of ==, this test detected this perfectly. Test: 4 0 0 2 0 2 2 0 2 Answer: 14 Edited by author 01.09.2022 22:29 | Rounding hint | Olerinskiy | 1588. Jamaica | 16 Jan 2022 03:01 | 2 | floor(x) or round(x) - wa7 (int)x - OK Thank you. It helped me pass WA7 Edited by author 16.01.2022 03:01 | Why WA at # test 8? | SerailHydra | 1588. Jamaica | 2 Jan 2022 15:26 | 5 | I've WA#8 too.Interesting, what test is it?Thank!!! Edited by author 27.10.2007 17:54 And I had WA too; because of stupid mistakes. This tests helped me to figure them out: 5 0 0 0 2 1 1 2 0 2 2 9 0 0 0 10 0 20 10 0 10 10 10 20 20 0 20 10 20 20 The thing is that if you order edges by an angle (atan) and length and do binsearch it's still possible that there will be edges with an appropriate angle, bigger length but not the one you are looking for, so binsearch in this case will give you a wrong result, so try to find a way to order them simple test is 6 0 0 10 0 10 10 10 20 0 10 0 20 and the answer is 171 | WA2 | AleshinAndrei | 1588. Jamaica | 19 Aug 2020 23:26 | 1 | WA2 AleshinAndrei 19 Aug 2020 23:26 How do you think what's the input-data in test-2? I did tested my program around 10 times :) but i didn't find mistake(( UPD: N = 1 ))) you mustn't test borders-cases in input data. You must check your algorithm. In this case i have "out of range" (because v_arr has length = 0, but in this program i don't check it and i address to zero index). If check border-case this algorithm is working My program: @@ #include <iostream> #include <cmath> struct Point { int64_t x; int64_t y; }; struct Vector { double r; double angle; }; int cmp(const void *a, const void *b){ Vector* v1 = (Vector*)a; Vector* v2 = (Vector*)b; double ans1 = ((v1->angle) - (v2->angle)); if (ans1 < 0){ return -1; } else if (ans1 > 0){ return 1; } double ans2 = ((v1->r) - (v2->r)); if (ans2 < 0){ return -1; } else if (ans2 > 0){ return 1; } return 0; } int main() { int N; std::cin >> N; Point p_arr[N]; Vector v_arr[N-1]; double dist = 0; int64_t dx, dy; for (int i = 0; i < N; ++i){ std::cin >> p_arr[i].x >> p_arr[i].y; } for (int i = 0; i < N; ++i){ for (int j = 0; j < i; ++j){ dx = p_arr[j].x - p_arr[i].x; dy = p_arr[j].y - p_arr[i].y; v_arr[j].r = sqrt(dx*dx + dy*dy); v_arr[j].angle = atan2(dy, dx); } for (int j = i+1; j < N; ++j){ dx = p_arr[j].x - p_arr[i].x; dy = p_arr[j].y - p_arr[i].y; v_arr[j-1].r = sqrt(dx*dx + dy*dy); v_arr[j-1].angle = atan2(dy, dx); } qsort(v_arr, N-1, sizeof(Vector), cmp); for (int j = N-2; j > 0; --j){ v_arr[j].angle -= v_arr[j-1].angle; } dist += v_arr[0].r; for (int j = 1; j < N-1; ++j){ if (v_arr[j].angle != 0){ dist += v_arr[j].r; } } } printf("%.0f", (dist / 2)); } @@ Edited by author 20.08.2020 00:55 | Hint WA7 | Vladimir [SPbETU] | 1588. Jamaica | 11 Jul 2020 01:28 | 3 | Hint WA7 Vladimir [SPbETU] 18 Oct 2013 00:01 Use printf("%.0lf\n", floor(answer + .5)); for output answer ;) | Rare WA#10 | Hidden | 1588. Jamaica | 15 May 2018 01:37 | 1 | It seems to be a rare problem in the submissions, but others have it. Any tips? I tried all the tests in the discussions, it works. | who has wa4 | CoolBoy | 1588. Jamaica | 5 Oct 2017 17:13 | 4 | 4th test is: 3 0 0 9999 10000 9998 9999 So double should be used instead of float...When I replaced float with double my code passed this test... And, the answer should be 28283 thats wroung answer for that test ! - you shouldn't add to the sum same distance twice !! ans is 14141 ! No! Right answer is 28283, because the points are not placing on one line. Edited by author 05.10.2017 17:14 Edited by author 05.10.2017 17:14 | It's very stupid! I have TL on Pascal and AC on C++(2013).I wrote same algo! | Felix_Mate | 1588. Jamaica | 29 Nov 2015 21:37 | 1 | | WA at #14... | Mikhail Krivenko | 1588. Jamaica | 7 Jan 2015 03:48 | 2 | can anyone help me with that? AC now Mikhail Krivenko 7 Jan 2015 03:48 | My AC code !!! | AYUBXON UBAYDULLAYEV (TUIT of IT) | 1588. Jamaica | 16 Feb 2014 19:51 | 3 | #include<iostream> #include<math.h> #include<algorithm> void quickSort(double x[],double y[],int left, int right) { int i = left, j = right; double tmp; double pivot = x[(left + right) / 2]; while (i <= j) { while (x[i] < pivot) i++; while (x[j] > pivot) j--; if (i <= j) { tmp = x[i]; x[i] = x[j]; x[j] = tmp; tmp = y[i]; y[i] = y[j]; y[j] = tmp; i++; j--; } }; if (left < j) quickSort(x,y,left, j); if (i < right) quickSort(x,y,i, right); } double dis(double x1,double y1,double x2,double y2) { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } using namespace std; int main() { double a[305][305],x[305],y[305],max,s1; int i,j,n,k; cin>>n; for(i=1;i<=n;i++)cin>>x[i]>>y[i]; quickSort(x,y,1,n); int left=1,right=1; for(i=2;i<=n;i++) { if(x[i]==x[i-1])right++; else { sort(y+left,y+right+1); right++; left=right; } } sort(y+left,y+right+1); for(i=1;i<n;i++) for(j=i+1;j<=n;j++) a[i][j]=dis(x[i],y[i],x[j],y[j]); for(i=1;i<n-1;i++) for(j=i+1;j<n;j++) { max=a[i][j]; bool f=0; for(k=j+1;k<=n;k++) if ((x[k]-x[i])*(y[i]-y[j])==(y[k]-y[i])*(x[i]-x[j])) { if (max<a[i][k]) max=a[i][k];else a[i][k]=0; if (max<a[j][k]) max=a[j][k];else a[j][k]=0; } if (max>a[i][j]) a[i][j]=0; } s1=0; for(i=1;i<n;i++) for(j=i+1;j<=n;j++)s1+=a[i][j]; s1=s1+0.4999999999; cout<<(long long)s1; system("pause"); return 0; } #include<cstdio> #include<cmath> int main() { double x[300],y[300]; double l[300][300],m,s=0; int n,k,i,j; scanf("%i",&n); for(i=0;i<n;i++) { scanf("%lf%lf",&x[i],&y[i]); j=i; while(j&&(x[j]<x[j-1]||(x[j]==x[j-1]&&y[j]<y[j-1]))) { x[j]=x[j]+x[j-1];x[j-1]=x[j]-x[j-1];x[j]=x[j]-x[j-1]; y[j]=y[j]+y[j-1];y[j-1]=y[j]-y[j-1];y[j]=y[j]-y[j-1]; j--; } } for(i=0;i<n-1;i++) for(j=0;j<n;j++) l[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); for(i=0;i<n-1;i++) { for(j=i+1;j<n;j++) { if(!l[i][j])continue; m=l[i][j]; for(k=j+1;k<n;k++) { if((x[i]-x[j])*(y[k]-y[j])==(x[k]-x[j])*(y[i]-y[j])) { (l[i][k]>m)?m=l[i][k]:l[i][k]=0; (l[j][k]>m)?m=l[j][k]:l[j][k]=0; } } if(l[i][j]<m)l[i][j]=0; s+=l[i][j]; } } printf("%.lf",s); return 0; } There is no need to reinvent the wheel, that is a half of the program devoted to sorting can be replaced with struct P{ double x,y; }; P p[n]; F(i,n) cin >> p[i].x >> p[i].y; sort(p, p+n, [](const P& a, const P& b){ return tie(a.x,a.y) < tie(b.x,b.y); }); To reduce number of possible typos, use macros, such as #define I(x) int x; cin >> x #define F(i,n) for(int i = 0; i < (n); ++i) #define FOR(i,a,b) for(int i = (a); i < (b); ++i) Finally, "do not post AC solutions" :-) | What is the best algorithm? | asdsdf | 1588. Jamaica | 26 Mar 2013 21:13 | 7 | I use O(n^3), but i meet time problem. Can you help me? Of course, the best complexity is O(N^2 log N), but O(N^3) can get AC. Can anybody in short explain how to create O(N^2 logN) algorithm, please? I've already accepted O(n^3) solution and there's no promlem with it(definitely not the best implementation of this algorithm got ac in 0.2 sec), but how to create O(N*NlogN) algo? Use angle sort, after use binary search. I've Accepted O(N*NlogN) :) N^2 * log(N^2) algo: 1) Sort n^2 lines by distance. 2) Iterate from largest to smallest. 3) We have to add line to the answer, if we not have bigger line in set, covering this. We can easily check it with set. O(N^3) easily gets AC in 0.078s. | WA #5 | Faeton (Kyiv - Mohyla Academy) | 1588. Jamaica | 14 Mar 2012 20:05 | 3 | WA #5 Faeton (Kyiv - Mohyla Academy) 13 Feb 2008 03:20 8 0 10 0 20 10 20 100 20 0 30 0 99 0 100 0 0 | WA test 8 | Henrique | 1588. Jamaica | 16 Jun 2010 00:20 | 2 | plz help me, i got WA on this test , if someone knows this one help me!. I think it's a test like: 3 0 0 0 3 0 2 and I just adjust my program | WA on test 8... | Dexter | 1588. Jamaica | 6 Apr 2009 04:00 | 2 | Help! I get Wrong Answer on test 8... If someone knows 8th test please post it...thanks I get wrong answer on test 8 too. | Can someone help me with wa#7 | Igor Sarcevic | 1588. Jamaica | 5 Apr 2009 15:55 | 2 | I spend 3 hours searching to find the bug, but i found nothing, pls help me solve it... i had the same problem, but after realising that i might have made a mistake somewhere, i tried test case someone else already posted: 5 0 0 0 2 1 1 2 0 2 2 so, when i "fixed" my program, now i have WA#4 instead of WA#7 :P | WA#1...i don't understand why | Dexter | 1588. Jamaica | 4 Apr 2009 20:18 | 2 | I tested my code with many test cases and it always worked (even with N=1 - answer is 0). But when I submit the solution I always get WA on first test case. And I don't know why. Can I get the first test case so I can find out why my code doesn't work? I used Dev-C++ environment and C language (not C++). Edited by author 05.04.2009 16:46 Edited by author 05.04.2009 16:48 | What's the test 8 | yuyan | 1588. Jamaica | 18 Mar 2009 06:07 | 1 | Why I WA on #8?I can't find what's wrong with my program. Here is my code: program jamaica; const maxn=310; var k,b,l:array [0..maxn*maxn] of extended; x,y:array [0..maxn] of int64; i,j,m,n,min,max:longint; ans,d:double; procedure init; begin readln(n); for i:=1 to n do readln(x[i],y[i]); end; procedure qsort(head,tail:longint); var i,j,t,k:longint; begin if head>=tail then exit; i:=head;j:=tail; t:=x[(i+j) shr 1]; repeat while x[j]>t do dec(j); while x[i]<t do inc(i); if i<=j then begin k:=x[i];x[i]:=x[j];x[j]:=k; k:=y[i];y[i]:=y[j];y[j]:=k; inc(i);dec(j); end; until i>=j; qsort(head,j); qsort(i,tail); end; procedure sort(head,tail:longint); var i,j:longint; x,y,t:double; begin if head>=tail then exit; i:=head;j:=tail; x:=k[(i+j) shr 1];y:=b[(i+j) shr 1]; repeat while (k[j]-x>1e-8) or (abs(k[j]-x)<1e-8) and (b[j]-y>1e-8) do dec(j); while (k[i]-x<-1e-8) or (abs(k[i]-x)<1e-8) and (b[i]-y<-1e-8) do inc(i); if i<=j then begin t:=k[i];k[i]:=k[j];k[j]:=t; t:=b[i];b[i]:=b[j];b[j]:=t; t:=l[i];l[i]:=l[j];l[j]:=t; inc(i);dec(j); end; until i>=j; sort(head,j); sort(i,tail); end; procedure solve; begin qsort(1,n); ans:=0; min:=y[1];max:=y[1]; for i:=2 to n do if x[i]<>x[i-1] then begin ans:=ans+max-min; max:=y[i];min:=y[i]; end else begin if y[i]>max then max:=y[i]; if y[i]<min then min:=y[i]; end; ans:=ans+max-min; m:=0; for i:=1 to n-1 do for j:=i+1 to n do if x[i]<>x[j] then begin inc(m);k[m]:=(y[j]-y[i])/(x[j]-x[i]);b[m]:=y[i]-k[m]*x[i]; l[m]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j])); end; sort(1,m); d:=l[1]; for i:=2 to m do if (k[i]<>k[i-1]) or (b[i]<>b[i-1]) then begin ans:=ans+d; d:=l[i]; end else begin if l[i]>d then d:=l[i]; end; ans:=ans+d; end; begin init; solve; writeln(round(ans)); end. | Please, help me! I've got Compilation Error ???? | Nguyen Dinh Tu (DHSP) | 1588. Jamaica | 3 Feb 2008 00:16 | 5 | #include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <utility> using namespace std; const int maxN = 304; int x[maxN], y[maxN]; int n; vector< pair<int, int> > p; bool mark[maxN][maxN]; int dist(const int& i, const int& j) { return (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]); } bool compairation(const pair<int, int>& p1, const pair<int, int>& p2) { return (dist(p1.first, p1.second) > dist(p2.first, p2.second)); } int ccw(const int& i, const int& j, const int& k) { int dx1 = x[j] - x[i], dy1 = y[j] - y[i]; int dx2 = x[k] - x[j], dy2 = y[k] - y[j]; return (dx1 * dy2 - dx2 * dy1); } int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
for (int i = 1; i < n; i++) for (int j = i + 1; j <= n; j++) p.push_back(pair<int, int>(i, j)); sort(p.begin(), p.end(), compairation);
memset(mark, true, sizeof(mark));
double total = 0.0; for (int i = 0; i < p.size(); i++) if (mark[p[i].first][p[i].second]) { int d = p[i].first, c = p[i].second; vector<int> point; point.clear(); for (int j = 1; j <= n; j++) if (ccw(d, j, c) == 0) point.push_back(j); for (int u = 0; u < point.size(); u++) for (int v = u + 1; v < point.size(); v++) { mark[point[u]][point[v]] = false; mark[point[v]][point[u]] = false; //cout << point[u] << " " << point[v] << endl; } total += sqrt(double(dist(d, c))); }
cout << round(total) << endl;
return 0; } cout << round(total) << endl;//<Mistake here There is no function round() in C++. Edited by author 01.02.2008 02:11 Or try follow: Set #include<stdio.h> and write printf("%0.lf",total); I think it will be more helpful. Edited by author 01.02.2008 01:42 Edited by author 01.02.2008 02:11 Thank you very much! I've got AC. But i compiled it sucessfully by DevC++ and Eclipse IDE. (It also uses g++ compiler). Please tell me why ????? Edited by author 01.02.2008 19:05 As far as I know there is no standart function round() in C++.For more information read FAQ.Good luck! | Why I got wa on test#4? | panrui | 1588. Jamaica | 27 Dec 2007 20:20 | 1 | #include<iostream> #include<math.h> #define MAX 200000 #define N 350 using namespace std; int n; double map1[N][N]; struct node { int x,y; }point[N]; double dist(node a,node b) { return sqrt((double)((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y))); } void init() { cin>>n; int i,j; for(i=1;i<=n;i++) cin>>point[i].x>>point[i].y; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { map1[i][j]=dist(point[i],point[j]); //cout<<map1[i][j]<<" "; } //cout<<endl; } } double calck(node a,node b) { if(a.x-b.x!=0) return (a.y-b.y)/(a.x-b.x);else return -MAX; } int mid(node c,node a,node b) { if(a.x!=b.x) { if(abs(a.x-b.x)>abs(a.x-c.x)) return 1; }else if(abs(a.y-b.y)>abs(a.y-c.y)) return 1; return 0; } void solve() { int i,j,k,used[N][N]; double ans=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { ans+=map1[i][j]; used[i][j]=0; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { for(k=1;k<=n;k++) { if(i==j || j==k || i==k) continue; if(calck(point[i],point[j])==calck(point[i],point[k]) && mid(point[k],point[i],point[j]) && used[i][k]==0 && used[k][i]==0) {ans-=map1[i][k]*2;used[i][k]=1;} } } } ans/=2; cout<<(int)(ans)<<endl; } int main() { init(); solve(); return 0; } | What are the rules of rounding? | Denis | 1588. Jamaica | 10 Dec 2007 19:24 | 3 | double dist = ...; printf("%0.0lf\n", dist); writeln(round(dist)); It's better to use round(ans + 1e-8) to avoid possible tricky tests with answers near x.5 |
|
|