Обсуждение @ 1021. Таинство суммы @ Timus Online Judge

Sandro (USU) Problem 1021 is under investigation. (+) [13] // Задача 1021. Таинство суммы 20 мар 2007 00:15

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.

Sandro (USU) Re: Problem 1021 is under investigation. (+) [3] // Задача 1021. Таинство суммы 20 мар 2007 11:13

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. :)

AlMag Re: Problem 1021 is under investigation. (+) [2] // Задача 1021. Таинство суммы 20 мар 2007 17:10

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

Sandro (USU) Re: Problem 1021 is under investigation. (+) [1] // Задача 1021. Таинство суммы 20 мар 2007 21:39

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

Asker_Kazharov What's test 5 // Задача 1021. Таинство суммы 27 авг 2007 17:25

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

Evgenij Makarov (Vologda SPU#2) Re: Problem 1021 is under investigation. (+) [8] // Задача 1021. Таинство суммы 26 мар 2007 17:19

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

Shady TKTL Why They Have Changed Tests [7] // Задача 1021. Таинство суммы 1 апр 2007 19:48

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.

Samsonov Alex [USU] Re: Why They Have Changed Tests [3] // Задача 1021. Таинство суммы 1 апр 2007 19:50

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

mathfrog Re: Why They Have Changed Tests [2] // Задача 1021. Таинство суммы 26 авг 2007 20:27

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

DixonD (Lviv NU) Re: Why They Have Changed Tests [1] // Задача 1021. Таинство суммы 28 авг 2007 17:30

Just use array of bool

Madhav Re: Why They Have Changed Tests // Задача 1021. Таинство суммы 13 июн 2008 02:07

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

Bobur Re: Why They Have Changed Tests [2] // Задача 1021. Таинство суммы 5 дек 2007 18:48

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!!

Alias (Alexander Prudaev) Re: Why They Have Changed Tests [1] // Задача 1021. Таинство суммы 5 дек 2007 23:32

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

Bobur Re: Why They Have Changed Tests // Задача 1021. Таинство суммы 7 дек 2007 07:26

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!!

Обсуждение задачи 1021. Таинство суммы