Show all threads Hide all threads Show all messages Hide all messages |
If you have WA #8 | elmariachi1414 (TNU) | 1078. Segments | 27 Oct 2022 20:16 | 9 |
It is right.... I failed in #8 as well... Look at this: We assume, that one segment is inside another, if the two segments are different, the first one is fully contained in the second one, and their endpoints do not coincide. Pay attention to this: and their endpoints do not coincide. It means 3 4 and 4 4 coincide too! try this test : 3 -3 -2 1 5 2 4 Answer: 2 3 2 try this 8 1 10 2 3 4 5 6 7 8 9 20 30 21 29 22 28 answer 3 8 7 6 Another test: .in 3 3 5 3 4 4 5 .out 1 1 or 1 2 or 1 3 This is a helpful test for dfs-like algo. |
WA#5 help! | Daria | 1078. Segments | 30 May 2022 16:14 | 2 |
Does somebody know what test I need to try to solve this problem? |
This is not mentioned in statement | andreyDagger | 1078. Segments | 17 Nov 2021 23:48 | 1 |
Segments can be with zero length |
Here are second and third test case for people who WA#2 or #3 | Ilian | 1078. Segments | 3 Mar 2021 19:45 | 6 |
Test case 2: 9 -1 1 -2 2 -3 3 -10 10 3 6 4 5 2 7 1 8 0 9 Answer: 6 6 5 7 8 9 4 Test case 3: 100 272 422 352 367 102 435 274 469 532 554 88 468 28 761 334 381 62 236 858 955 104 930 4 892 467 749 39 695 189 709 217 790 571 999 126 355 138 779 570 645 31 222 372 511 345 888 535 731 435 953 87 869 172 863 442 936 450 704 452 697 862 896 887 977 510 844 135 225 95 932 632 888 30 704 165 523 47 306 107 645 22 34 237 712 779 796 505 964 419 495 171 751 449 616 62 642 355 954 101 266 71 585 284 723 69 900 781 998 21 338 619 950 173 239 394 502 183 605 113 999 30 748 122 833 541 829 65 453 650 741 141 562 355 928 360 852 83 997 563 590 482 668 318 980 84 170 233 858 9 484 637 799 104 611 483 856 29 889 16 463 530 709 774 979 414 654 332 527 406 476 257 735 57 257 201 508 259 806 62 955 410 790 37 720 490 893 573 779 241 400 315 640 242 940 165 929 54 814 356 501 Answer: 13 2 8 95 88 38 66 77 48 14 92 61 79 12 the answer to test 3 can also be 13 2 8 95 88 38 66 51 48 14 92 61 7 12 it can also be 13 45 58 22 84 96 52 86 46 19 62 26 79 12 can also be 13 85 58 22 84 96 52 86 46 19 62 11 35 69 Edited by author 03.03.2021 19:41 Edited by author 03.03.2021 19:41 |
My wrong solution got accepted | Nanami_chan | 1078. Segments | 4 Jun 2020 23:11 | 1 |
3 50 100 -50 70 51 70 My accepted solution prints 1 2 While the correct answer should be 2 3 1 Edited by author 04.06.2020 23:13 |
WA test #4 or #6. Here's the bug!! | Dang Quang Huy | 1078. Segments | 1 Jul 2016 20:08 | 1 |
test #4, if you sort the left nodes then before updating the DP[i], you should check whether their left nodes are coincide or not. e.g: 4 1 2 1 3 1 4 1 5 test #6: this test has n == 1, you just need to print 1 and 1 in the output. |
if you get WA#8 or WA#13 try this test case. | Adham(TUIT) | 1078. Segments | 9 Jan 2016 12:48 | 2 |
input: 7 1 1000 2 500 501 999 3 499 502 800 4 400 503 700 output: 4 6 4 2 1 or 4 7 5 3 1 |
Idea | Felix_Mate | 1078. Segments | 8 Jul 2015 12:21 | 1 |
Idea Felix_Mate 8 Jul 2015 12:21 I solved the problem by using a topological sorting.The vertices are segments.The arcs of the graph characterize nesting |
if you use O(n*logn)..and wa. test thist~ | july | 1078. Segments | 6 Jul 2015 17:37 | 4 |
4 0 1 -1 4 -2 10 -3 3 Edited by author 07.05.2009 17:46 it's very useful data.thanks! is the answer this? 3 1 2 3 |
I got WA #4. pls help me! | Elmi Ehmedov | 1078. Segments | 27 Aug 2013 13:22 | 3 |
my code : #include <iostream> #include <algorithm> using namespace std; struct cord { int x,y,p; }; int comp(cord a,cord b) { if (a.x < b.x) return 1; return 0; } int main() { cord a[501]; int best[501]; int way[501]; int oway[501],f=0; int n,i,j,k,l;
cin>>n; for (i=0;i<n;i++) { cin>>a[i].x>>a[i].y; if (a[i].y < a[i].x) swap(a[i].x,a[i].y); best[i]=1; a[i].p=i+1; way[i]=i; } sort(a,a+n,comp); for (i=0;i<n;i++) for (j=0;j<n;j++) if (j != i) { if (a[i].x >= a[j].x && a[i].y <= a[j].y) { if (best[j]+1 >= best[i]) { best[i]=best[j]+1; way[i]=j; } } } k=best[0]; l=0; for (i=1;i<n;i++) if (best[i] >= k) k=best[i],l=i; while (l != way[l] && k > 0) { oway[f]=a[l].p; f++; l=way[l]; k--; } oway[f]=a[l].p; f++; cout<<f<<endl; for (i=0;i<f;i++) cout<<oway[i]<<" "; cout<<endl;
return 0; } Edited by author 26.04.2011 18:15 Edited by author 26.04.2011 18:15 oh, I have solved it. Thanks! Edited by author 26.04.2011 23:09 |
WA#3 Please help | George Agapov | 1078. Segments | 8 Jul 2013 22:56 | 4 |
My solution: http://pastebin.com/BVfebbpv I used such algorithm: 1) sort of each point (it seems to work correctly on tests with same coordinates) 2) walk through sorted array of points, making dp on every segment with two variables (maxi and maxv) to indicate maximum value we can reach in this segment and id of inside segment, corresponding to this maaximal value I tried almost all tests from topics and lots, invented by myself and can't get what's wrong with my solution. try this 8 1 10 2 3 4 5 6 7 8 9 20 30 21 29 22 28 answer 3 8 7 6 I also had WA#3, but this test is AC. My solution used BFS. Please, help me! Thanks! #pragma comment(linker,"/STACK:8000000") #include <stdio.h> int loading(int &N,int** (&M)){ int *Left,*Right; scanf("%d",&N); if(N==0) {printf("%d",0); return -1;} Left=new int[N]; Right=new int[N]; int tmpL,tmpR; for(int i=0;i<N;++i) {scanf("%d %d",&tmpL,&tmpR); /*if(tmpR<tmpL) {int tmp=tmpR; tmpR=tmpL; tmpL=tmp;}*/ Left[i]=tmpL; Right[i]=tmpR;} M=new int*[N]; for(int i=0;i<N;++i) {M[i]=new int[N]; for(int j=0;j<N;++j) M[i][j]=0;}
//i-ый отрезок вложен в j-ый for(int i=0;i<N;++i) for(int j=0;j<N;++j) if(Left[j]<Left[i] && Right[i]<Right[j]) {M[i][j]=1; M[j][i]=-1;} delete[] Left;delete[] Right; return 0; } int doing(int &N,int **(&M),int *(&Last),int &posBiggestWeight,int &BiggestWeight){ Last=new int[N]; int *Weight=new int[N]; for(int i=0;i<N;++i) {Last[i]=-1; Weight[i]=0;}
//Поиск отрезков, которые ни во что не вложены int *Roots=new int[N],iCountRoots=0; for(int i=0;i<N;++i){ bool isNotRoot=true; for(int j=0;j<N && isNotRoot;++j) if(M[i][j]==1) isNotRoot=false; if(!isNotRoot){ Roots[iCountRoots++]=i; } } //Перебор всех вложеных for(int k=0;k<iCountRoots;++k){ int NeedVisit[1000000],cntNVisit=0; NeedVisit[cntNVisit++]=Roots[k]; Weight[Roots[k]]=0; while(cntNVisit>0){ int tekVertex=NeedVisit[--cntNVisit],tekWeight=Weight[tekVertex],newWeight=tekWeight+1; for(int j=0;j<N;++j) if(M[tekVertex][j]==1 && newWeight>=Weight[j]){ NeedVisit[cntNVisit++]=j; Weight[j]=newWeight; Last[j]=tekVertex; } } } //поиск максимального веса BiggestWeight=-2; posBiggestWeight=-1; for(int i=0;i<N;++i) if(Weight[i]>BiggestWeight){ posBiggestWeight=i; BiggestWeight=Weight[i]; } delete[] Weight; return 0; } int saveing(int &N,int* (&Last),int &posBiggestWeight,int &BiggestWeight){ int *Answer=new int[BiggestWeight+1],pos=posBiggestWeight; int indAnswer=BiggestWeight; while(pos!=-1){ Answer[indAnswer--]=pos+1; pos=Last[pos]; } printf("%d\n",BiggestWeight+1); for(int i=0;i<BiggestWeight;++i) printf("%d ",Answer[i]); printf("%d\n",Answer[BiggestWeight]); delete[] Answer; return 0; } int main(){ int N,**M,*Last,posBiggestWeight=0,BiggestWeight=0; int res=loading(N,M); if(res==-1) return 0; doing(N,M,Last,posBiggestWeight,BiggestWeight); saveing(N,Last,posBiggestWeight,BiggestWeight); delete[] Last; for(int i=0;i<N;++i) delete[] M[i]; delete[] M; return 0; } |
got AC in 0.31 but i still did n^2 is there anyhting better? | marius dumitran | 1078. Segments | 8 Apr 2013 16:38 | 7 |
i used a df after i made an oriented graf(it's much easier to do than other solutions) if u did it better than O(N*N) please email me at dmarius1@yahoo.com Thanks Edited by author 15.04.2004 19:05 My decision not worse at all... At last! AC 0.001 and 394 KB I use dp O(n).ac in 0.0001s first,sort; second dp: answer=max{f(1)..f(n)}; f(i) means the best sum from the i one If you use sorting, it must be at least O(n*logn) I used sorting and then found the LIS in O(nlogn) time, 0.031 seconds |
About algo | Andrew Sboev [USU] | 1078. Segments | 15 Mar 2013 20:45 | 1 |
My DP gets WA3, and I don't know why. But my BFS gets AC :) |
No subject | Alex | 1078. Segments | 11 Mar 2013 15:35 | 1 |
Edited by author 11.03.2013 15:39 Edited by author 11.03.2013 15:39 |
Got AC~ | Heng | 1078. Segments | 21 Sep 2012 11:54 | 1 |
program ural1078(input,output); type node=record x,y:longint;num:longint;end; var n,i,j,max,maxi:longint; f:array[1..500]of longint; c:array[1..500]of longint; l:array[1..500]of longint; a:array[1..500]of node; procedure sort(l,r:longint); var i,j:longint;k,temp:node; begin i:=l;j:=r;k:=a[(l+r)div 2]; repeat while a[i].x>k.x do inc(i); while k.x>a[j].x do dec(j); if i<=j then begin temp:=a[i]; a[i]:=a[j]; a[j]:=temp; inc(i);dec(j); end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; procedure print(x:longint); begin if x=-1 then exit; print(c[x]); write(a[x].num,' '); end; begin readln(n); //if n=0 then writeln(0); for i:=1 to n do with a[i] do begin readln(x,y);num:=i; end; sort(1,n); fillchar(c,sizeof(c),255); for i:=1 to n do begin f[i]:=1;l[i]:=0; for j:=i-1 downto 1 do if (a[i].x<a[j].x)and(a[j].y<a[i].y) //Take Care!!! then begin if f[j]+1>f[i] then begin f[i]:=f[j]+1; c[i]:=j; end; end; end; for i:=1 to n do if f[i]>max then begin maxi:=i;max:=f[i]; end; writeln(max); print(maxi); end. |
Those need help for WA#6 | Nguyen Khac Tung | 1078. Segments | 26 Mar 2012 08:48 | 2 |
As I have encountered, I think the test is most likely several same length sequences which are not contained by any. Make sure you try this case before submitting :) |
solution for a problem | Arjun | 1078. Segments | 8 Mar 2012 14:51 | 1 |
hi, can anybody give me the solution for this problem 1078 in java? thanks. |
Why do this code gets WA3? I tried all the tests, supposed there. | iama | 1078. Segments | 11 Feb 2012 18:14 | 1 |
|
For koala: try this test for problem 1078 (+) | shitty.Mishka | 1078. Segments | 11 Feb 2012 17:56 | 3 |
0 :) The correct answer is 0 GL > 0 > > :) > The correct answer is > 0 > > GL 0 < N < 500 10 years later... Edited by author 11.02.2012 18:09 |
for those who have WA#2 | lolpwnZzzz | 1078. Segments | 23 Jul 2011 23:09 | 1 |
Try such test: 5 -10 30 -10 20 1 1 2 5 3 4 Correct answer: 3 5 4 1 or 5 4 2 |