Discussion of Problem 1273. Tiealso DP.... It's obvious that LIS can be sloved in O(nlogn)... test 1?)) уже не надо Edited by author 31.10.2010 14:28 Edited by author 31.10.2010 14:45 I have AC!! Edited by author 31.10.2010 15:41 Just write in your code: ... scanf("%d",&n); if (n == 0){ printf("0"); return 0; } ... When I write it I got AC Good Luck :-) Thank you, I got AC too :) Alexander Akimenko ssau 6108 test [1] // Problem 1273. Tie 21 Mar 2010 15:37 please give some tests, WA7 I've tried all the tests mentioned here, and the output was correct. Still I have WA on test 7 var a,b,c,d: array [1..102] of integer; ind,n,i,j,k,z,v:integer; begin readln(n); k:=0; z:=0; for i:=1 to n do begin read(a[i]); readln(b[i]); if a[i]>b[i] then begin inc(z); d[i]:=1; end else d[i]:=0; end; if z>n div 2 then for j:=1 to n-1 do for i:=1 to n-1 do if d[i]>d[i+1] then begin v:=d[i]; d[i]:=d[i+1]; d[i+1]:=v; v:=a[i]; a[i]:=a[i+1]; a[i+1]:=v; v:=b[i]; b[i]:=b[i+1]; b[i+1]:=v; end; if z<n div 2 then for j:=1 to n-1 do for i:=1 to n-1 do if d[i]<d[i+1] then begin v:=d[i]; d[i]:=d[i+1]; d[i+1]:=v; v:=a[i]; a[i]:=a[i+1]; a[i+1]:=v; v:=b[i]; b[i]:=b[i+1]; b[i+1]:=v; end; repeat for i:=1 to n do c[i]:=0; for i:=1 to n do for j:=1 to n do if (((a[i]>a[j]) and (b[i]<b[j])) or ((a[i]<a[j]) and (b[i]>b[j]))) then c[i]:=c[i]+1; ind:=1; for i:=2 to n do if c[i]>c[ind] then ind:=i; a[ind]:=0; b[ind]:=0; if (c[ind]>0) then k:=k+1; until c[ind]=0; writeln(k); readln; end. I cant understand how it can be solved for nlogn. Help me or I'll kill you! lelik! I know how But i won't saw cause rule is so stupid please call me on 9 o'clock :)) what's your name? and how old are you? This could be done in K logK... why K is only 100? I think, 1000 is ok. It's 100. And I didn't say that is ok, I just said that K could be 100.000 and still working. I agree with you k log k is very simple :) #include <iostream.h> int main() {int K,max; cin>>K; int **a=new int*[K]; for (int i=0;i<2;i++) a[i]=new int[K]; for (int i=0;i<K;i++) for (int j=0;j<2;j++) cin>>a[j][i]; int *b=new int[2000]; for (int i=0;i<2000;i++) b[i]=0; for (int i=0;i<K;i++) if (a[0][i]>a[1][i]) b[a[0][i]-a[1][i]]++; else b[a[1][i]-a[0][i]+1000]++; max=b[0]; for (int i=1;i<2000;i++) if (b[i]>max) max=b[i]; cout<<K-max<<endl; //cin>>K; } ????? {$R+} var a, b: array[1 .. 101] of longint; y1, y2: array[1 .. 101] of longint; j, k, i, n, max, ind: longint; bn : boolean; begin read (n); for i := 1 to n do read (y1[i], y2[i]); repeat bn := true; for i := 1 to n - 1 do for j := i + 1 to n do begin if (b[i] = 0) and (b[j] = 0) then if ((y1[i] > y1[j]) and (y2[i] < y2[j])) or ((y1[i] < y1[j]) and (y2[i] > y2[j])) or (y1[i] = y1[j]) or (y2[i] = y2[j]) then begin bn := false; inc (a[i]); inc (a[j]); end; end; max := 0; for i := 1 to n do if a[i] > max then begin max := a[i]; ind := i; end; if max > 0 then begin inc (k); b[ind] := 1; end; for i := 1 to n do a[i] := 0; until bn = true; writeln (k); end. Try test 5 5 3 4 6 2 4 3 1 7 5 Correct answer is 2, but your - 3. You can remove second and third ties. #include <iostream> using namespace std; void main() { int y1[100]; int y2[100]; int n,i,q,u; int ct[100]; int cty1[10000]; int cty2[10000]; int cr = 0,res = 0; int spect[100]; cin >> n; for(i = 0; i<n; i++) { cin >> y1[i]; cin >> y2[i]; ct[i] = 0; } for(i = 0; i<n; i++) { for(q = i+1; q<n; q++) { if ( ((y1[i]>=y1[q]) && (y2[i]<=y2[q])) || ((y1[i]<=y1[q]) && (y2[i]>=y2[q])) ) { ct[i]++; ct[q]++; cty1[cr] = i; cty2[cr] = q; cr++; } } } while(cr!=0) { int max = ct[0]; int mid = 0; int l = 0; for(u = 0; u<n; u++) { if (ct[u]>max) { max = ct[u]; mid = u; } } for(u = 0; u<n; u++) { if (ct[u]==max) { spect[l] = u; l++; } } /////////// int mini = 10000; int minid = spect[0]; for(u = 0; u<l; u++) { int cur = 0; for(int y = 0; y<l; y++) if (y!=u) for(int o = 0; o<cr; o++) if ( (cty1[o]==spect[u] && cty2[o]==spect[y]) || (cty2[o]==spect[u] && cty1[o]==spect[y]) ) cur++; if (cur<mini) { minid = spect[u]; mini = cur; } } /////////// mid = minid; for(i = 0; i<cr; i++) { if (cty1[i]==mid) { ct[cty2[i]]--; if (i!=cr-1) { cty1[i] = cty1[cr-1]; cty2[i] = cty2[cr-1]; } cr--; i--; } else { if (cty2[i]==mid) { ct[cty1[i]]--; if (i!=cr-1) { cty1[i] = cty1[cr-1]; cty2[i] = cty2[cr-1]; } cr--; i--; } } } ct[mid] = 0; res++; } cout << res; cin >> res; } P.S. it works with 5 5 3 4 6 2 4 3 1 7 5 Some new tests were added. 35 authors got WA. The next rejudge will take place if new tricky tests will be found. Edited by author 24.11.2006 22:45 New rejudge has been finished. 22 submits lost AC verdict. Thanks to anus(USU) for idea of some good tests. What is this. I'm WA on test 9. Help me I like DP, but now I cann't do it! May be the weather is bed, that's why... Please, help me! Thanks. var x,y:array[1..100] of integer; b:array[1..100] of boolean; i,n,otv:integer; ex:boolean; procedure reflesh; var i,max,col,j,yd:integer; begin ex:=false; for i:=1 to n do if b[i] then begin col:=0; for j:=1 to n do if (i<>j) and b[j] then begin if (x[i]=y[i]) then break; if (x[i]<y[i]) then if ((x[j]>x[i]) and (y[i]>y[j])) then begin inc(col); yd:=j; end; if (x[i]>y[i]) then if ((x[i]>x[j]) and (y[i]<y[j])) then begin inc(col); yd:=j; end; end; if col=1 then begin inc(otv); b[yd]:=false; ex:=true; break; end; end; end; begin { assign(input,'c:\test.txt'); reset(input);} ex:=true; readln(n); fillchar(b,sizeof(b),true); for i:=1 to n do readln(x[i],y[i]); while ex do reflesh; writeln(otv); end. Try this 3 1 5 2 3 3 4 The right answer - 1. You should use DP. I am very weak in the theory. My algorithm not true. Whether you can give me idea. (my mail xxvictorxx@mail.ru (if has overlooked)) you algo wrong. You need use DP. i got AC O(N^2/2) I've seen there are many WA's for this problem, even if you only need basic knowledge to solve it. Although i find my source perfect, i cannot imagine what makes it receive Wrong Answer on test #3 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define MAXN 101 typedef struct shit { int x, y; }; shit a[MAXN]; int N, i, j; int m[MAXN]; int cmp(shit a, shit b) { return a.x < b.x ? 1 : 0; } int main(void) { scanf("%d\n", &N); for (i = 0; i < N; i ++) scanf("%d %d\n", &(a[i].x), &(a[i].y)); sort(a, a + N, cmp); int ans = 1; m[0] = 1; for (i = 1; i < N; i ++) { m[i] = 1; for (j = 0; j < i; j ++) if (a[j].y < a[i].y && 1 + m[j] > m[i]) m[i] = 1 + m[j]; if (m[i] > ans) ans = m[i]; } printf("%d\n", N - ans); return 0; } "Although i find my source perfect, i cannot imagine what makes it receive Wrong Answer on test #3..." Oh yeah... I couldn't find bug in your source, but since I had many problems myself on this one I can send you my code. E-mail me on dporobic at gmail dot com . If you want to know how to solve it, write me on shteynerserg@mail.ru It also can be done in O(K * logK). O(N^2) is with DP, a classic problem (longest increasing subset) My AC solution with DP outputs 2 in this test: 6 0 3 1 0 2 2 3 5 4 1 5 4 But the correct answer is 3. Maybe this test should be added to the test set. I think so :) I remember the optimal answer for sets of ties with numbers k..l for all k,l (for all segments). The optimal answer Ans(k,l+1)= max(Ans(k,l),S+1), where S is the sum of optimal answers for all segments in k..l, that any tie of any of these segments doesn't intersect (l+1)th tie. (In the first case we delete (l+1)th tie, in the second case leave (l+1) and delete all ties, intersecting it.) This algorith is not correct, because ties in the optimal solutions can intersect, so sum of the optimal solutions may not be solution at all. My test is the simple example of it. But this algorith gets AC, and this is very strange. |
|