## 10487 - Closest Sums

Moderator: Board moderators

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

### 10487 - Closest Sums

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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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.

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong
I do similar things.
3). Sort the sum by shell sort
Until N=0
But I get TLE.
Can anyone help me?

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:
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~

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
but why my program got rte.
what may be array size of distinct number array?
-
anupam
"Everything should be made simple, but not always simpler"

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong
Oh... actually I neither know how to implement quick sort in PASCAL nor hashing. I really need to learn a lot.
Btw, I think the table should have only N*(N-1)/2 size. I haven't declare so large.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
dominik and other bosses,
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
"Everything should be made simple, but not always simpler"

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong
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.
Btw, is it a stable sort?

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm
to anupam :

I declare

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

before this I always get Run time error

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm
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

Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:

### 10487, 10489 and 10490

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
While (n<>0) do
begin
Inc(c); writeln(output,'Case ',c,':');
for i:= 1 to n do
for i:= 1 to m do
begin
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;
end;
End.[/pascal]

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

Begin
for i:= 1 to t do
begin
for j:= 1 to b do
begin
for k:= 1 to m do
begin
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
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.');
end;
End.[/pascal]
There are 10 kind of people on this world: those who understand binary and those who don't!

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).