Page 1 of 6

10487 - Closest Sums

Posted: Mon May 05, 2003 4:17 pm
by deddy one
hi this is my algorithm

1.scan the input
2.store each two distinct closest sum in array
3.scan the query
4.search the answer from the array sequentially


but it's slow to get accepted.
can anyone give me a better approach in this problem???

Posted: Tue May 06, 2003 8:43 am
by Dominik Michniewski
I got Acc in the same way, but ....
after creating all possible pairs I sort them and use bsearch to search query values ...
I don't know how we could get better time in this problem ...

DM

Posted: Tue May 06, 2003 8:58 am
by Adrian Kuegel
You can sort the input values and find the answer to each query (without constructing all possible sums) in linear time. Think about it, it is not too difficult.

Posted: Tue May 06, 2003 9:43 am
by Eric
I do similar things.
1). Read input
2). Add distinct numbers
3). Sort the sum by shell sort
4). Read query
5). Binary search the answer
Until N=0
But I get TLE. :-?
Can anyone help me?

Posted: Tue May 06, 2003 10:34 am
by soyoja
I think that this problem can solve with no sort.
Use hashing, instead of sort... The range of input data is only 1000...
So you can use hashing technique by array.
Good luck~

Posted: Tue May 06, 2003 10:46 am
by anupam
but why my program got rte.
please help.
what may be array size of distinct number array?
-
anupam
:oops: :oops: :oops:

Posted: Tue May 06, 2003 11:39 am
by Dominik Michniewski
shell sort has time complexity O(N^2) I think, try to use qsort
this table should have N*N size ... maybe this cause error ...

Best regards
DM

Posted: Tue May 06, 2003 1:11 pm
by Eric
Oh... actually I neither know how to implement quick sort in PASCAL nor hashing. I really need to learn a lot. :o
Btw, I think the table should have only N*(N-1)/2 size. I haven't declare so large. :wink:

Posted: Tue May 06, 2003 2:15 pm
by Dominik Michniewski
You have right - I always try to declare only such big tables as is necessary ... :)

Try to search net for QSORT or QUICK SORT and you take a lot of sources I think

DM

Posted: Wed May 07, 2003 7:00 am
by anupam
dominik and other bosses,
please help abt getting my run time error.
what may be the size of the distinct sum array?i take 500000.
is'nt it sufficient?
i will put my code if you can't guess.
---
anupam :oops: :oops: :oops:

Posted: Wed May 07, 2003 10:10 am
by Eric
Thanks, I have now re-written the code with quicksort and got accpeted in a second.
I think I will not use other sorting afterward. :wink:
Btw, is it a stable sort?

Posted: Wed May 07, 2003 12:57 pm
by deddy one
to anupam :

I declare

[c]int sum[1000000][/c]

before this I always get Run time error

Posted: Wed May 07, 2003 1:02 pm
by deddy one
btw the algorithm that I describe above
(without any sorting and bsearch)
is accepted in 0.9 sec

but I see that in top ten rank
for this problem,
the time to get accepted is incredible

and I still couldn't figure out how
to do this in linear time
:oops: :oops: :oops:

10487, 10489 and 10490

Posted: Thu May 08, 2003 7:41 pm
by Pier
I have problems with this three programs. Any help is appreciated!

Problem 10487:
[pascal]Var
c,i,j,k,m,n,s,t: integer;
a: array [1..1000] of integer;

Begin
readln(input,n); c:= 0;
While (n<>0) do
begin
Inc(c); writeln(output,'Case ',c,':');
for i:= 1 to n do
readln(input, a);
readln(input,m);
for i:= 1 to m do
begin
readln(input,s); t:= maxint;
for j:= 1 to n do
for k:= j+1 to n do
if abs(a[j]+a[k]-s) < abs(t-s) then t:= a[j] + a[k];
writeln(output,'Closest sum to ',s,' is ',t,'.');
end;
readln(input,n);
end;
End.[/pascal]

Problem 10489:
[pascal]Var
a,n,p,s: longint;
b,i,j,k,m,t: byte;

Begin
readln(input,t);
for i:= 1 to t do
begin
readln(input,n,b); s:= 0;
for j:= 1 to b do
begin
read(input,m); p:= 1;
for k:= 1 to m do
begin
read(input, a);
p:= p*a;
end;
Inc(s,p);
end;
writeln(output,s mod n);
end;
End.[/pascal]

Problem 10490:
[pascal]{$N+}
Var
n: longint;
r: extended;

Function Primo(n: Longint): boolean;
var
i: Longint;
res: boolean;
begin
res:= true; i:= 3;
if (n mod 2= 0) then res:= false;
Repeat
if (n mod i= 0) then
begin
res:= false;
break;
end;
Inc(i,2);
until (i>trunc(sqrt(n)));
if (n=2) or (n=3) then res:= true;
primo:= res;
end;

Begin
readln(input,n);
While (n<>0) do
begin
r:= exp(n*ln(2)) -1;
if primo(trunc(r)) then writeln(output,'Perfect: ',r*exp((n-1)*ln(2)):0:0,'!')
else if primo(n) then writeln(output,'Given number is prime. But, NO perfect number is available.')
else writeln('Given number is NOT prime! NO perfect number is available.');
readln(input,n);
end;
End.[/pascal]

Posted: Thu May 08, 2003 10:25 pm
by turuthok
For 10487, probably the solution to your WA is to ignore the (a+b) where a == b ...

For 10489, I don't think your p := p*a statement can survive overflow problem eventhough you declared p as longint.

-turuthok-