Page 1 of 3

529 - Addition Chains

Posted: Fri Jul 26, 2002 4:36 pm
by Revenger
I can't understand why this program gets Accepted 8)

I use a such algorithm:

1. Consider that sequence <a0,a1,..,am> is good if and only if it is the answer for N = am

2. If sequence <a0,a1,..,am,a(m+1)> is good then the sequence <a0,a1,..,am> is also good.

So, I find all good sequences with length 1, then 2, then 3 etc.

The maximum length of good sequences (for N=1..10000) is 18 (Anyone who get Accepted can said so). There are about 2000000 good sequences of length 17.

But, in my program I consider
maximum length = 15
maximum number of good sequences = 50000

and it get Accepted :evil:

I want to get Accepted with correct program!
Can anyone help me?

[pascal]Program p529;

Const MaxD = 15;
MaxN = 10000;
MaxComb = 50000;

Type ChainType = Array[0..MaxD]of ShortInt;

Var Inf : Array[1..MaxN]of ChainType;
NewT,OldT : Array[1..MaxComb]of ChainType;
nt,ot : Integer;
N,i,j : Integer;

Procedure Rec(Step,WT : Integer);
Var i,j,k,p : Integer;
begin
for i:=Step downto 1 do
for j:=Step downto i do begin
p:=OldT[WT,i]+OldT[WT,j];
if (p>OldT[WT,Step]) And (p<=MaxN) then
if Step+1<Inf[p,0] then begin
for k:=1 to Step do Inf[p,k]:=OldT[WT,k];
Inf[p,Step+1]:=p;
Inf[p,0]:=Step+1;
end;
end;
end;

Procedure Rec2(Step,WT : Integer);
Var i,j,k,p : Integer;
begin
for i:=Step downto 1 do
for j:=Step downto i do begin
p:=OldT[WT,i]+OldT[WT,j];
if (p>OldT[WT,Step]) And (p<=MaxN) then
if Step+1=Inf[p,0] then begin
if nt=MaxComb then exit;
nt:=nt+1;
for k:=1 to Step do NewT[nt,k]:=OldT[WT,k];
NewT[nt,Step+1]:=p;
end;
end;
end;

begin
Inf[1][0]:=1;
Inf[1][1]:=1;
for i:=2 to MaxN do Inf[i,0]:=100;

ot:=1;
OldT[1]:=Inf[1];
for i:=2 to MaxD do begin
nt:=0;
for j:=1 to ot do Rec(i-1,j);
if i<MaxD then for j:=1 to ot do Rec2(i-1,j) else Break;
for j:=1 to nt do OldT[j]:=NewT[j];
ot:=nt;
end;

While True do begin
Read(N);
if N=0 then Break;
Write('1');
for i:=2 to Inf[N][0] do Write(' ',Inf[N]);
Writeln;
end;
end.[/pascal]

529 Addition Chains Help!!

Posted: Wed May 07, 2003 10:26 am
by tonyk
I don't know how to slove this problem.
Anyone give me some hints??
Or give me a correct program(written in C or C++)
Many thanks!!

Posted: Wed May 07, 2003 1:01 pm
by junjieliang
I'm not sure about others, but I used IDA* with an obvious heuristic...

Posted: Wed May 07, 2003 9:55 pm
by Adil
junjieliang, thank you for your very useful hint. i got AC in 0.029 sec time. however, there are much better time than that. did someone use anyother technique?

junjieliang, have you used IDA* for any other prob on this site?

Posted: Thu May 08, 2003 1:34 pm
by junjieliang
Well, I just started learning IDA*, so I've not used it on any other problems yet.

Posted: Sun May 25, 2003 2:31 pm
by Ronald29
Find all posibility using recursive. to find the minimum, try to find it on each level, don't go to the next level of recursive if all value in one level not checked. It's the most simple algorithm I can found, if anyone know another algorithm please let me know. thx, hope this can help you...tonyk :wink:

Posted: Wed Nov 12, 2003 2:32 pm
by Julien Cornebise
junjieliang wrote:I'm not sure about others, but I used IDA* with an obvious heuristic...
Hi
What is IDA* please ? Could anyone give me a good URL describing it ?
(isn't it that sort of Alpha and Beta cut ?)

Posted: Thu Nov 13, 2003 11:46 am
by Julien Cornebise
Hi.
I finally found what is ID (Incremental Deepening). I used it, and have a fine program for n <= 100 (wich makes the chain length be 9).
But with the new limit, n <= 10000, I can't solve it !! It's far too slow... I stop my deepening as soon as the new element to insert in the chain is > n. Is there a better condition ?
Please help me, thank you :-)

Posted: Thu Nov 13, 2003 11:57 am
by Julien Cornebise
Hi
I don't understand why you consider your program as wrong... If your program gets AC with your limits, this means that there are not cases longer than 15 in the sample input. So, if you change your constants, it should still work, because it will find the answer with length 15 before having to try length 18.
Or is there something that I did not understand in your explanation (sorry, I'm not familiar with pascal).

(BTW : I'm still stuck with this problem, TLE, though using incremental deepening. Any idea ? :)

Posted: Thu Nov 13, 2003 2:11 pm
by junjieliang
Hi,

I think what you're saying is iterative deepening search instead, where you increase the limit by a constant value (eg 1) after every search to go deeper.

IDA* is slightly different. Instead of adding 1, you use a heuristic to guess how much to increase by. This heuristic should not overestimate however, else the algorithm will be wrong.

Hope that helps.

Posted: Thu Nov 13, 2003 5:49 pm
by anupam
hey, check out again, your program gets wa..
--
anupam

Posted: Thu Nov 13, 2003 7:40 pm
by Julien Cornebise
junjieliang wrote:Hi,

I think what you're saying is iterative deepening search instead, where you increase the limit by a constant value (eg 1) after every search to go deeper.

IDA* is slightly different. Instead of adding 1, you use a heuristic to guess how much to increase by. This heuristic should not overestimate however, else the algorithm will be wrong.

Hope that helps.
Mmmm.... I guess I see the global meaning of it all, but I don't see wich euristic I could use. I'll try to think of it. If I'm still stuck by tomorow, could you please give me a hint ?

But, anyway, even if I can "guess" what the length of the chain is (should be >= ln(n) with ln in basis 2, I think), the search in between the chain is still veeery long, isn't it ?

This is the first time I meet that kind of algorithm (always used simple stupid BFS)...

Posted: Fri Nov 14, 2003 2:49 pm
by Julien Cornebise
Hi

After a whole night trying to find the heuristic mentionned above, I'm ashamed to confess that I don't see it :oops: :(
Could you please give me a hint ? I'm stuck and it's prettily annoying me ... :/
Thanks !

Posted: Sat Nov 15, 2003 12:00 pm
by junjieliang
You're right about the heuristic having something to do with log base 2. Assume that in your search the last number is n, and your target is t. Then an estimate of the number of steps more that you need will be log(t/n), where the log base 2 of course...

To shorten the runtime, you can break early with the help of the heuristic. Say you're at depth 5, and the heuristic says there are at least 3 steps more. If your upper bound so far is less than 8 (5 + 3), then you know there's no way you can get an answer, and you can just break out of the search early.

Posted: Sun Nov 16, 2003 10:09 pm
by Julien Cornebise
Thank you

I'll try this as soon as I'll have recuperated from SWERC (it was today, and I'm a bit dead)...

Thank you :-)