Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | Опечатка в условии | Musin | 1424. Маршрутка | 15 май 2020 18:22 | 1 | В один из дней небеса сжалились на Сергеем Александровичем на-> над | WA18? | fatnot | 1424. Маршрутка | 8 янв 2020 23:52 | 1 | WA18? fatnot 8 янв 2020 23:52 How can i fix WA18? Im solving using greedy algo | A Test | joaopfg | 1424. Маршрутка | 4 авг 2018 03:40 | 1 | A Test joaopfg 4 авг 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. Маршрутка | 17 авг 2013 08:12 | 1 | | How to improve? | luckysundog | 1424. Маршрутка | 27 фев 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. Маршрутка | 3 фев 2011 22:55 | 1 | WA3 bagens 3 фев 2011 22:55 Getting wrong answer. Can anybody post tests, please? | Simple problem or weak tests? | Fyodor Menshikov | 1424. Маршрутка | 29 дек 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. Маршрутка | 17 авг 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. Маршрутка | 16 янв 2010 17:46 | 8 | WTF? Aleksey [TeXHuK] 11 ноя 2006 15:12 Please, show 9 test. Who make this problem, public your solution, please. Re: WTF? Samsonov Alex [USU] 11 ноя 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 ноя 2006 16:17 Without test very hardly found bugz in code :-( Re: WTF? Samsonov Alex [USU] 11 ноя 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 сен 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 май 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 янв 2010 17:46 | WA #5 | Igor Mihajlovic | 1424. Маршрутка | 19 сен 2009 05:58 | 7 | WA #5 Igor Mihajlovic 10 сен 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 июл 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. Маршрутка | 19 апр 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. Маршрутка | 5 апр 2009 00:09 | 1 | a test Kazakov Sergey (CK) 5 апр 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. Маршрутка | 14 ноя 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. Маршрутка | 6 авг 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. Маршрутка | 1 июн 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. Маршрутка | 20 май 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? |
|
|