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.

actually L ≤ 100

What is the answer for test:
4 10
0 10
10 0
1 1
5 -5

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

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.

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

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.

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?

:)