In fact many of you got AC with O(N1*N2) solution. Some new tests were added and some more will be added soon. This problem had very simple O(N) and O(N*log N) solutions but unfortunately very weak tests. 756 authors had already lost their AC.

Extra tests were added and Time Limit was decreased to 1 second. Because of limitations [-32768, 32767] some O(N^2) solutions still have AC, but these limitations will not be changed. Investigation is finished. :)

Are the limits the same?
I have O(n1+n2) and TLE#8
Is it too slow?!

Your algo is correct. Sorry for wrong verdict. This was a system bug.

On 3rd test my program get time 0.14 but system says "Time limit exceeded"..

Is this a bug?

I try pass problem again, and got AC...

Edited by author 26.03.2007 23:29

My solution got AC by tnow it TL on 4 test
Thise code for those who can answer to my problem

var a:array[1..50001]of integer;
    n,i,j,k,m:longint;
begin read(n);
      for i:=1 to n do read(a[i]);
      read(m);
      for i:=1 to m do
          begin read(k);
                for j:=1 to n do
                    if (a[j]+k=10000) then
                       begin write('YES');
                             halt(0);
                       end;
          end;
      write('NO');
end.

Your solution complexity is O(N*M), which is too slow. Try to find a better algorithm. Good luck!

 i got one with O(nlogn) but what the O(n) one ? you mean that we use hash to search ?

I use binary search. But I have WE on test 5.
What's problem? Solution complexity is O(n+m).

Just use array of bool

here is my code and i've time limit test 10.
begin
  read(n);
  for i := 1 to n do
  read(a[i]);
  q := false;

  read(m);
  q1 := true;
  read(x);
  if x+a[n]<10000 then q1 := false
  else  begin   i := n;
      repeat
        if x+a[i]=10000 then q := true;
        i := i - 1;
      until (i=0) or (x+a[i]<10000);
        end;

  if q1 then
    begin
  for j := 1 to m-1 do
    begin
      read(x);
        i := n;
        repeat
        if x+a[i]=10000 then q := true;
        i := i - 1;
        until (i=0) or (x+a[i]<10000);
    end;
    end
  else  for j := 1 to m-1 do
          read(x);
  if q then write('YES')
  else write('NO');
end.
who can give me more correct than mine, pls!!

your solution is too slow
there is O(n + m) solution
for example
4
5 7 10 15
5
[and some numbers]
at first you can read first group of 4 numbers (5, 7, 10,15)
and while you read second group you can easy check
is it 9995, 9993, 9990, 9985 or not

after reading next integer from second group
you dont need to check all 4 numbers.
you can do it fast just using array of boolean

thanks!!, but I find new algo
begin
  read(n);
  for i := 1 to n do
  read(a[i]);

  q := false;
  j := 0;
  read(m);
  repeat
    inc(j);
    read(x);           i1 := 1;   ni := n;
      if (a[i1]+x<=10000) and (a[ni]+x>=10000) then
        begin  i := 0;
          repeat
          inc(i);
        if a[ni div 2]+x<=10000 then i1 := ni div 2
        else ni := ni div 2;
          until (i=10) or (ni-i1<=3);

     for i := i1  to ni do
     if a[i]+x=10000 then q := true;
       end;
  until (q) or (a[n]<=10000) or (j=m);
  if q then write('YES')
  else write('NO');
end.
but i've WA#3 now!!

using a bool array of length 65000 will solve it very very fast.//idea of bucket sort

Edited by author 13.06.2008 02:08