Hi everybody! I solved this problem, but my algo is O(n log n) and it works 0.14 seconds. Idea of my algorithm is to find two vectors witch sum is not greater than L and change them on their sum. It it possible to prove that such two vectors exists if there are more than two vectors in set. Do this procedure while we can find such two vectors. But many people solved it much better... I want to know this solution. Consider that for any vectors a,b,c, |a|,|b|,|c| <= L exists integers u, v, w, |u|,|v|,|w|=1, |ua+vb+wc|<=L It is not right: what are u, v, w for a = (5,0) b = (0,0) c = (0,5)??? L = 5, of course Many people above have solved this problem, but they didn't express their thought well. The key is this: if there are AT LEAST 3 vectors in the set with module not exceeed L, we can ALWAYS choose 2 of them and, with choosing the direction, make the module of their sum not exceed L. Thus, we can reduce the amount of vectors by this until there are only TWO. At last, for any two vectors which has the module not longer than L, we can make the module of their sum not exceed L*sqrt(2). And that's all the key. What's left is to find a way to programme. Maybe it will help you, maybe not for my poor English. Thank you for well-expressed idea. It really helps to understand the idea of solution to the problem. Yep =) 2 Victor Barinov (TNU): complexity of my solution is not O(NlogN), but even O(N^2)! And it's AC 0.015 sec. Just use the same heuristics as in disjoint sets. Edited by author 04.07.2009 18:52 Edited by author 04.07.2009 18:56 Can somebody, please, prove the idea described by 198808xc? P.S. I've solved this problem using lot of cheating (brute force+random sort+heuristic) and would like to know, what is right solution. P.P.S. To prove it we should just realize the fact, that there is always 2 vectors, such, that angle between them is >=120 degrees. So their sum is <=L. Edited by author 14.07.2009 19:24 If you only two vectors, you're out of luck of getting |X+Y| and |X-Y| <= L when angle between them is more than 60 degrees (so together with their sum/diff they form an equilateral triangle). Now if you have 3 vectors, these 3 vectors and their reflections form a lotus (or a hexagon) which covers everything, so there will always be a pair with |X+Y| or |X-Y| <= L. When you're down to just 2 vectors, the worst situation is 90 degree angle which yields sqrt(2)*L. Your algo should be O(n) ;) I don't quite understand how write it with complexity of O(n log n) What is the answer for test: 4 10 0 10 10 0 1 1 5 -5 YES +--+ But after three steps P = (0,10) - (10,0) - (1,1) = (-11,9); Distance to Z = (0,0) equal to sqrt(11*11+9*9) = sqrt(202) = 14.2126 > sqrt(2)*10 = 14.1421 Hmm, well, you might be onto something! The thing is, my program doesn't have "WRONG ANSWER" in it at all, and now that i look at it again i don't really remember why :) You can try to email one of the admins about this. Edit @below: ohhh right. By now i already forgot about this detail. Thanks! Edited by author 26.09.2016 16:04 "...and she wants him to move off her not farther than by the square root of 2 multiplied by L (sqrt(2)L) IN THE END OF HIS WALK." Your case describes the distance after 3 steps, not 4. Nikifor is allowed to move farther in the middle of the travel. Edited by author 26.09.2016 14:36 Edited by author 26.09.2016 14:36 Edit my first comment, see the next one for complete explanation. I can share my code via email if you don't have an access to it. Edited by author 21.12.2015 22:46 My AC solution fails on following test 3 100 71 70 99 1 -71 70 It returns YES +-+ which means (71; 70) - (99; 1) + (-71; 70) = (-99; 139), |(-99; 139)|~170.65 > 141.4. But it is really strange that my AC solution contains awful mistake in sorting. In fact, sort doesn't work at all in my AC solution and output depends on vectors order! I wonder how could this code pass all tests. And I wonder how the code with fixed sorting (but still incorrect) fails on 53-th test only. Please add mentioned test. Edited by author 21.12.2015 22:48 9 9 0 9 9 0 5 4 4 5 0 9 9 0 -5 4 -4 5 9 0 program acm_1130; type vec=record x,y:longint; end; var w,a:array[1..3]of vec; c,b:vec; i,n,nn:longint; L:longint; p:array[0..10000,1..3,1..2] of byte; q:array[0..10000,1..3]of shortint; f:boolean; procedure delta(nn,r:longint); var j:longint; begin if nn=0 then exit; for j:=1 to 2 do if p[nn,r,j]>0 then begin q[nn-1,p[nn,r,j]]:=-q[nn-1,p[nn,r,j]]; delta(nn-1,p[nn,r,j]); end; end; procedure minn(i:longint); begin if sqr(a[1].x+a[2].x)+sqr(a[1].y+a[2].y)<=sqr(L) then begin w[1].x:=a[1].x+a[2].x; w[1].y:=a[1].y+a[2].y; w[2]:=a[3]; q[i,1]:=1; q[i,2]:=1; q[i,3]:=1; p[i+1,1,1]:=1; p[i+1,1,2]:=2; p[i+1,2,1]:=3; exit; end; if sqr(a[1].x-a[2].x)+sqr(a[1].y-a[2].y)<=sqr(L) then begin w[1].x:=a[1].x+a[2].x; w[1].y:=a[1].y+a[2].y; w[2]:=a[3]; q[i,1]:=1; q[i,2]:=-1; q[i,3]:=1; p[i+1,1,1]:=1; p[i+1,1,2]:=2; p[i+1,2,1]:=3; exit; end; if sqr(a[1].x+a[3].x)+sqr(a[1].y+a[3].y)<=sqr(L) then begin w[1].x:=a[1].x+a[3].x; w[1].y:=a[1].y+a[3].y; w[2]:=a[2]; q[i,1]:=1; q[i,2]:=1; q[i,3]:=1; p[i+1,1,1]:=1; p[i+1,1,2]:=3; p[i+1,2,1]:=2; exit; end; if sqr(a[1].x-a[3].x)+sqr(a[1].y-a[3].y)<=sqr(L) then begin w[1].x:=a[1].x-a[3].x; w[1].y:=a[1].y-a[3].y; w[2]:=a[2]; q[i,1]:=1; q[i,2]:=1; q[i,3]:=-1; p[i+1,1,1]:=1; p[i+1,1,2]:=3; p[i+1,2,1]:=2; exit; end; if sqr(a[2].x+a[3].x)+sqr(a[2].y+a[3].y)<=sqr(L) then begin w[1].x:=a[2].x+a[3].x; w[1].y:=a[2].y+a[3].y; w[2]:=a[2]; q[i,1]:=1; q[i,2]:=1; q[i,3]:=1; p[i+1,1,1]:=2; p[i+1,1,2]:=3; p[i+1,2,1]:=1; exit; end; if sqr(a[2].x-a[3].x)+sqr(a[2].y-a[3].y)<=sqr(L) then begin w[1].x:=a[2].x-a[3].x; w[1].y:=a[2].y-a[3].y; w[2]:=a[2]; q[i,1]:=1; q[i,2]:=1; q[i,3]:=-1; p[i+1,1,1]:=2; p[i+1,1,2]:=3; p[i+1,2,1]:=1; exit; end; end; begin read(n); read(L); if n=1 then begin write('+'); exit; end; if n=2 then begin read(c.x,c.y); read(b.x,b.y); if sqr(c.x-b.x)+sqr(c.y-b.y)<sqr(c.x+b.x)+sqr(c.y+b.y) then writeln('+-') else writeln('++'); exit; end; for i:=1 to 3 do read(a[i].x,a[i].y); fillchar(p,sizeof(p),0); fillchar(q,sizeof(q),1); minn(0); a[1]:=w[1]; a[2]:=w[2]; for i:=1 to n-3 do begin read(a[3].x,a[3].y); minn(i); a[1]:=w[1]; a[2]:=w[2]; end; f:=true; if sqr(a[1].x-a[2].x)+sqr(a[1].y-a[2].y)<sqr(a[1].x+a[2].x)+sqr(a[1].y+a[2].y) then f:=true else f:=false; if f then begin nn:=n-2; delta(nn,2); end; writeln('YES'); for i:=1 to 3 do if q[0,i]>0 then write('+') else write('-'); for i:=1 to n-3 do if q[i,3]>0 then write('+') else write('-'); end. Edited by author 07.01.2013 14:31 - Edited by author 20.11.2011 03:03 I am using recursion to solve the problem. But, I get WA8. I have debugged the code; but could not find any issues. What is the test case? Thanks, program ural; var n,l,i,p,q:integer; x,y:array[1..2]of integer; a,b:integer; c,u:array[1..10000]of boolean; begin readln(n,l); if n=1 then begin writeln('YES'); writeln('+'); halt; end; l:=l*l; readln(x[1],y[1]); readln(x[2],y[2]); c[1]:=true; c[2]:=true; for i:=3 to n do begin readln(a,b); p:=x[1]+a; q:=y[1]+b; if sqr(p)+sqr(q)<=l then begin x[1]:=p; y[1]:=q; u[i]:=true; c[i]:=true; continue; end; p:=x[1]-a; q:=y[1]-b; if sqr(p)+sqr(q)<=l then begin x[1]:=p; y[1]:=q; u[i]:=true; continue; end; p:=x[2]+a; q:=y[2]+b; if sqr(p)+sqr(q)<=l then begin x[2]:=p; y[2]:=q; c[i]:=true; continue; end; p:=x[2]-a; q:=y[2]-b; if sqr(p)+sqr(q)<=l then begin x[2]:=p; y[2]:=q; continue; end; end; if sqr(x[1]+x[2])+sqr(y[1]+y[2])>2*l then c[2]:=not c[2]; writeln('YES'); write('+'); if c[2] then write('+') else write('-'); for i:=3 to n do begin if u[i] then begin if c[i] then write('+') else write('-'); end else begin if c[i]=false then c[i]:=not c[2]; if c[i] then write('+') else write('-'); end; end; end. try this test 3 10 10 0 0 10 5 5 any hint? while i have more than two vectors, i find two of them with |sum|<=L. in the end i have two of them and try to sum in different ways, but wa5 Program FLY_ural1130; Const max=30000; Var n,i,l,now,head:longint; p:array[1..max]of boolean; x,y,m,q,w,k:array[1..max]of longint; Function check(f,u:longint):longint; var a,b,c:longint; begin a:=sqr(x[f])+sqr(y[f]); b:=sqr(x[u])+sqr(y[u]); c:=sqr(x[f]-x[u])+sqr(y[f]-y[u]); if (a+b-c)>sqrt(a*b) then exit(1) else if(a+b-c)<=-sqrt(a*b) then exit(2) else exit(3); end; Procedure back(u:longint); begin if q[u]=0 then begin p[u]:=not p[u]; exit; end; back(q[u]); back(w[u]); end; Procedure change_mod1(a,b:longint); begin inc(head); x[head]:=x[a]-x[b]; y[head]:=y[a]-y[b]; q[head]:=m[a]; w[head]:=m[b]; m[head]:=head; back(w[head]); end; Procedure change_mod2(a,b:longint); begin inc(head); x[head]:=x[a]+x[b]; y[head]:=y[a]+y[b]; q[head]:=m[a]; w[head]:=m[b]; m[head]:=head; end; Procedure exchange(a,b:longint); var u:longint; begin u:=x[a]; x[a]:=x[b]; x[b]:=u; u:=y[a]; y[a]:=y[b]; y[b]:=u; u:=m[a]; m[a]:=m[b]; m[b]:=u; u:=m[a]; m[a]:=m[b]; m[b]:=u; u:=q[a]; q[a]:=q[b]; q[b]:=u; u:=w[a]; w[a]:=w[b]; w[b]:=u; end; Function checkzero(u:longint):boolean; begin if (x[u]=y[u])and(y[u]=0) then exit(true) else exit(false); end; Begin {assign(input,'1130.in'); reset(input); assign(output,'1130.out'); rewrite(output); } readln(n,l); head:=n; now:=1; for i:=1 to n do begin readln(x[i],y[i]); p[i]:=true; m[i]:=i; end; while head>1+now do begin if checkzero(now) then begin inc(now); continue; end; if checkzero(now+1) then begin inc(head); x[head]:=x[now]; y[head]:=y[now]; m[head]:=m[now]; inc(now,2); continue; end; if checkzero(now+2) then begin inc(head); x[head]:=x[now]; y[head]:=y[now]; m[head]:=m[now]; inc(now); inc(head); x[head]:=x[now]; y[head]:=y[now]; m[head]:=m[now]; inc(now,2); continue; end; case check(now,now+1) of 1:change_mod1(now,now+1); 2:change_mod2(now,now+1); 3:case check(now,now+2) of 1:begin change_mod1(now,now+2); // exchange(now+1,now+2); inc(now); inc(head); x[head]:=x[now]; y[head]:=y[now]; m[head]:=m[now]; end; 2:begin change_mod2(now,now+2); inc(now); inc(head); x[head]:=x[now]; y[head]:=y[now]; m[head]:=m[now]; end; 3:case check(now+1,now+2) of 1:begin change_mod1(now+1,now+2); inc(head); x[head]:=x[now]; y[head]:=y[now]; m[head]:=m[now]; inc(now); end; 2:begin change_mod2(now+1,now+2); // exchange(now,now+2); inc(head); x[head]:=x[now]; y[head]:=y[now]; m[head]:=m[now]; inc(now); end; end; end; end; inc(now,2); end; if sqr(x[now]+x[head])+sqr(y[now]+y[head])>sqr(l) then back(m[head]); writeln('YES'); for i:=1 to n do if p[i] then write('+') else write('-'); close(output); End. Edited by author 21.11.2008 22:52 Edited by author 21.11.2008 22:52 Many people above have solved this problem, but they didn't express their thought well. The key is this: For ANY 3 vectors in the set with module not exceeed L, we can ALWAYS choose 2 of them and, with choosing the direction, make the module of their sum not exceed L. (this can be proved by geometry) So, we choose the two and reduce them to one (simply adding them and record the direction). Thus, we can reduce the amount of vectors by this until there are only TWO. At last, for any two vectors which has the module not longer than L, we can make the module of their sum not exceed L*sqrt(2). And that's all the key. What's left is to find a way to programme. Use tree to store the father-son relation is a good choice. Maybe it will help you, maybe not for my poor English. A new set of tricky tests has been added to this problem. 59 authors have lost AC after rejudge. [ There was a stupid question :) ] I have TLE#5. Why? My program looks like ... Input(); while (abs(x)>l || abs(y)>l) { for(i=0;i<n;++i) if (...) { ... } } Output(); And that's all! Edited by author 15.05.2007 20:21 Edited by author 15.05.2007 20:32 subj... Here's my prog. [code deleted] Edited by author 17.05.2007 19:48 Thank U, but I have just seen Nazarov Denis's subject. XueMao has the same algo as mine. But His AC vs My TLE#12. I want to understand my mistake... Ha-ha! You can try to solve it from O(n^2) but I think you never get AC if you using this algorithm! XueMao have TLE#12 too! http://acm.timus.ru/author.aspx?id=16378Thanks a lot to Sandro's rejudge!!! :)))))))) P.S. It can be solved more faster like O(n). I think I'll try to find O(N) algo than to write O(2^n) solution. In this case I'd learn nothing. Try to sort from any parameters: x+y; abs(x)+abs(y); abs(x)-abs(y) - it's strange sort, but it helped me; Try to move not from first to last, but from first and last at the same time. Use the SHAMANISM! :) Edited by author 11.02.2008 22:30 Simple brute-force solution gets AC. I think, tests may be improved to crash them. But in this case I don't know effective solution of the problem... My program: Program t1130;{$N+} Const MaxN=10000; Var T :array[1..MaxN,1..3]of longint; N,i,j :longint; L :extended; Ci,Cj :extended; ex :boolean; begin FillChar(T,SizeOf(T),0); Ci:=0; Cj:=0; Read(N,L); for i:=1 to N do begin Read(T[i,1],T[i,2]); T[i,3]:=1; Ci:=Ci+T[i,1]; Cj:=Cj+T[i,2]; end; Repeat ex:=true; for i:=1 to N do if T[i,3]=1 then if Sqr(Ci-2*T[i,1])+Sqr(Cj-2*T[i,2])<Ci*Ci+Cj*Cj then begin T[i,3]:=-1; Ci:=Ci-2*T[i,1]; Cj:=Cj-2*T[i,2]; ex:=false; end else if Sqr(Ci+2*T[i,1])+Sqr(Cj+2*T[i,2])<Ci*Ci+Cj*Cj then begin T[i,3]:=1; Ci:=Ci+2*T[i,1]; Cj:=Cj+2*T[i,2]; ex:=false; end; if (ex)and(Ci*Ci+Cj*Cj>2*L*L) then begin T[N,3]:=-1*T[N,3]; Ci:=Ci+2*T[N,3]*T[N,1]; Cj:=Cj+2*T[N,3]*T[N,2]; ex:=false; end; Until ex; Writeln('YES'); for i:=1 to N do if T[i,3]=1 then Write('+') else Write('-'); Writeln; end. {$n+} Program Walk; Var i,j,k,m,n,bj:longint; x,y,z:double; a:array[1..10001,1..2] of integer; e:array[1..10001] of shortint; Begin fillchar(a,sizeof(a),0); fillchar(e,sizeof(e),0); read(n); read(z); x:=0; y:=0; for i:=1 to n do begin e[i]:=1; read(a[i,1],a[i,2]); x:=x+a[i,1]; y:=y+a[i,2]; end; while x*x+y*y-2*z*z>1e-14 do begin for i:=1 to n do if sqrt(x*x+y*y)-Sqrt(sqr(x-2*a[i,1]*e[i])+sqr(y-2*a[i,2]*e[i])) >1e-14 then begin x:=x-2*a[i,1]*e[i]; y:=y-2*a[i,2]*e[i]; e[i]:=-e[i]; if 2*z*z-x*x-y*y>1e-14 then break; end; end; writeln('YES'); for i:=1 to n do if e[i]=-1 then write('-') else write('+'); writeln; End. Dont believe this programm it gets TLE on test12 I use recursion (with optimization :)) and got AC 0.015! I submited O(N^2) solution and got AC with time 0.25. Is it normal? :) There is a O(N) solution. I know. I accepted it too. |
|