ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1021. Sacrament of the Sum

I have an O(1) way to find the answer.
Posted by grayluck 10 Sep 2009 08:34
just put all the numbers in a array of boolean.

var
n,i,caint:longint;
b:array[-100000..100000]of boolean;
begin
fillchar(b,sizeof(b),false);
for i := 1 to n do
begin
b[caint]:=true;
end;
for i := 1 to n do
begin
if b[10000-caint] then
begin
writeln('YES');
halt;
end;
end;
writeln('NO');
end.

Edited by author 10.09.2009 08:34
Re: I have an O(1) way to find the answer.
Posted by Pavel Sergeev 15 Oct 2009 00:28
I think it is O(n2)
Re: I have an O(1) way to find the answer.
Posted by SkidanovAlex 15 Oct 2009 11:04
It is O(n), not O(1)

And there's another O(n) solution for this problem, which requires only O(n) memory instead of O(v) in your case, where v is max value of a_i.
Re: I have an O(1) way to find the answer.
Posted by nguyenductam 3 Apr 2010 11:13
Yes , SkidanovAlex right. O(n).
Re: I have an O(1) way to find the answer.
Posted by Mariana 24 Sep 2012 16:31
thanks