Show all threads Hide all threads Show all messages Hide all messages | Опечатка в условии | Musin | 1424. Minibus | 15 May 2020 18:22 | 1 | В один из дней небеса сжалились на Сергеем Александровичем на-> над | WA18? | fatnot | 1424. Minibus | 8 Jan 2020 23:52 | 1 | WA18? fatnot 8 Jan 2020 23:52 How can i fix WA18? Im solving using greedy algo | A Test | joaopfg | 1424. Minibus | 4 Aug 2018 03:40 | 1 | A Test joaopfg 4 Aug 2018 03:40 A test which help me to discover a bug in my code: 5 1 4 1 1 2 2 4 4 5 3 5 Answer: 3 1 2 3 | a test for wa 8 | binwin20 | 1424. Minibus | 17 Aug 2013 08:12 | 1 | | How to improve? | luckysundog | 1424. Minibus | 27 Feb 2011 22:30 | 1 | Stupid O(M*K) solution works about 0.421s (modified "greedy activity selector"). But i heard about segment_tree/heap solutions - i can't understand what are they speaking about. How to improve O(M*K) ? | WA3 | bagens | 1424. Minibus | 3 Feb 2011 22:55 | 1 | WA3 bagens 3 Feb 2011 22:55 Getting wrong answer. Can anybody post tests, please? | Simple problem or weak tests? | Fyodor Menshikov | 1424. Minibus | 29 Dec 2010 20:35 | 19 | My solution should use 2 * M * K indexations of linear array in the worst case (100 000 000 for max M and K) but works about 0.5s, twice less than time limit, and it is Java! Does it mean that so simple algorithm is enough or that tests are weak? Edited by author 15.05.2007 02:27 I used greedy algo, pascal, 0.265sec works, O(2*M*K) too. For such strong authors request of failed solver! Give us short clarification of this great optimization problem! What is more simple prototipe of it? What class of the problem? Graphs?DP? May be.... Timus Online Judge server is fast enough to perform more than 100000000 operations per second. The problem is based on the Activity Selection problem. Timus Online Judge server is fast enough to perform more than 100000000 operations per second. The truth of this statement depends on operation kind. Recently I solved problem in which 50 000 000 operations * and % on 64-bit integers worked 2s. Dmitry, do you know more precise numbers, how many operations of each kind the server can execute per second? For example linear array indexations - 180 bln, long multiplication - 100 bln and so on... Just write a kind of performance mark program, submit it and you will get exactly what you want. Then you may post the results here and everyone will appreciate your work. Is Activity Selection problem standard internet term? What is more simple prototipe of it? I don't know. What class of the problem? Graphs?DP? May be.... I'd said simulation. And I think Alexander Kouprin's definition "greedy" is right. The problem gets simpler if you change its model. You can allow driver to debus any boarded passenger at any stop < F[i] refunding the passenger all her money P. The driver in this case would get the same amound of money as if he would not board that debussed half-way passengers at all. Edited by author 15.05.2007 14:09I'd said it's sorting problem. :) You have segments of way: first point and last. Your task is how to combinate maximum of segment in K lines. This lines can be severed inside of itself and have big holes. I'd said it's sorting problem. :) I used sorting too, but I think the main problem is to devise what to do after sorting. I think it's a lecture hall assignment problem. One thing is that number of lecture halls here is limited by M... Thank for "lecture hall assignment" brand! I tried to solve it running Greedy-Activity-Selector M times. But WA at test 4. What is wrong with such approach? Gready _Activity_Selector of course. But with auxiliary subproblem: Let we have a set S={[ai,bi]} intervals chosen to some moment and according with greedy should include in S new segment [c,d]. Can we do it without excess of M. For, we must solve the problem of maximal overlapping value. I used augmented red-black tree as in Cormen but have very bad time 0.843 AC. Intuition says that good times taken due better ways of solving auxiliary problem. Edited by author 29.09.2007 14:41 Thanks, I realised that. I simply store now all stations beginnings in an array (maximum K). I initialise it with M value for each element. Now, for each request I go from start to end and check if all elements are non-zero (not including the end). If that requirement is met, I add the request to the result and decrement all checked elements By the way. Should we sort just time ending of the activity? In that case I get WA#4, If I sort beginnings in decreasing order in case of end equals, I get TLE #4 my algo is O(N + K *log(M)) -> AC in 0.1 i use segment tree and got AC in 0.109. what's the best algo? order of my algo is O((n+m)logn + klogk). GOOD LUCK!!! | Test #7 | 2lazy | 1424. Minibus | 17 Aug 2010 08:45 | 5 | Gettin' wrong answer. Can anybody post it, please!? 10 2 5 1 1 6 1 4 4 5 5 8 7 9 Answer: 5 1 2 3 4 5 May be test 7 is another thing.I don't know exactly. Edited by author 16.05.2009 11:57 I got wa7 too. But my algo give right answers in all tests at timus :( I use sort and greedy :( I don't understand why sort and greedy not work? this is not test 7 this test works for me i also use sort + greedy and i dont know why i get wa7 Try this one: 10 3 5 1 1 2 1 5 1 7 6 8 4 9 The answer is: 5 1 2 3 4 5 | WTF? | Aleksey [TeXHuK] | 1424. Minibus | 16 Jan 2010 17:46 | 8 | WTF? Aleksey [TeXHuK] 11 Nov 2006 15:12 Please, show 9 test. Who make this problem, public your solution, please. Re: WTF? Samsonov Alex [USU] 11 Nov 2006 15:57 Probably you should try to find a bug in your code. It doesn't look like this problem have any troubles with test data. Re: WTF? Aleksey [TeXHuK] 11 Nov 2006 16:17 Without test very hardly found bugz in code :-( Re: WTF? Samsonov Alex [USU] 11 Nov 2006 19:42 But actually you have to obtain this useful skill. I have WA9 too. try test: 3 1 2 1 1 3 1 2 Re: WTF? AlexF [USTU Frogs] 18 Sep 2007 10:16 I don't think that 9 test has smth special) I had a very stupid bug in my code and so had WA#9) Failed test was 10 1 7 1 1 8 2 3 3 4 4 5 5 6 6 7 7 8 IMHO Cool problem) Re: WTF? Vladimir Mihajlovski 27 May 2008 00:41 I also fall on test 9, but both of these tests work fine. What was the bug you corrected? Edited by author 27.05.2008 02:28 WA9 Programmer 16 Jan 2010 17:46 | WA #5 | Igor Mihajlovic | 1424. Minibus | 19 Sep 2009 05:58 | 7 | WA #5 Igor Mihajlovic 10 Sep 2008 20:56 i use a lecture hall algo here it is: #include <iostream.h> struct Putnik { int s; int f; int b; int br; }; int min(int x,int y) { return x<y?x:y; } void merge(Putnik *a,int f,int s,int n) {
int i,j,k; Putnik *b; b=new Putnik[n-f]; k=0; i=f; j=s; while(i<s && j<n) { if (a[i].f<a[j].f) b[k++]=a[i++]; else b[k++]=a[j++]; } while(i<s) b[k++]=a[i++]; while(j<n) b[k++]=a[j++]; for(i=0;i<k;i++) a[i+f]=b[i]; delete [] b; } main() { int n,k,m,p,i,j,z,l,mn; Putnik pt; Putnik *a; cin >>n>>m>>k>>p; a=new Putnik[k]; for(i=0;i<k;i++) { cin>>a[i].s; cin>>a[i].f; a[i].b=1; a[i].br=i+1; }
for(i=1;i<k;i*=2) for(j=0;j<k;j+=2*i) if (j+i<k) merge(a,j,j+i,min(k,j+2*i));
z=k; for(i=0;i<m && z;i++) { l=0; while(a[l].b==0) l++; pt=a[l]; a[l].b=0; z--; for(j=l+1;j<k;j++) if (a[j].b && a[j].s>=pt.f) { z--; a[j].b=0; pt=a[j]; } }
mn=(k-z)*p; cout<<mn<<"\n"; for(i=0;i<k;i++) if (a[i].b==0) cout<<a[i].br<<" "; delete [] a;
} and get wa# 5 i dont see a bug here plz help me some tests would be nise also Edited by author 10.09.2008 21:58 Try this: 10 2 4 1 1 4 1 1 4 5 3 6 The answer is: 4 1 2 3 4 tried it's ok still wa Edited by author 16.11.2008 06:23 Edited by author 16.11.2008 06:23 10 3 10 1 1 2 2 6 1 6 3 6 4 6 5 6 1 3 7 9 1 4 1 5 output 7 1 7 9 6 2 5 8 thx it was a dum error i passed test 5 but wa7 now idk why Re: WA #5 3a[3.141592..]Jlu 19 Jul 2009 23:55 test : 10 2 4 1 1 4 1 1 4 5 3 6
is incorrect!!! S[i] < F[i] ;) this test is incorrect: s[i] != f[i] !! | WA on #14.Can somebody give me some tests to help me find out the mistakes? | yuyan | 1424. Minibus | 19 Apr 2009 20:26 | 2 | Up to now.I can't find what's wrong with my program? I use greedy algorithm with heap. Here is my code: program mini; const maxn=201000; var h,p,l,list:array [0..maxn] of longint; vis:array [0..maxn] of boolean; g,next,v,d,g1,next1,v1:array [0..maxn] of longint; i,j,k,m,n,r,q,e,t:longint; ans:qword; procedure insert(u:longint); begin inc(e);next[e]:=g[u];g[u]:=e;v[e]:=r;d[e]:=j; end; procedure ins(u:longint); begin next1[r]:=g1[u];g1[u]:=r;v1[r]:=r; end; procedure swap(var x,y:longint); var t:longint; begin t:=x;x:=y;y:=t; end; procedure up(k:longint); begin while (k>1) and (h[k shr 1]<h[k]) do begin swap(h[k shr 1],h[k]); swap(l[k shr 1],l[k]); p[l[k shr 1]]:=k shr 1;p[l[k]]:=k; k:=k shr 1; end; end; procedure down(k:longint); begin repeat j:=k; if (j shl 1<=t) and (h[j shl 1]>h[k]) then k:=j shl 1; if (j shl 1+1<=t) and (h[j shl 1+1]>h[k]) then k:=j shl 1+1; if j<>k then begin swap(h[j],h[k]); swap(l[j],l[k]); p[l[j]]:=j;p[l[k]]:=k; end; until j=k; end; procedure init; begin read(n,m,k,q); for r:=1 to k do begin read(i,j);if i=j then repeat until false; if i>j then swap(i,j); insert(i); ins(j); end; end; procedure solve; begin ans:=0;t:=0; for i:=1 to n do begin r:=g1[i]; while r<>0 do begin if vis[v1[r]] then begin inc(ans);list[ans]:=v1[r]; inc(m);vis[v1[r]]:=false; h[p[v1[r]]]:=h[t];p[l[t]]:=p[v1[r]];l[p[l[t]]]:=l[t];dec(t); down(p[v1[r]]); end; r:=next1[r]; end; r:=g[i]; while r<>0 do begin dec(m);vis[v[r]]:=true; inc(t);l[t]:=v[r];p[v[r]]:=t;h[t]:=d[r]; up(t); r:=next[r]; end; while m<0 do begin vis[l[1]]:=false;h[1]:=h[t];l[1]:=l[t];p[l[1]]:=1;dec(t); down(1); inc(m); end; r:=g1[i]; while r<>0 do begin if vis[v1[r]] then begin inc(ans);list[ans]:=v1[r]; inc(m);vis[v1[r]]:=false; h[p[v1[r]]]:=h[t];p[l[t]]:=p[v1[r]];l[p[l[t]]]:=l[t];dec(t); down(p[v1[r]]); end; r:=next1[r]; end; end; end; procedure print; begin writeln(ans*q); if ans=0 then exit; for i:=1 to ans-1 do write(list[i],' ');writeln(list[ans]); end; begin assign(input,'mini.in');reset(input); assign(output,'mini.out');rewrite(output); init; solve; print; close(input);close(output); end.
Could you tell me what's wrong with my program?Or let me refer to your AC program? Thanks. | a test | Kazakov Sergey (CK) | 1424. Minibus | 5 Apr 2009 00:09 | 1 | a test Kazakov Sergey (CK) 5 Apr 2009 00:09 10 2 5 1 1 6 1 4 4 5 5 8 7 9 Answer: 5 1 2 3 4 5 | Second line for K=0 | partisan (Andrey Korotkov) | 1424. Minibus | 14 Nov 2008 19:17 | 1 | Does the (empty) second line needed if K=0? | I don't use heap, but I've got wa7. Please give me some contrtests. Thanks. | Crash_access_violation | 1424. Minibus | 6 Aug 2008 22:13 | 3 | CONST MaxN = 50000; TYPE List = Record s, f, t : Longint; b : BooLean; End; VAR N, M, K, P, Res : Longint; A : Array [1 .. MaxN] of List; Ans : Array [1 .. MaxN] of Longint; PROCEDURE In_Data; Var i : Longint; Begin ReadLn(N, M, K, P); for i := 1 to K do begin ReadLn(A[i].s, A[i].f); A[i].t := i; A[i].b := false; end; End; PROCEDURE qSort(L, R : Longint); Var i, j, x, y, temp : Longint; Begin i := L; j := R; x := A[(L + R) div 2].f; y := A[(L + R) div 2].s; Repeat while (A[i].f < x) or ((A[i].f = x) and (A[i].s < y)) do inc(i); while (A[j].f > x) or ((A[j].f = x) and (A[j].s > y)) do dec(j); if i <= j then begin temp := A[i].s; A[i].s := A[j].s; A[j].s := temp; temp := A[i].f; A[i].f := A[j].f; A[j].f := temp; temp := A[i].t; A[i].t := A[j].t; A[j].t := temp; inc(i); dec(j); end; UntiL i > j; if L < j then qSort(L, j); if i < R then qSort(i, R); End; PROCEDURE Solve; Var i, j, temp : Longint; Begin j := 1; while A[j].b and (j < K) do inc(j); if (j = K) and A[j].b then Exit; temp := 0; for i := j to K do if not A[i].b then if temp <= A[i].s then begin inc(Res); Ans[Res] := A[i].t; A[i].b := true; temp := A[i].f; end; End; PROCEDURE Out_Data; Var i : Longint; Begin WriteLn(Res * P); for i := 1 to Res do Write(Ans[i], ' '); End; PROCEDURE Run; Var i : Longint; Begin In_Data; if K > 1 then qSort(1, K); Res := 0; for i := 1 to M do Solve; Out_Data; End; BEGIN Run; END. You Algo is Wrong for 100 percent. First i solved as you now i AC CONST MaxN = 50000; TYPE List = Record s, f, t : Longint; b : BooLean; End; VAR N, M, K, P, Res : Longint; A : Array [1 .. MaxN] of List; Ans : Array [1 .. MaxN] of Longint; PROCEDURE In_Data; Var i : Longint; Begin ReadLn(N, M, K, P); for i := 1 to K do begin ReadLn(A[i].s, A[i].f); A[i].t := i; A[i].b := false; end; End; PROCEDURE qSort(L, R : Longint); Var i, j, x, y, temp : Longint; Begin i := L; j := R; x := A[(L + R) div 2].f; y := A[(L + R) div 2].s; Repeat while (A[i].f < x) or ((A[i].f = x) and (A[i].s < y)) do inc(i); while (A[j].f > x) or ((A[j].f = x) and (A[j].s > y)) do dec(j); if i <= j then begin temp := A[i].s; A[i].s := A[j].s; A[j].s := temp; temp := A[i].f; A[i].f := A[j].f; A[j].f := temp; temp := A[i].t; A[i].t := A[j].t; A[j].t := temp; inc(i); dec(j); end; UntiL i > j; if L < j then qSort(L, j); if i < R then qSort(i, R); End; PROCEDURE Solve; Var i, j, temp : Longint; Begin j := 1; while A[j].b and (j < K) do inc(j); if (j = K) and A[j].b then Exit; temp := 0; for i := j to K do if not A[i].b then if temp <= A[i].s then begin inc(Res); Ans[Res] := A[i].t; A[i].b := true; temp := A[i].f; end; End; PROCEDURE Out_Data; Var i : Longint; Begin WriteLn(Res * P); for i := 1 to Res do Write(Ans[i], ' '); End; PROCEDURE Run; Var i : Longint; Begin In_Data; if K > 1 then qSort(1, K); Res := 0; for i := 1 to M do Solve; Out_Data; End; BEGIN Run; END. what idea in your solution? sory for my bad english Edited by author 06.08.2008 22:14 | Just a test case my program failed :) | DK [Samara SAU 1: X2008] | 1424. Minibus | 1 Jun 2008 22:38 | 1 | 5 2 3 1 1 3 3 4 2 5 answer is 3 1 2 3 | Why WA #2 ? | Dimitrije | 1424. Minibus | 20 May 2008 16:34 | 2 | I think that my program is correct and i can't find a mistake. Can anyone help me with some test? |
|
|